Question

二叉树的基本概念

Answer 1

二叉树是另一种树形结构，其特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
与树相似，二叉树也以递归的形式定义。二叉树是n(n≥0)个结点的有限集合：
①或者为空二叉树，及n=0。
②或者由一个根结点和两个互不相交的称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
二叉树有五种不同的基本形态： A：空二又树 B：只有一个根结点的二叉树 C：右子树为空的二叉树 D：左子树为空的二叉树 E：左、右子树都非空的二叉树

1）满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
2）完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
这种树特点如下：
①若i≤⌊n/2⌋，则结点i为分支结点，否则为叶子结点。
②叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
③如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。
④若n为奇数，则每个分支结点都有左子女和右子女；若n为偶数，则编号最大的分支结点（编号为n/2）只有左子女，没有右子女，其余分支结点左、右子女都有。
3）二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。
4）平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。

1）非空二叉树上叶子结点数等于度为2的结点数加1，即N0=N2+1
2）非空二叉树上第K层上至多有2^(k-1)个结点(k≥1)。
3）高度为H的二叉树至多有2^H-1个结点(H≥1)。
4）对完全二叉树按从上到下、从左到右的顺序依次编号1，2，...，N，则有以下关系：
①当i>1时，结点i的双亲结点编号为⌊i/2⌋，即当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。
②当2i≤N时，结点i的左孩子编号为2i，否则无左孩子。
③当2i+1≤N时，结点i的右孩子编号为2i+1，否则无右孩子。
④结点i所在层次（深度）为⌊log2(i)⌋+1。
5）具有N个（N>0）结点的完全二叉树的高度为⌈log2(N+1)⌉或⌊log2(N)⌋+1。