树树一个有n(n >= 0)个节点组成一个有限集合1 有且仅有一个被称为根节点(root)的节点2 当n > 1,除了根节点之外，剩余的m个节点互不相交，分别都是一颗颗的树这些树我们称为子树，每一个节点实际上都是一棵树(子树)的根树的每一个节点都包含两个部分1 数据元素2 节点和节点之间的关系，不像原先的链表，关系都是一个方向上面1个节点可能有n个节点和它有关系(因此它就不是一个线性表)每个节点的关系数量我们称为这个节点的度度：出度(我可以到别人)，树里面我们暂时只考虑出度 入度(别人到我)在树里面如果一个节点和别人没有关系了(出度为0)，这种节点我们称之为终端节点(叶子节点)树的层次(深度)：从根开始，根为第一层，根的儿子为第二层，儿子的儿子为第三层......不能乱了辈分二叉树 -- 一种树的形态，每个节点的度(出度)最多只有2，如果你的树满足这一点这棵树就被称为二叉树，二叉树我们就可以分大小两边根据这个大小我们可以分为左右关系，左边的被称为左儿子右边的被称为右儿子二叉树有5种形态1 空树2 只有一个根节点3 只有一个左儿子4 只有一个右儿子5 有左右儿子二叉树的基本性质1 在二叉树的第i(i从1开始)层上面最多有 2 ^ (i - 1)2 深度为k的二叉树最多有 2 ^ k - 1 个节点3 对于任何一个二叉树，有如下关系n0为度为0的节点个数 n1为度为1的节点个数 n2为度为2的节点个数 n为总节点数n = n2 + n1 + n0n = 分支数(出度的个数) + 1分支数 = 2 * n2 + 1 * n1 n = 2 * n2 + 1 * n1 + 1so:2 * n2 + 1 * n1 + 1 = n2 + n1 + n0-> n2 + 1 = n0->这个性质对于任何一个多叉树都是适用的假设你是一个m叉树n = n0 + n1 + n2 + n3 + .... + nmn = 分支数(出度的个数) + 1分支数 = m * nm + (m - 1) * n(m - 1) + .... + 3 * n3 + 2 * n2 + 1 * n1n0 + n1 + n2 + n3 + .... + nm = m * nm + (m - 1) * n(m - 1) + .... + 3 * n3 + 2 * n2 + 1 * n1 + 1n0 = 1 + n2 + 2n3 + 3n4 + .... + (m - 1)nm ----> 可以直接套公式的二叉树的两种特殊的形态满二叉树：深度为k的二叉树有 2 ^ k - 1 个节点，这颗二叉树就是一颗满二叉树不增加深度的情况，不能往这棵树里面添加节点完全二叉树：1 除去最后一层是一个满二叉树2 最下面的那一层所有的节点都是尽左排，一个节点的左边是不能添加新的节点满二叉树是一个特殊的完全二叉树 4 对于一个有n个节点的完全二叉树从上到下，从左往右，从1开始进行编号根为1 根的左儿子为2 根的右儿子为3 ......假设有一个节点的编号为 i 则，这个节点的父节点的编号为 i / 2如果它有左儿子，那么它左儿子的编号为 2 * i如果它有右儿子，那么它右儿子的编号为 2 * i + 15 具有n个节点的完全二叉树的深度为 log2(n) 向下取整 + 1假设深度为k2 ^ (k - 1) <= n < 2 ^ k计算机如何来使用二叉树首先我们应该要保存二叉树1 数据2 左右儿子(关系)1 顺序结构来保存二叉树由于完全二叉树是可以表示左右儿子关系和父亲关系的因此完全二叉树才能用数组存储就是上面的第4个性质如果这棵树不是完全二叉树呢？数组保存不了，因此需要将不是完全二叉树的二叉树补全为完全二叉树才能使用数组保存，这么一来浪费就有点多了因此顺序结构存储二叉树就不是那么方便2 链式结构保存1 有数据域2 有指针域 -> 至少要有两个指针 lchild rchildstruct TreeNode{Tree_Datatype data;//树的数据struct TreeNode * lchild;//指向它的左儿子struct TreeNode * rchild;//指向它的右儿子};二叉树的遍历：遍历:根据某一种规则对集合里面所有元素的访问(必须访问1次，并且只能访问一次)二叉树的遍历有三种(左边在右边的前面)1 先序(根)遍历 -> 根 左 右首先:先访问根节点再次：以相同的规则继续访问根节点的左儿子最后：以相同的规则继续访问根节点的右儿子2 中序(根)遍历 -> 左 根 右首先以相同的规则访问它的左孩子访问根节点最后以相同的规则继续访问根节点的右儿子3 后序(根)遍历 -> 左 右 根首先以相同的规则访问它的左孩子再以相同的规则继续访问根节点的右儿子访问根节点练习：一棵二叉树的先序为：EBADCFHGIKJ中序为:ABCDEFGHIJK请画出这棵树先中序、中后序能确定这棵树但是先后序不一定能确定这棵树建立一棵二叉树：建立树之前我们需要先确定左边是什么关系，右边是什么关系这种确定关系的二叉树我们叫二叉排序树一般是根绝大小来进行确定的一般左边为小右边为大示例代码为左小右大删除树里面一个节点 : 删除一个节点之后我们不能影响这个树的排序性(每个节点的左边都是小的，右边都是大的)1 最特殊的，这个树是空树2 这棵树就只有这么一个根节点，你还把它删了(这会导致树的根节点发生变化)3 删除的这个节点只有一个左孩子4 删除的这个节点只有一个右孩子5 你要删除的这个节点是一个叶子6 你要删除的节点有两个孩子我们在建立这棵树的时候，这棵树有可能变得奇怪比如说这棵树变得像一个链表一样如你的加入顺序为ABCDEFG还有像一个蚯蚓一样还有很多种奇怪的情况，遇到这种情况树的查找效率就变得很低了树的优势就没有了，因此我们需要处理，让这棵树看起来更像一棵树这种操作我们叫平衡处理AVL树 -> 平衡二叉树 height-balanced tree / balanced binary tree规定AVL树里面所有节点的左孩子和右孩子的高度差的绝对值不超过1这颗树我们就叫AVL树AVL树在创建的时候我们就需要做平衡处理，加入一个节点就可能造成某一个节点不平衡因此我们需要对每个节点都要做平衡处理 -- 由于没加如一个节点都要做平衡处理，因此它的添加效率较低但是由于是平衡的，因此它的查找效率很高如果想要它的插入效率高一点，查找效率也高 --- 红黑树(有限的平衡)AVL树我们需要做平衡处理1 当我们往一个节点的左边的左边插入了一个节点，这个时候引起了这个节点的不平衡单向右旋2 当我们往一个节点的右边的右边插入了一个节点，这个时候引起了这个节点的不平衡单向左旋3 当我们往一个节点的左边的右边插入了一个节点，这个时候引起了这个节点的不平衡先左旋再右旋4 当我们往一个节点的有边的左边插入了一个节点，这个时候引起了这个节点的不平衡先右旋在左旋左左为右右右为左左右为左右右左为右左线索：树是非线性的，通过线索我们可以将树的遍历变成线性的先序线索 中序线索 后序线索将树的非线性转换成一个链表的线性在树节点里面加上一个成员struct ListTreeNode * _prenext; 先序线索指针 指向先序遍历的下一个中序后序亦然最小生成树 ： 将所有的节点都连接起来，节点与节点的连接线上面有一个权值()为了解决成本最低的问题每次都在带加入节点里面找到权值最小的，将它加入到我们的树里面去加入的时候不一定会和原树连接在一起，别急，你还要加的当所有的节点全部被覆盖，你的最小生成树就弄完了哈夫曼树：每个节点都是带值的，每次在待加入的节点里面找最小的两个将这两个最小的节点合成一个新的节点根据大小关系将树给建立出来多个树在一起就是森林
平时看到的树都是多叉树，但是处理的时候我们需要转换为二叉树将多叉树转为二叉树：1 先将所有的兄弟依次连接起来(大哥连二哥，二哥连三哥.....)2 断开除了大哥和父亲的关系以外的父子关系3 拉开兄弟之间的连线，节点变成它前面的那个哥哥的右孩子(大哥的右孩子是二哥，二哥的右孩子是三哥..)长子变成它的左孩子森林转为二叉树 -> 根据多叉树转二叉树的规则可以知道，转出来的二叉树是没有右孩子的，其它树都往前面一棵树上的右孩子去接二叉树转树1 将父节点与子节点的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子...连接起来2 断掉所有的右孩子关系二叉树转森林根节点的右孩子是二颗树根节点的右孩子的右孩子是第三颗树.....
