数据结构——二叉树

一.概念

1.结点的度：⼀个结点含有⼦树的个数称为该结点的度；

2.树的度：⼀棵树中，所有结点度的最⼤值称为树的度；

3.叶⼦结点或终端结点：度为0的结点称为叶结点；

4.双亲结点或⽗结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；

5.孩⼦结点或⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点

6.根结点：⼀棵树中，没有双亲结点的结点；

7.结点的层次：从根开始定义起，根为第1层，根的⼦结点为第2层，以此类推

8.树的⾼度或深度：树中结点的最⼤层次；

二.二叉树

1.概念

树的度为2的，⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

2.两种特殊的二叉树

满二叉树：一颗二叉树如果每层的结点数都达到最⼤值，则这棵⼆叉树就是满⼆叉树。

也就是说，如果⼀棵⼆叉树的层数为K，且结点总数是 ，则它就是满⼆叉树。

完全二叉树：完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点⼀ 对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

3.二叉树的性质

1.若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i - 1)(i>0)个结点

2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点总数是((2 ^ k) - 1)(k>=0)

3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1 (度为0的结点比度为2的结点多一个)

4. 具有n个结点的完全⼆叉树的深度k为log(n + 1)上取整

5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点

若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦

若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦

4. 二叉树的遍历

1.前序遍历：根结点 --> 左子树 --> 右子树

2.中序遍历：左子树 --> 根结点 --> 右子树

3.后序遍历：左子树 --> 右子树 --> 根结点

4.层序遍历：从上到下从左到右依次遍历