广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
树
§7.1 树的概念
【定义】 树（Tree）是n（n>0）个结点的有限集合T，它满足如下两个条件： (1) 有且仅有一个特定的称为根（Root）的结点；
(2) 其余的结点可分为m（m≥0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（Sub Tree）。
A ○
B ○C ○D ○【基本术语】k
E ○F ○G ○H ○I ○J 树的结点包含一个数据元素及若干指向其子树的分支。 ○结点拥有的子树数称为结点的度（degree）。
K ○L ○M ○如图7.1，A的度为3，C的度为1，F的度为0。
图7.1.1
度为0的结点称为叶子（leaf）或终端结点。例如K、L、F、G、M、I、J。 度不为0的结点称为分支结点或非终端结点。 除根结点外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值，如图7.1中树的度为3。 结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲（parent）。 如图7.1.1，B为A的子树的根，则B是A的孩子，而A则是B的双亲。 同一个双亲的孩子之间互称为兄弟（sibling），例如B、C、D互为兄弟。
将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如，M的祖先为A、D、H。
反之，结点的子树中的任一结点都称为该结点的子孙，如B的为E、F、K、L。 5. 结点的层次（level）是从根开始定义起，根为第一层，根的孩子为第二层。 若某结点在第x层，则其子树的根就在x+1层。 树中结点的最大层次称为树的高度或深度（depth）。如图7.1的树的深度为4。 6. 如果将树中的结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树,否则称为无序树。如图7.1.2。 A ○A ○ B ○C ○C ○B ○
图7.1.2 两棵不同的有序树
7. 森林（forest）是m（m≥0）棵互不相交的树的集合。
§7.2 二叉树
A §7.2.1 二叉树的定义 ○二叉树（binary tree）是一种树型结构，它的每个结点至多只
B ○C ○有二棵子树（即二叉树中不存在度大于2结点），并且，二叉树
D ○E ○F ○G 的子树有左右之分，其次序不能任意颠倒。 ○（如图7.2.1）
H ○I ○J ○37 / 17
图7.2.1
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
满二叉树和完全二叉树是两种特殊形态的二叉树。
k
满二叉树是指深度为k，且有2-1个结点的二叉树。 完全二叉树是指深度为k，有n个结点，当且仅当每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时。 1 1 1 ○○○ 2 ○3 2 ○3 2 ○3 ○○○
4 ○5 ○6 ○7 4 ○5 ○6 ○7 4 ○5 ○6 ○7 ○○○
○8 ○9 ○8 ○9 ○8 ○9 ○10 ○11 ○12 ○13 ○14 ○15 10 ○11 ○12 10 ○11 ○12 ○○
图7.2.2 满二叉树 图7.2.3 完全二叉树 图7.2.4 非完全二叉树
§7.2.2 二叉树的性质
性质1：在二叉树的第i层上至多有 ① 个结点（i≥1）。 性质2：深度为k的二叉树至多有 ② 个结点（k≥1）。
性质3：对任意一棵二叉树，如果度为2的结点数为n2，则其叶子结点数为 ③。 性质4：具有n个结点的完全二叉树的深度为?log2n??1
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任一结．．．．．点i （1≤i≤n），有：
① 如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点是i div 2 ② 如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子为2*i ③ 如果2*i+1>n，则结点i无右孩子，否则其右孩子为2*i+1 [参考答案及证明]：
i-1
① 2
证明：利用归纳法
i-10
当i=1时，只有一个根结点，显然，2=2=1 正确；
j-1
假设对所有的j，1≤j i-1 由假设，第i-1层上至多有2个结点，由于二叉树中的每个结点的度至多为2，故在第 i-2i-1 i层上的最大结点数为第i-1层上最大结点数的2倍，即2*2=2 k ② 2-1 证明：深度为K的二叉树的最大结点数为 ?(第i层上的最大结点数)??2i?1i?1kki?1?2k?1 ③ n2+1 证明：设叶子结点数为n0，度为1的结点数为n1，则该数结点的总数为： n ＝ n0 + n1 + n2 （1） 树中结点之间的连线称为分支。树中除根结点外，其余每个结点都有一个分支进入，设B为二叉树分支的总数，则有： B ＝ n –1 38 / 17 广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树 另一方面，这些分支是由度为1或2的结点射出的，所以： B ＝ n1 + 2n2 所以： n – 1 ＝ n1 + 2n2 （2） 由式（1）和（2）得： A B C D F G I M n0 + n1 + n2 – 1 ＝ n1 + 2n2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 即： n0 ＝ n2 + 1 ④ 证明：假设深度为K的完全二叉树的结点数为n，则根据性质2和完全二叉树定义有： 2k?1?1?n?2k?1 或 2k?1?n?2k 于是 k?1?log2n?k ∵ k是整数 ∴ k??log2n??1 ⑤ 证明略 §7.2.2 二叉树的存储结构 1．顺序存储结构 将二叉树的所有结点按一定的次序，存储到一片连续的存储单元中。这种结构，较适用于满二叉树或近似满二叉树。 A ○ B ○C 如图7.2.5中完全二叉树的存储结构如下： ○ A B C D E F G H I J A ○B ○C ○D ○F ○G ○I ○M ○K L M D ○E ○F ○G ○1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 H ○I ○J ○K ○L ○M ○图7.2.5 图7.2.6中的二叉树的存储结构如下： 可以看出，当二叉树较稀疏时，采用顺序存储将造成浪费。 [练习] 如果完全二叉树最多有n层，那么存储该树的数组最少设 图7.2.6 ________个单元； 某结点存储于S[i]，则存在双亲结点的条件： if ______________________ 其双亲结点位于S[ ____ ]，其左孩子结点位于S[ ____ ]； 2．链式存储结构 设计不同的结点结构可以构成不同形式的链式存储结构。 由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成， 39 / 17 广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树 则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域，如图7.2.7。 有时为了便于找到结点的双亲，则还可以在结点的结构中增加一个指向其双亲结点的指针域。用这两种结点结构所得的二叉树的存储结构分别称为二叉链表和三叉链表，如图7.2.8。 Lchild Data Rchild 图7.2.7 A A A ○ B B ○ B C ○D ○C C D D E ○F ○ G ○G G 图7.2.8 (b) 三叉链表 (a) 二叉链表 在具体应用中采用什么存储结构，除根据二叉树的形态之外，还应考虑需进行何种操作。如找结点的双亲，在三叉链表中容易实现，而在二叉链表中则需从根中指针出发巡查。 §7.3 遍历二叉树 遍历二叉树（traversing binary tree）是指按某种搜索路径巡访树中每个结点，使得每个结点均被访问一次，且仅访问一次。 根据二叉树的定义知，二叉树由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三个部分，则遍历了整棵二叉树。假设以D、L、R分别表示访问根结点、遍历左子树、遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。前三种分别称为先（根）序、中（根）序、后（根）序，后三种称为逆先序、逆中序、逆后序。通常只使用前三种。 先序遍历二叉树的操作定义为： （1）访问根结点； 【例7.3_1】 A ○（2）先序遍历左子树； B ○C （3）先序遍历右子树； ○中序遍历二叉树的操作定义为： D ○F ○G ○ （1）中序遍历左子树； I ○M （2）访问根结点； ○ （3）中序遍历右子树； 图7.3.1 后序遍历二叉树的操作定义为： DLR（先序）：ABDICFMG （1）后序遍历左子树； LDR（中序）：DIBAFMCG （2）后序遍历右子树； （3）访问根结点； LRD（后序）：IDBMFGCA 遍历算法的描述形式随存储结构的不同而不同，若定义二叉树的存储结构如下： TYPE Pointer = ^ node； 40 / 17 E F E F 广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树 node ＝ RECORD data ：char； lchild ，rchild ：pointer； END； 先序遍历二叉树的递归算法如下： procedure preorder（p ：pointer）； begin if p<>nil then begin write (p^.data)； preorder（p ^ . lchild）； preorder（p ^ . rchild）； end； end； 请完成中序遍历二叉树的递归算法： procedure inorder（p ：pointer）； begin end； 请完成后序遍历二叉树的递归算法： procedure postorder（p ：pointer）； begin end； 二叉树的三种遍历递归算法写得非常精妙，只要对它稍加修改（主要在process语句处），就可的各种不同功能、用途的算法。如建立二叉树、查找结点、求每个结点所处的层次、求二叉树的高度、结点个数、复制二叉树等。 §7.4 二叉树的建立 二叉树的建立可分先序、中序、后序三种方法。先序建立二叉树即输入结点数据的顺序按先序遍历所得的序列输入，输入“*”，表示该子树为空，如输入a b c * * d * * e * * ，得到的二叉树如图7.4.1。 a ○ b ○e ○中序、后序类推。 c ○d ○41 / 图17 7.4.1
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
