树的定义和基本术语

25
6.2 二叉树
满二叉树的特点： (1)每一层结点数都达到最大值。即对给 定深度，它是具有最多结点数的二叉树 (2)满二叉树中不存在度数为1的结点,且树 叶都在最下一层上
【例】一个深度为3的满二叉树。
26
6.2 二叉树
完全二叉树特点： （1） 满二叉树是完全二叉树，完全二叉树不一 定是满二叉树。 （2） 叶子结点只可能在层次最大的两层上出现； （3） 对任一结点，若其右分支下的子孙的最大 层次为l，则其左分支下的子孙的最大层次 为必 l 或 l＋1。
6.1 树的定义和基本术语
从逻辑结构看：
1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根 到该结点的路径； 5）树是一种分枝结构（除了一个称为根的 结点外）每个元素都有且仅有一个直接 前趋，有且仅有零个或多个直接后继。
6
6.1 树的定义和基本术语
A B E K L F , E, F, G, H, I, J，K，L，M} A是根，其余结点可以 划分为3个互不相交 的集合：T1, T2, T3
T1={B, E, F，K，L} , T2={C, G} , T3={D, H, I, J ，M}; 它们是A的子树。 对于 T1，B是根，其余结点可以划分为2个互不相 交的集合：T11={E，K，L}，T12={F}，T11,T12 7 是B 的子树。
3
第六章
树和二叉树
难点： • 二叉树的遍历及其有关应用
4
第六章
树和二叉树
• 树形结构是一类非常重要的非线性数据结构， 它是以分支关系定义的层次结构。它在现实世 界中广泛存在，在计算机领域中也有广泛应用 • 本章重点讨论二叉树的存储结构及其各种操作， 并研究树和森林与二叉树之间的转换关系。最 后给出一些应用实例

7.5 树的应用
➢判定树
在实际应用中，树可用于判定问题的描述和解决。
•设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有一枚且 仅有一枚硬币是伪造的，假硬币的重量与真硬币的重量不同，可能轻， 也可能重。现要求以天平为工具，用最少的比较次数挑选出假硬币， 并同时确定这枚硬币的重量比其它真硬币是轻还是重。
的第i棵子树。 ⑺Delete（t，x，i）在树t中删除结点x的第i棵子树。 ⑻Tranverse（t）是树的遍历操作，即按某种方式访问树t中的每个
结点，且使每个结点只被访问一次。
7.2.2 树的存储结构
顺序存储结构 链式存储结构 不管哪一种存储方式，都要求不但能存储结点本身的数据 信息，还要能够唯一的反映树中各结点之间的逻辑关系。 1.双亲表示法 2.孩子表示法 3.双亲孩子表示法 4.孩子兄弟表示法
21
将二叉树还原为树示意图
A BCD
EF
A
B
C
E
D
F
A
B
C
E
D
F
22
练习：将下图所示二叉树转化为树
1 2
4
5
3
6
2 4
1 53
6
23
7.3.2 森林转换为二叉树
由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树 的根视为兄弟，森林同样可以用二叉树表示。 森林转换为二叉树的方法如下：
⑴将森林中的每棵树转换成相应的二叉树。 ⑵第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树 的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来 后，此时所得到的二叉树就是由森林转换得到的二叉树。
相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是 一棵树。树T1，T2，…，Tm称为这个根结点的子树。 • 可以看出，在树的定义中用了递归概念，即用树来定义树。因此， 树结构的算法类同于二叉树结构的算法，也可以使用递归方法。

（2）表示形式
该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集： T1={B, E, F, K, L}，T2={C, G}，T3={D, H, I, J, M}; T1、T2和T3都是A的子树， 其本身也是一棵树。
层次
A 1
对比树型结构和线性结构的结构特点
线性结构
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 树型结构
一个后继)
(无后继)
(无后继)
(无前驱)
(一个前驱、
(无前驱)
(一个前驱、 多个后继)
B C D 2
E F G H I J 3
K L M 4
图6.1 一般的树
￡6.1.2 基本术语
结点：包含一个数据元素及若干指向其子树的分支。在树的 图形表示中为一个圆圈。
结点的度（Degree）：结点拥有的子树数。
叶子（或终端结点）（Leaf）：度为0的结点。即没有子树 的结点。
分支结点（或非终端结点）：度不为0的结点。
内部结点：除根结点之外的分支结点。
01
6.2 二叉树
02
6.3 遍历二叉树和线索二叉树
03
6.4 树和森林
04
6.6 哈夫曼树及其应用
6.1 树的定义和基本术语
6.1 树的定义和基本术语
（1）定义 树（Tree）：是n（n≥0）个结点的有限集。 定义一：（递归定义）： ①在任意一棵非空树中，有且仅有一个特定的称为根（root） 的结点； ②当n>1时，其余结点可分为m（m>0）个互不相交的有限集 T1, T2, … , Tm，其中每一个集合本身又是一棵树。并且 T1, T2, … , Tm，称为根的子树（SubTree）。 定义二：（形式定义） 任何一棵树是一个二元组Tree = (root, F)。 其中：root是数据元素，称做树的根结点；F是m（m≥0）棵树的森林， F＝（T1, T2, … , Tm），其中Ti = (ri, Fi)称做根root的第i棵子树；当m≠0 时，在树根和其子树森林之间存在下列关系： RF = {<root, ri> | i = 1, 2, … ,m; m > 0}

5.2.2 二叉树的性质
➢ 满二叉树和完全二叉树
满二叉树是指深度为h且节点数取得最大值2h-1的二叉树。 如果一棵深度为h的二叉树，除第h层外，其他每层的节点数 都达到最大，且最后一层的节点自左而右连续分布，这样的二 叉树称为完全二叉树。
5.2.2 二叉树的性质
5.2.2 二叉树的性质
性质6 对含有n个节点的完全二叉树自上而下、同一层从左往右 对节点编号0,1,2,…,n-1，则节点之间存在以下关系： （1）若i=0，则节点i是根节点，无双亲；若i>0，则其双亲节 点的编号为i/2-1； （2）若2×i +1≤n，则i的左孩子编号为2×i+1； （3）若2×i+2≤n，则i的右孩子编号为2×i+2； （4）若i>1且为偶数，则节点i是其双亲的右孩子，且有编号为 i-1的左兄弟； （5）若i<n-1且为奇数，则节点i是其双亲的左孩子，且有编号 为i+1的右兄弟。
5.3.3 二叉树的二叉链表类模板定义
//根据二叉树的先序遍历序列和中序遍历序列创建以r为根的二叉树
void CreateBinaryTree(BTNode<DataType> * &r, DataType pre[], DataType
in[], int preStart, int preEnd, int inStart, int inEnd); int Height(BTNode<DataType> *r); //求以r为根的二叉树高度 //求以r为根的二叉树中叶子节点数目
5.1.2 树的术语
（9）节点的层次：从根节点开始，根为第一层，根的孩子为 第二层，根的孩子的孩子为第三层，依次类推，树中任一节 点所在的层次是其双亲节点所在的层次数加1。 （10）堂兄弟：双亲在同一层的节点互为堂兄弟。