树具有如下最基本的性质：

1. 树中的结点数等于所有结点的度数加 1。
2. 度为 m 的树中第 i 层上至多有 (m^{i-1}) 个结点（(ige 1)）。
3. 高度为 h 的 m 叉树至多有 (frac{m^h-1}{m-1}) 个结点。
4. 具有 n 个结点的 m 叉树的最小高度为 (lceil log_m(n(m-1)+1)rceil)。

4.2 二叉树的概念

4.2.1 二叉树的定义及其主要特性

（1）二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
与树相似，二叉树也以递归的形式定义。二叉树是 n（(nge 0)）个结点的有限集合：

1. 或者为空二叉树，即 n=0。
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。
   左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，就成为另一棵不同的二叉树。
即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树的 5 种基本形态如图 4-2 所示：

二叉树与度为 2 的有序树的区别：

1. 度为 2 的树至少有 3 个结点，而二叉树可以为空：
2. 度为 2 的有序树的孩子结点的左右次序是相对于另一孩子结点而言的，如果某个结点只有一个孩子结点，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为 2,均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言，而是确定的。

（2）几个特殊的二叉树

1. 满二叉树：一棵高度为 h,并且含有 (2^h-1) 个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点，如图 4-3(a) 所示。
   满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2。
   可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1）起，自上而下，自左向右。
   这样每个结点对应一个编号，对于编号为 i 的结点，如果有双亲，其双亲为 (lfloor i/2 rfloor)，如果有左孩子，则左孩子为 2i；如果有右孩子，则右孩子为 2i+1。
   

   

2. 完全二叉树：设一个高度为 h,有 n 个结点的二叉树，当且仅当其每一个结点都与髙度为 h 的满二叉树中编号为 (1sim n) 的结点一一对应时，称为完全二叉树，如图 4-3(b) 所示。
   这种树的特点如下：
   1. 若 (ilelfloor n/2rfloor)，则结点 i 为分支结点，否则为叶子结点。
   2. 叶子结点只可能在层次最大的两层上出现。
      对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
   3. 如果有度为 1 的结点. 只可能有一个，且该结点只有左孩子而无右孩子（重要特征）
   4. 按层序编号后，一旦出现某结点（其编号为 i）为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点。
   5. 若 n 为奇数，则每个分支结点都有左子女和右子女；若 n 为偶数，则编号最大的分支结点（编号为 n/2）只有左子女，没有右子女，其余分支结点左、右子女都有。
3. 二叉排序树：
   或者是空二叉树，或者是具有如下性质的二叉树：
   左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。
   左子树和右子树又各是一棵二叉排序树。

4. 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1。

（3）二叉树的性质

1. 非空二叉树上叶子结点数等于度为 2 的结点数加 1,即 (N_0 = N_2+1)。
   证明：设度为 0、1 和 2 的结点个数分别为 (N_0)、(N_1) 和 (N_2)，结点总数 (N=N_0+N_1+N_2)。
   再看二叉树中的分支數，除根结点外，其余结点都有一个分支进入，设 B 为分支总数，则 N=B+1。
   由于这些分支是由度为 1 或 2 的结点射出的，所以又有 (B=N_1+2N_2)。
   于是得：(N_0+N_1+N_2=N_1+2N_2+1)，则 (N_0=N_2+1)。

   注意：该结论经常在选择題中用到，希望考生牢记并灵活应用。

2. 非空二叉树上第 K 层上至多有 (2^{k-1}) 个结点（(Kge 1)）。
3. 高度为 H 的二叉树至多有 (2^H-1) 个结点（(Hge 1)）。
4. 对完全二叉树按从上到下、从左到右的顺序依次编号 (1,2,N)，则有以下关系：
   • 当 (igt 1) 时，结点 i 的双亲结点编号为 (lfloor i/2rfloor)，即
     当 i 为偶数时，其双亲结点的编号为 i/2，它是双亲结点的左孩子；
     当 i 为奇数时，其双亲结点的编号为 (i-1)/2，它是双亲结点的右孩子。
   • 当 (2ile N) 时，结点 i 的左孩子编号为 2i，否则无左孩子。
   • 当 (2i+1le N)时，结点 i 的右孩子编号为 2i+1，否则无右孩子。
   • 结点 i 所在层次（深度）为 (lfloor log_2{i}rfloor+1)。

5. 具有 N 个（(Ngt 0)）结点的完全二叉树的高度为 (lceil log_2{(N+1)}rceil) 或 (lfloor log_2{N}rfloor+1)。

4.2.2 二叉树的存储结构

（1）顺序存储结构

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!