前⾔
树是数据结构中的重中之重，尤其以各类⼆叉树为学习的难点。⼀直以来，对于树的掌握都是模棱两可的状态，现在希望通过写⼀个关于⼆叉树的专题系列。在学习与总结的同时更加深⼊的了解掌握⼆叉树。本系列⽂章将着重介绍⼀般⼆叉树、完全⼆叉树、满⼆叉树、线索⼆叉树、霍夫曼树、⼆叉排序树、平衡⼆叉树、红⿊树、B树。希望各位读者能够关注专题，并给出相应意见，通过系列的学习做到⼼中
有“树”。
1 重点概念
结点是数据结构中的基础，是构成复杂数据结构的基本组成单位。
1.2 树结点声明
本系列⽂章中提及的结点专指树的结点。例如：结点A在图中表⽰为：
2 树
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意⼀颗⾮空树中： 1)有且仅有⼀个特定的称为根(Root)的结点；
2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每⼀个集合本⾝⼜是⼀棵树，并且称为根的⼦树。
蓝宝石4850
此外，树的定义还需要强调以下两点：
1)n>0时根结点是唯⼀的，不可能存在多个根结点，数据结构中的树只能有⼀个根结点。
2)m>0时，⼦树的个数没有限制，但它们⼀定是互不相交的。
⽰例树：
图2.1为⼀棵普通的树：
全能住宅改造王2011图2.1 普通树
由树的定义可以看出，树的定义使⽤了递归的⽅式。递归在树的学习过程中起着重要作⽤，如果对于递归不是⼗分了解，建议先看看递归算法
2.2 结点的度
结点拥有的⼦树数⽬称为结点的度。
图2.2中标注了图2.1所⽰树的各个结点的度。
图2.2 度⽰意图
2.3 结点关系
结点⼦树的根结点为该结点的孩⼦结点。相应该结点称为孩⼦结点的双亲结点。
图2.2中，A为B的双亲结点，B为A的孩⼦结点。
同⼀个双亲结点的孩⼦结点之间互称兄弟结点。
图2.2中，结点B与结点C互为兄弟结点。
2.4 结点层次
从根开始定义起，根为第⼀层，根的孩⼦为第⼆层，以此类推。
图2.3表⽰了图2.1所⽰树的层次关系
图2.3 层⽰意图
2.5 树的深度
树中结点的最⼤层次数称为树的深度或⾼度。图2.1所⽰树的深度为4。
3 ⼆叉树
3.1 定义
⼆叉树是n(n>=0)个结点的有限集合，该集合或者为空集(称为空⼆叉树)，或者由⼀个根结点和两棵互不相交的、分别称为根结点的左⼦树和右⼦树组成。
图3.1展⽰了⼀棵普通⼆叉树：
图3.1 ⼆叉树
3.2 ⼆叉树特点
由⼆叉树定义以及图⽰分析得出⼆叉树有以下特点：
1)每个结点最多有两颗⼦树，所以⼆叉树中不存在度⼤于2的结点。
2)左⼦树和右⼦树是有顺序的，次序不能任意颠倒。
3)即使树中某结点只有⼀棵⼦树，也要区分它是左⼦树还是右⼦树。
3.3 ⼆叉树性质
精氨酸酶
1)在⼆叉树的第i层上最多有2i-1 个节点 。(i>=1)
2)⼆叉树中如果深度为k，那么最多有2k-1个节点。(k>=1)
3)n0=n2+1 n0表⽰度数为0的节点数，n2表⽰度数为2的节点数。
4)在完全⼆叉树中，具有n个节点的完全⼆叉树的深度为[log2n]+1，其中[log2n]是向下取整。
5)若对含 n 个结点的完全⼆叉树从上到下且从左⾄右进⾏ 1 ⾄ n 的编号，则对完全⼆叉树中任意⼀个编号为 i 的结点有如下特性：
(1) 若 i=1，则该结点是⼆叉树的根，⽆双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点⽆左孩⼦， 否则，编号为 2i 的结点为其左孩⼦结点；
(3) 若 2i+1>n，则该结点⽆右孩⼦结点， 否则，编号为2i+1 的结点为其右孩⼦结点。
3.4 斜树
斜树：所有的结点都只有左⼦树的⼆叉树叫左斜树。所有结点都是只有右⼦树的⼆叉树叫右斜树。这两者统称为斜树。
图3.2 左斜树
图3.3 右斜树
3.5 满⼆叉树
满⼆叉树：在⼀棵⼆叉树中。如果所有分⽀结点都存在左⼦树和右⼦树，并且所有叶⼦都在同⼀层上，这样的⼆叉树称为满⼆叉树。
满⼆叉树的特点有：
1)叶⼦只能出现在最下⼀层。出现在其它层就不可能达成平衡。
2)⾮叶⼦结点的度⼀定是2。抗拉强度计算
3)在同样深度的⼆叉树中，满⼆叉树的结点个数最多，叶⼦数最多。
图3.4 满⼆叉树
3.6 完全⼆叉树
完全⼆叉树：对⼀颗具有n个结点的⼆叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满⼆叉树中编号为i的结点在⼆叉树中位置完全相同，则这棵⼆叉树称为完全⼆叉树。
图3.5展⽰⼀棵完全⼆叉树
图3.5 完全⼆叉树
特点：
1)叶⼦结点只能出现在最下层和次下层。
2)最下层的叶⼦结点集中在树的左部。
3)倒数第⼆层若存在叶⼦结点，⼀定在右部连续位置。
4)如果结点度为1，则该结点只有左孩⼦，即没有右⼦树。
5)同样结点数⽬的⼆叉树，完全⼆叉树深度最⼩。
注：满⼆叉树⼀定是完全⼆叉树，但反过来不⼀定成⽴。3.7 ⼆叉树的存储结构
⼆叉树的顺序存储结构就是使⽤⼀维数组存储⼆叉树中的结点，并且结点的存储位置，就是数组的下标索引。
图3.6
图3.6所⽰的⼀棵完全⼆叉树采⽤顺序存储⽅式，如图3.7表⽰：
图3.7 顺序存储
由图3.7可以看出，当⼆叉树为完全⼆叉树时，结点数刚好填满数组。
那么当⼆叉树不为完全⼆叉树时，采⽤顺序存储形式如何呢？例如：对于图3.8描述的⼆叉树：
图3.8.png
伊妹儿影院
其中浅⾊结点表⽰结点不存在。那么图3.8所⽰的⼆叉树的顺序存储结构如图3.9所⽰：
图3.9
其中，∧表⽰数组中此位置没有存储结点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。
那么对于图3.3所⽰的右斜树极端情况对应的顺序存储结构如图3.10所⽰：
图3.10
由图3.10可以看出，对于这种右斜树极端情况，采⽤顺序存储的⽅式是⼗分浪费空间的。因此，顺序存储⼀般适⽤于完全⼆叉树。
安南将军
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议