第6章 树和二叉树 本章主题：树、二叉树 教学目的：掌握树和二叉树的类型定义、运算及存储结构 教学重点：树的各种表示、各种存储方式和运算，

Presentation on theme: "第6章 树和二叉树 本章主题：树、二叉树 教学目的：掌握树和二叉树的类型定义、运算及存储结构 教学重点：树的各种表示、各种存储方式和运算，"— Presentation transcript:

1 第6章 树和二叉树 本章主题：树、二叉树 教学目的：掌握树和二叉树的类型定义、运算及存储结构 教学重点：树的各种表示、各种存储方式和运算，
第6章 树和二叉树 本章主题：树、二叉树 教学目的：掌握树和二叉树的类型定义、运算及存储结构 教学重点：树的各种表示、各种存储方式和运算， 二叉树的概念及其运算和应用 教学难点：二叉树的非递归运算及应用 主要内容：树 二叉树 树、森林与二叉树的转换 树的应用 2019/2/25

2 本章学习导读 本章主要介绍树的基本概念，树的存储结构，树和二叉树的遍历等一些常用算法。通过本章学习，读者应该：
1) 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 2) 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 3) 熟练掌握二叉树和树的各种存储结构及建立的算法。 4) 学会编写实现树的各种操作的算法。 5)了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。 2019/2/25

3 非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等)
数据结构:线性结构和非线性结构 线性结构(线性表, 栈,队列等) 非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等) 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 2019/2/25

4 6.1 树的逻辑结构和存储结构 树型结构实例 1．家族树 图6-1 家族树 2019/2/25

5 2．书的目录结构 图6-2 书的目录 2019/2/25

6 1．树的定义 6.1 树的逻辑结构和存储结构 6.1 .2 树的定义
6.1 树的逻辑结构和存储结构 树的定义 1．树的定义 树(Tree)是n (n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件： (1) 有且仅有一个结点没有前驱，称该结点为根结点(Root)； (2) 除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl ，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。 树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。 2019/2/25

7 返回 图6-3 树的示例 图6-3 (a)是一棵只有一个根结点的树； 图6-3 (b)是一棵有12个结点的树，即T={A，B，C，…，K，L }。A是棵根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的 。 2019/2/25

8 6 .有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
2．树的基本术语 树的结点包含一个数据元素及若干指向其子树的分支。 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点; 3. 树的度:树中所有结点的度的最大值 Max(D(I)) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度 5.森林:是m(m>=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6 .有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。 2019/2/25

9 7.森林: 是m（m≥0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系描述，定义如下：
8.孩子、双亲: 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 9.子孙: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。 10.祖先: 从根结点到该结点路径上的所有结点。 11.兄弟: 同一个双亲的孩子之间互为兄弟。 12.堂兄弟: 双亲在同一层的结点互为堂兄弟。 2019/2/25

10 6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。
3. 树的基本运算 树的基本运算主要有： ⒈ 初始化操作INITIATE(T)：创建一棵空树。 ⒉ 求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。 ⒊ 求双亲函数PARENT(T,x)：在树T中求x的双亲。 ⒋ 求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。 ⒌ 建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。 6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。 2019/2/25

11 6.1.3 树的表示 树的逻辑表示方法有多种，常见的有 ： 1． 树形图表示法 2． 嵌套集合表示法（文氏图表示法） 3． 凹入表示法
4． 广义表表示法 2019/2/25

12 6.1.3 树的存储结构 和线性表一样，树可以用顺序和链式两种存储结构。
树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。 1．双亲存储表示法 一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域： 　　data域-----存放结点的信息；　　 　　parent域-----存放该结点双亲结点的位置 特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。 2019/2/25

13 存储结构描述为： #define MaxTreeSize 100 //定义数组空间的大小
  typedef char DataType； //定义数据类型   typedef struct { DataType data； //结点数据 int parent； //双亲指针，指示结点的双亲在数组中的位置 } PTreeNode； typedef struct {  PTreeNode nodes[MaxTreeSize]; int n； //结点总数 } PTree； PTree T； //T是双亲链表 2019/2/25

14 这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。
2．孩子链表表示法 这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。 　 n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。 　 n个孩子链表的头指针用一个向量表示。 头指针向量　孩子链表 特点：与双亲相反，求孩子易，求双亲难。 图6-6 树的孩子链表结构 2019/2/25

15 存储结构描述为： typedef struct CTNode { int child; //孩子链表结点
　struct CTNode *next; }*ChildPtr; typedef struct //孩子链表头结点 { ElemType data; 　　　 //结点的数据元素 ChildPtr firstchild; 　　 //孩子链表头指针 }CTBox; typedef struct { CTBox nodes[MaxTreeSize]; int n, r,　　　　　　　 //数的结点数和根结点的位置 } CTree; 2019/2/25

16 typedef struct Cnode //DataType和MaxTreeSize由用户定义 { //孩子链表结点
孩子链表表示法的类型说明 typedef struct Cnode //DataType和MaxTreeSize由用户定义 { //孩子链表结点   int child; //孩子结点在数组中对应的下标   struct CNode *next; } Cnode; typedef struct //孩子链表头结点 {  DataType data; //存放树中结点数据 CNode *firstchild; //孩子链表的头指针 } PTNode; typedef struct { PTNode nodes[MaxTreeSize]; Int n,root; //树的结点数和根结点的位置 } Ctree; Ctree T; //T的孩子链表表示 2019/2/25

17 孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。
3．孩子兄弟链表表示法 孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。 由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。 特点：双亲只管长子 长子连接兄弟 图6-7 树的孩子-兄弟存储结构 2019/2/25

18 struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;
树的孩子兄弟链表的存储结构描述为： typedef struct CSNode { ElemType data; 　struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; 孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作。但是，孩子兄弟存储结构的缺点也是查找当前结点的双亲结点比较麻烦，需要从树根结点开始逐个结点比较查找。 2019/2/25

19 所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式 。
6.1.5 树和森林的遍历 1．树的遍历 所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式 。 树的遍历可以按深度优先遍历，也可以按照广度优先（按层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。 (1) 前序遍历的递归定义：  若树T非空，则： 访问根结点R； 按照从左到右的顺序依次前序遍历根结点R的各子树T1，T2，…，Tk。 2019/2/25

20 按照从左到右的顺序依次后序遍历根T的各子树Tl，T2，…，Tk； 访问根结点R。 (3) 广度优先（按层）遍历
(2) 后序遍历的递归定义： 若树T非空，则： 按照从左到右的顺序依次后序遍历根T的各子树Tl，T2，…，Tk； 访问根结点R。 (3) 广度优先（按层）遍历 广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点），再从左至右访问第二层结点，依次按层访问……，直到树中结点全部被访问为止。对图6-6 (a)中的树进行按层次遍历得到树的广度优先遍历序列为：ABCDEFG。 说明： ① 前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（6.2节将介绍二叉树） ② 后序遍历树恰好等价于中序遍历该树所对应的二叉树。 2019/2/25

21 void Preorder(Btree *root) //先根遍历k叉树 { if (root!=NULL)
树的先序遍历算法描述如下： void Preorder(Btree *root) //先根遍历k叉树 { if (root!=NULL) {printf(“%c\n”,root->data); //访问根结点 　　for(i=0;i<k;i++) preorder(root->t[i]); //递归前序遍历每一个子结点 　} } 2019/2/25

22 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点；
2．森林的遍历 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点； 前序遍历第一棵树中根结点的各子树所构成的森林 前序遍历去掉第一棵树外其它树构成的森林。 (2) 后序遍历森林 若森林非空，则: 后序遍历森林中第一棵树中根结点的各子树所构成的森林； 访问第一棵树的根结点； 后序遍历去掉第一棵树外其它树构成的森林。 当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。 2019/2/25

23 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点；
2．森林的遍历 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点； 前序遍历第一棵树中根结点的各子树所构成的森林 前序遍历去掉第一棵树外其它树构成的森林。 (2) 后序遍历森林 若森林非空，则: 后序遍历森林中第一棵树中根结点的各子树所构成的森林； 访问第一棵树的根结点； 后序遍历去掉第一棵树外其它树构成的森林。 2019/2/25

24 图6-8 森林和对应的二叉树 2019/2/25

25 6.2 二叉树 6.2.1二叉树的定义与性质 二叉树(Binary Tree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。 1．二叉树的递归定义 二叉树(BinaryTree)是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件： (1) 有且仅有一个根结点； (2) 其余的结点分成两棵互不相交的左子树和右子树。 2019/2/25

26 (a) 空二叉树 (b) 只有根结点的二叉树 (c) 右子树为空的二叉树
二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。 二叉树有5种基本形态： (a) 空二叉树 (b) 只有根结点的二叉树 (c) 右子树为空的二叉树 (d) 左子树为空的二叉树 (e) 左右子树均不为空的二叉树 图6-9 二叉树的五种基本形态 2019/2/25

27 两种特殊形态的二叉树：满二叉树和完全二叉树。 (1) 满二叉树(FullBinaryTree) 深度为k，且有2k-1个结点的二叉树。
特点：（1）每一层上结点数都达到最大 （2）度为1的结点n1=0，树叶都在最下一层上。 结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。 1 2 3 7 6 5 4 K=3 n=23-1=7 满二叉树 2019/2/25

28 深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。
(2) 完全二叉树(Complete BinaryTree)  深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。 4 5 2 1 3 图6-11 完全二叉树 完全二叉树的特点： （1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。 （2）完全二叉树结点数n满足2k-1-1＜n≤2k-1 （3）满二叉树一定是完全二叉树，反之不成立。 2019/2/25

29 LH2=0 RH2=1 1 3 2 4 6 5 3 2 4 1 LH2-RH2=0-1=-1 LH1=3 RH1=1 LH1 -RH1=2
非完全二叉树 非完全二叉树 2019/2/25

30 性质1 在二叉树的第i层上至多有2i-1 个结点(i≥1)。 性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
2．二叉树的性质 性质1 在二叉树的第i层上至多有2i-1 个结点(i≥1)。 性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。 （深度一定，二叉树的最大结点数也确定） 性质3 二叉树中,终端结点数n0与度为2的结点数n2有如下关系: n0=n2+1 性质4 结点数为n的完全二叉树，其深度为 log2n + l 性质5 在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有： ⑴ i=1时，结点i是树的根；否则，结点i的双亲为结点  i/2  (i>1) 。 ⑵ 2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。 ⑶ 2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。 2019/2/25

31 用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。
6.2.2 二叉树的存储结构 同线性表一样，二叉树的存储结构也有顺序和链表两种结构。 1．顺序存储结构 用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。 A B C D E F G 完全二叉树 D C G F E B A bt [3] 的双亲为  3/2  =1， 即在bt[1]中； 其左孩子在bt[2i]=bt[6]中； 其右孩子在bt[2i+1]=bt[7]中。 2019/2/25

32 一般二叉树也按完全二叉树形式存储，无结点处用0表示。
D 二叉树 C G F E B A A B C D E F G 这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的大量浪费。 2019/2/25

33 例如：深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。
⒉ 链式存储结构 （二叉链表） 设计不同的结点结构，可以构成不同的链式存储结构。常用的有： 二叉链表 三叉链表 线索链表 用空链域存放指向前驱或后继的线索 2019/2/25

34 由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：
其中左链域lchild为指向左孩子的指针，右链域rchild为指向右孩子的指针，数据域data表示结点的值。若某结点没有左孩子或右孩子，其相应的链域为空指针。 对应的结构类型定义如下： typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTree,*tree; 其中，tree是指向根结点的指针。 2019/2/25

35 lchild data rchild 二叉树 二叉链表的结点结构 说明：
E B A 二叉链表 A C B D E ∧ 说明： ● 一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。 ● 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。 2019/2/25

36 lchild data parent rchild
3．带双亲指针的二叉链表 由于经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。就是三叉链表。 三叉链表的结点结构 lchild data parent rchild 三叉链表 D 二叉树 C E B A A ∧ B ∧ C ∧ D ∧ ∧ E ∧ ∧ 性质6 含有n个结点的二叉链表中，有n+1个空链域。 二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。 2019/2/25

37 6.2.3 二叉树的基本运算及实现 1．二叉树的基本运算 （1）Inittree (&T) 功能：初始化操作 (建立一棵空的二叉树)。
二叉树的基本运算及实现 1．二叉树的基本运算 （1）Inittree (&T) 功能：初始化操作 (建立一棵空的二叉树)。 （2）Root(T) 功能：求二叉树的根。 （3）Parent(T,x) 功能：求二叉树T中值为x的结点的双亲。 （4）Lchild(T,x) 功能：求结点的左孩子。 （5）Rchild(T,x) 功能：求结点的右孩子。 （6）Traverse(T) 功能：遍历或访问二叉树T。 （7）creatree(&T) 功能：创建二叉树T 2019/2/25

38 2．二叉树部分运算的算法描述 (1) 创建二叉树creatree(&root, str)： 功能：创建二叉树T。算法描述如下：
void creatree(BTree **b, char *str) { BTree *stack[MAXSIZE], p=NULL; int top=-1,k,j=0; char ch; *b=NULL; ch=str[j]; while(ch!=’\0’) { switch(ch) { case ’(’：top++; stack[top]=p;k=1,break; //为左结点 case ’)’：top--;break; case ’,’：k=2;break; //为右结点 default：p=(BTree *)malloc(sizeof(BTree)); p->data=ch;p->lchild=p->rchild=NULL; 2019/2/25

39 p->data=ch;p->lchild=p->rchild=NULL; if(*b==NULL) //为根结点
*b=p; else { switch(k) { case 1：stack[top]->lchild=p;break; case 2：stack[top]->rchild=p;break; } j++; ch=str[j]; 2019/2/25

40 (2) 查找给定的结点find (root，x) (3) 找左孩子结点lchild(p)或右孩子结点rchild(p)
(4) 输出二叉树disptree(root) 2019/2/25

41 6.3 遍历二叉树和线索二叉树 6.3.1遍历二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。 遍历二叉树：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。 遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 2019/2/25

42 访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。 遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR——先（根）序遍历， LDR——中（根）序遍历， LRD——后（根）序遍历。 1．遍历方案 LDR 中序遍历； LRD 后序遍历； DLR 先序遍历 2019/2/25

43 void Inorder (BiTree bt){ //bt为根结点指针 if( bt){//根非空
2）后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根结点 1）中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树 2）访问根结点 3）中序遍历右子树 算法描述: void Inorder (BiTree bt){ //bt为根结点指针 if( bt){//根非空 Inorder (bt->lchild) ; visit (bt->data)； Inorder (bt->rchild) ; } 算法描述: void Postorder (BiTree bt){ //bt为根结点指针 if( bt){ Postorder (bt->lchild) ; Postorder (bt->rchild) ; visit (bt ->data)； } 2019/2/25

44 例：表达式 a+b ×(c-d)-e/f + 算法描述: 3）先序遍历二叉树 void Preorder (BiTree bt){
if( bt){//根非空 visit (bt->data)； Preorder (bt->lchild) ; Preorder (bt->rchild) ; } 3）先序遍历二叉树 算法思想: 若二叉树非空，则： 1）访问根结点 2）先序遍历左子树 3）先序遍历右子树 例：表达式　a+b ×(c-d)-e/f a c d e f － b × ＋ + 遍历结果: 中序: a+b × c - d - e / f 后序: abcd - × + ef / - 先序: - +a × b - cd / ef 2019/2/25

45 2．遍历算法 （1）先序遍历的递归算法如下（假定结点的元素值为字符型）： #include "stdio.h"
typedef char ElemType; 　typedef struct node //定义链表结构 { ElemType data; //定义结点值 struct node *lchild; //定义左子结点指针 struct node *rchild; //定义右子结点指针 }BTree; preorder(BTree *root) //前序遍历 { if(root!= NULL) //如果不是空结点 　{ printf(“%c\n”,root->data); //输出当前结点值 　　preorder(root->lchild); //递归前序遍历左子结点 　　preorder(root->rchild); //递归前序遍历右子结点 　} 　return; //结束 2019/2/25

46 （2）中序遍历的递归算法如下（假定结点的元素值为字符型）：
void inorder(BTree *root) //中序遍历 { if(root!=NULL) //如果不是空结点 　 { inorder(root->lchild); //递归中序遍历左子结点 printf(“%c\n”,root->data); //输出当前结点值 inorder(root->rchild); //递归中序遍历右子结点 } (3) 后序遍历的算法实现 　void postorder(BTree *root) //后序遍历 { if(root!=NULL) //如果不是空结点 { postorder(root->lchild); //递归后序遍历左子结点 postorder(root->rchild); //递归后序遍历右子结点 printf(“%c\n”,root->data); //输出当前结点值 2019/2/25

47 中序遍历非递归算法,s为存储二叉树结点指针栈：
void inorder(BiTree bt) { InitStack(s)； Push(s,bt)； while(!StackEmpty(s)) { while(GetTop(s)){ Push(s,GetTop(s)->lchild)； p=POP(s)； if(!StackEmpty(s)) { visit(GetTop(s)->data)； p=Pop(s)； Push(s, p->rchild);}}} } 操作过程： 根结点先进栈，左结点紧跟根后面进栈,右结点在根出栈后入栈； 每个结点都要进一次和出一次栈，并且总是访问栈顶元素， 因此，算法正确，时间复杂度为 O(n)。 2019/2/25

48 通过上述三种不同的遍历方式得到三种不同的线性序列，它们的共同的特点是有且仅有一个开始结点和一个终端结点，其余各结点都有且仅有一个前驱结点和一个后继结点。
从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递归无关的语句printf()，则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为n，则空间复杂度也为O(n)。 2019/2/25

49 3．二叉链表的构造 (1) 基本思想 利用遍历可以实现对结点的一些操作，如求结点的双亲，求结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链表。先序序列中必须加入虚结点以示空指针的位置。 (2) 构造算法（举例说明） 2019/2/25

50 【例6-4】建立图6-13 (a)所示二叉树，其输入的先序序列是：ABD∮G∮∮CE∮∮F∮∮。
【解】假设虚结点输入时以空格字符表示，相应的构造算法为： void CreateBinTree (BTree **T) { //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身   char ch;   if((ch=getchar())==“ ”) *T=NULL; //读入空格，将相应指针置空   else //读入非空格   { *T=(BTree *)malloc(sizeof(BTree)); //生成结点     (*T)->data=ch；     CreateBinTree(&(*T)->lchild)； //构造左子树      CreateBinTree(&(*T)->rchild)； //构造右子树    } } 调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。 2019/2/25

51 6.3.2 线索二叉树 ⒈ 问题的提出：通过遍历二叉树可得到结点的一个线性序列，在线性序列中，很容易求得某个结点的直接前驱和后继。但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，如何保存遍历二叉树后动态得到的线性序列，以便快速找到某个结点的直接前驱和后继？ 2. 分析： n个结点有n-1个前驱和n-1个后继； 一共有2n个链域，其中：n+1个空链域，n-1个指针域； 因此, 可以用空链域来存放结点的前驱和后继。 线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。 2019/2/25

52 在二叉链表中增加 ltag 和 rtag 两个标志域
3. 线索二叉树： 有效利用二叉链表中空的存储空间，指定原有的孩子指针为空的域来存放指向前驱和后继的信息，这样的指针被称为“线索”。加线索的过程称为线索化，由此得到的二叉树称作线索二叉树。 ⑴ 结点结构 在二叉链表中增加 ltag 和 rtag 两个标志域 若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）； 若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）； 2019/2/25

53 中序、先序和后序线索二叉树中所有实线均相同，所有结点的标志位取值也完全相同，只是当标志位取1时，不同的线索二叉树将用不同的虚线表示。
按中序遍历得到的线索二叉树称为中序线索二叉树； 按先序遍历得到的线索二叉树称为先序线索二叉树； 按后序遍历得到的线索二叉树称为后序线索二叉树； （2）整体结构 增设一个头结点，令其lchild指向二叉树的根结点，ltag=0、rtag=1； 并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继； 最后用头指针指示该头结点。 2019/2/25

54 图6-14 线索二叉树 2019/2/25

55 线索二叉树的存储结点可描述如下： struct node { ElemenType data; //数据域 int ltag; //左标志域
　int rtag; //右标志域 　struct node *lchild; //左指针域 　struct node *rchild; //右指针域 }BTree; 同样，线索二叉树根据遍历规则的不同，可分为前序线索二叉树、中序线索二叉树、后序线索二叉树。 2019/2/25

56 建立中序线索二叉树的算法 ： void thread(BTree **current,BTree **pre)
{ if(*current!=NULL) { thread(&(*current)->lchild, pre); //左子树线索化 if((*current)->lchild==NULL){ (*current)->lchild=*pre; //建立当前结点的前驱线索 (*current)->ltag=1; } if((*pre)->rchild==NULL) { (*pre)->rchild=*current; //建立前驱结点的后继线索 (*pre)->rtag=1; *pre=*current; thread(&(*current)->rchild,pre); //右子树线索化 2019/2/25

57 BTree *creathread(BTree *b) //中序线索化二叉树 { BTree *pre,*root,*current;
root=(BTree *)malloc(sizeof(BTree)); //创建根结点 root->data=’r’; //值’r’表示根结点 root->ltag=1;root->rtag=0; if(b==NULL); //空二叉树 { root->lchild=root; root->rchild=root; } else 2019/2/25

58 { current=root->lchild=b; root->ltag=0;
else { current=root->lchild=b; root->ltag=0; pre=root; //pre是前驱结点，供加线索用 thread(&current,&pre); //中序遍历线索化二叉树 pre->rchild=root; //最后处理，加入指向根结点的线索 pre->rtag=1; root->rchild=pre; //根结点右线索化 root->rtag=1; } return root； 2019/2/25

59 6.4 树、森林与二叉树的转换 １．树与二叉树的对应关系
6.4 树、森林与二叉树的转换 １．树与二叉树的对应关系 　树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。 2．树转换成二叉树 将一棵树转化为等价的二叉树方法如下： (1) 在树中各兄弟（堂兄弟除外）之间加一根连线。 (2) 对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45°。 特点：根无右子树　 2019/2/25

60 图6-15树转换成二叉树 图6-16 森林和对应的二叉树 2019/2/25

61 树和森林都可转换成二叉树，但树转换成二叉树后根结点无右分支，而森林转换后的二叉树，其根结点有右分支。
3．森林转换成二叉树 树和森林都可转换成二叉树，但树转换成二叉树后根结点无右分支，而森林转换后的二叉树，其根结点有右分支。 将森林转化为二叉树方法如下： (1) 将森林中的每一棵树转换成等价的二叉树。 (2) 保留第一棵二叉树，自第二棵二叉树始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树依此相连后，所得到的二叉树就是由森林转化成的二叉树。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45°。 转换过程如图图6-16 。 2019/2/25

62 将当前根结点和其左子树作为森林的一棵树,并将其右子树作为 森林的其他子树；
4．二叉树转换成森林 将当前根结点和其左子树作为森林的一棵树,并将其右子树作为 森林的其他子树； 重复上面直到某结点的右子树为空。 T3 J I H G J I H G F E B C D A T1 B C D A F E T2 2019/2/25

63 6.5 二叉树的应用 树型结构具有广泛的应用领域，常见的有：二叉排序树、哈夫曼树和判定树等。 6.5.1 二叉排序树
二叉排序树T是一棵二叉树，或者为空，或者满足下面条件： （1）若T的根结点的左子树非空，则左子树中所有结点的值均小于根结点值； （2）若T的根结点的右子树非空，则右子树中所有结点的值均大于根结点值； （3）T的左右子树也分别为二叉排序树。 二叉排序树又称二叉查找树，是一种动态树表。它把查找和插入操作集为一体，或查找成功或插入。具体的查找和插入方法将在第9章介绍。 2019/2/25

64 哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。
路径长度和最优二叉树（哈夫曼树） 哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。 在许多应用中，常常赋给树中结点一个有某种意义的实数，称此实数为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(WPL)。 树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为： 两结点间的路径：从一结点到另一结点所经过的结点序列 路径长度：路径上的分支树 树的路径长度：从根到每一结点的路径长度之和 2019/2/25

65 例 1 3 2 4 6 7 5 ⑴-⑵-⑸为结点1到5之间的路径，其路径长度为2，
树的路径长度=l12 +l13+ l14 +l15+ l16 +l17 = =10 2 7 6 3 4 1 5 例 完全二叉树是路径长度最短的二叉树。 考虑带权时：设树中有m个叶结点，每个叶结点带一个权值wｉ且根到叶结点i的路径长度为 Li (ｉ=1，2，．． m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。 　　　　　　 Ｍ　　　 即：ＷＰＬ＝∑ ＷｋＬｋ 　　　　　　Ｋ＝１　 2019/2/25

66 例如，给定4个叶结点，设权值分别为1，3，5，7，据此可以构造出形状不同的4棵二叉树，如图6-19所示。它们的带权路径长度分别为：
(a) WPL=1×2+3×2+5×2+7×2=32 (b) WPL=1×2+3×3+5×3+7×l=33 (c) WPL=7×3+5×3+3×2+1×1=43 (d) WPL=1×3+3×3+5×2+7×1=29 WPL最小的二叉树是最优二叉树(Huffman 树)，图6-19(d)所示。 第0层 第1层 第2层 第3层 图6-19 由4个结点构成的不同的带权二叉树 2019/2/25

67 2．二叉树的带权路径长度(Weighted Path Length of Tree，简记为WPL)
1．二叉树的路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路经上的分支数目称为路径长度。树的路径长度是指从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。 2．二叉树的带权路径长度(Weighted Path Length of Tree，简记为WPL) 结点的带权路径长度定义为结点到树根之间的路径长度与该结点上所带权值的乘积。 树的带权路径长度(Weighted Path Length of Tree)是树中所有叶结点的带权路径长度之和，通常记为： 2019/2/25

68 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。
3．最优二叉树或哈夫曼树 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。 结论: ① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。 ② 在最优二叉树中，权值越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，但WPL最小。 2019/2/25

69 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。
3．最优二叉树或哈夫曼树 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。 结论: ① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。 ② 在最优二叉树中，权值越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，但WPL最小。 2019/2/25

70 6.5.3 构造最优二叉树： 1．哈夫曼算法 哈夫曼算法的基本思想是：
(1) 以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点； (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi） (3) 从F中删除这两棵二叉树，同时将新二叉树加入到F中; (4) 重复(2)．(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman 树。 2019/2/25

71 例如，给定权值集合{5，15，40，30，10}构造哈夫曼树的过程如图6-21所示，其中最优的带权路径长度为：WTL＝(5＋10)×4＋15×3＋30×2＋40＝205。由图6-21可以看出，哈夫曼树的结点的度数为0或2，没有度为1的结点。 图6-21 哈夫曼树构造过程 2019/2/25

72 用大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为：
2．哈夫曼树的存储结构及哈夫曼算法的实现 (1) 哈夫曼树的存储结构 用大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为： #define n //叶结点数目 #define m 2*n //树中结点总数 typedef struct { float weight; //权值，设权值均大于零 int lchild,rchild,parent; //左右孩子及双亲指针 } HTNode;   typedef HTNode HuffmanTree[m]; //哈夫曼树是一维数组 因为C语言数组的下界为0，用-1表示空指针。树中结点的lchild、rchild和parent不等于-1时，分别表示该结点的左、右孩子和双亲结点在数组中的下标。 设置parent域有两个作用：一是使查找某结点的双亲变得简单；二是可通过判定parent的值是否为-1来区分根与非根结点。 2019/2/25

73 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：
(2) 哈夫曼算法的简要描述 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)： ①初始化 将T[0…m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。 ②输入 读入n个叶子的权值存于数组的前n个分量(即T[0…n-1])中。它们是初始森林中n个孤立的根结点上的权值。 ③合并 对森林中的树共进行n-1次合并，所产生的新结点依次放入数组T的第i个分量中(n≤i≤m-1)。每次合并分两步： 2019/2/25

74 2) 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。
1) 在当前森林T[0…i-1]的所有结点中，选取权值最小和次小的两个根结点T [p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。 2) 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。 具体操作： 将T[p1]和T[p2]的parent置为i； 将T[i]的lchild和rchild分别置为p1和p2； 新结点T[i]的权值置为T[p1]和T[p2]的权值之和。 合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。 2019/2/25

75 (3) 哈夫曼树的构造 （数组法） void CreateHuffmanTree(HuffmanTree T)
{ int i,p1,p2; //构造哈夫曼树，T[m-1]为其根结点 InitHuffmanTree(T); //T初始化 InputWeight(T); //输入叶子权值至T[0．．n-1]的weight域 for(i=n;i<m;i++) { SelectMin(T,i-1,&p1,&p2);//共进行n-1次合并，新结点依次存于T[i]中 //在T[0…i-1]中选择两个权最小的根结点，其序号分别为p1和p2 T[p1].parent=T[p2].parent=i; T[i].1child=p1; //最小权的根结点是新结点的左孩子 T[i].rchild=p2; //次小权的根结点是新结点的右孩子 T[i].weight=T[p1].weight+T[p2].weight; } 2019/2/25

76 【例6-7】用链表构造哈夫曼树 【解】哈夫曼树的链表结构算法描述如下： #include “stdio.h”
#include “stdlib.h” #include “alloc.h” #define m 100 struct ptree //定义二叉树结点类型 { int w; //定义结点权值 struct ptree *lchild; //定义左子结点指针 struct ptree *rchild; //定义右子结点指针 }; struct pforest //定义链表结点类型 { struct pforest *link; struct ptree *root; int WPL=0; //初始化WTL为0 struct ptree *hafm(); void travel(); struct pforest *inforest(); 2019/2/25

77 printf("please input the sum of node\n"); //提示输入结点数
main( ) { struct ptree *head; int n,i,w[m]; printf("please input the sum of node\n"); //提示输入结点数 scanf("%d",&n); //输入结点数 printf ("please input weight of every node\n"); //提示输入每个结点的权值 for(i=1;i<=n;i++) scanf("%d",&w[i]); //输入每个结点权值 head=hafm(w,n); travel(head,0); printf("The length of the best path is WPL=%d", WPL); //输出最佳路径权值之和 } 2019/2/25

78 void travel(struct ptree *head,int n) //为验证harfm算法的正确性进行的遍历
{ struct ptree *p; p=head; if(p!=NULL) { if((p->lchild)==NULL && (p->rchild)==NULL) //如果是叶子结点 { printf("%d",p->w); printf("the hops of the node is: %d\n",n); WPL=WPL+n*(p->w); //计算权值 } travel(p->lchild,n+1); travel(p->rchild,n+1); 2019/2/25

79 struct ptree *hafm(int n, int w[m]) { struct pforest *p1,*p2,*f;
struct ptree *ti,*t,*t1,*t2; int i; f=(struct pfores *)malloc(sizeof(struct pforest)); f->link=NULL; for(i=1;i<=n;i++) //产生n棵只有根结点的二叉树 { ti=(struct ptree*)malloc(sizeof(struct ptree)); //开辟新的结点空间 ti->w=w[i]; //给结点赋权值 ti->lchild=NULL; ti->rchild=NULL; f=inforest (f, ti); } while(((f->link)->link)!=NULL)//至少有二棵二叉树 { p1=f->link; p2=p1->link; f->link=p2->link; //取出前两棵树 2019/2/25

80 f->link=p2->link; //取出前两棵树 t1=p1->root; t2=p2->root;
free(p1); //释放p1 free(p2); //释放p2 t=(struct ptree *)malloc(sizeof(struct ptree)); //开辟新的结点空间 t->w=t1->w+t2->w; //权相加 t->lchild=t1;　 t->rchild=t2; //产生新二叉树 f=inforest(f,t); } p1=f->link; t=p1->root; free(f); return(t); //返回t 2019/2/25

81 struct pforest *inforest(struct pforest *f, sturct ptree *t)
{ struct pforest *p, *q, *r; struct ptree *ti; r=(struct pforest *)malloc(sizeof(struct pforest)); //开辟新的结点空间 r->root=t; q=f; p=f->link; while (p!=NULL) //寻找插入位置 { ti=p->root; if (t->w>ti->w) //如果t的权值大于ti的权值 { q=p; p=p->link; //p向后寻找 } else p=NULL; //强迫退出循环 r->link=q->link; q->link=r; //r接在q的后面 return(f); //返回f 2019/2/25

82 通讯中常需要将文字转换成二进制字符串电文进行传送。 文字 电文，称为编码。
3． 哈夫曼编码 哈夫曼树的应用很广，哈夫曼编码就是哈夫曼树在电讯通信中的应用之一。 通讯中常需要将文字转换成二进制字符串电文进行传送。 文字 电文，称为编码。 收到电文后要将电文转换成原来的文字，电文 文字，称为译码。 在电报通信中，电文是以二进制的0，1序列传送的。在发送端需要将电文中的字符转换成0，1序列（编码）发送，在接收端又需要把接收到的0，1序列还原成相应的字符序列（译码）。 2019/2/25

83 最简单的二进制编码方式是等长编码。假定需传送的电文是CDABB，在电文中仅使用A，B，C，D 4种字符，则只需用两个字符串便可分辨。可依次对其编码为：00，01，10，11。上述需发送的的电文是“ ”。译码员可按两位一组进行译码，恢复原来的电文。 例如：需将文字“ABACCDA”转换成电文。文之中 有四种字符，用2位二进制便可分辨。 A B C D 编码方案1： 则上述文字的电文为： 共14位。 译码时，只需每2位一译即可。 特点：等长等频率编码，译码容易，但电文不一定最短。 2019/2/25

84 A B C D 编码方案2： 采用不等长编码，让出现次数多的字符用短码。 则上述文字的电文为： 共9位。 但无法译码，它既可译为BBCCACA，也可译为AAAACCDA等。 A B C D 编码方案3： 采用不等长编码，让出现次数多的字符用短码，且任一编码不能是另一编码的前缀。 则上述文字的电文为： 共13位。 2019/2/25

85 要得到最短的电文，即使得∑ Wi Li最小。
设有n种字符，每种字符出现的次数为Wi , 其编码长度为Li (i=1,2,．．．n)， 则整个电文总长度为∑ Wi Li ， 要得到最短的电文，即使得∑ Wi Li最小。 也就是以字符出现的次数为权值，构造一棵 Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。 用构造Huffman树编出来的码，称为Huffman编码。 2019/2/25

86 为了获得传送电文的最短长度，可将字符出现的次数（频率）作为权值赋予该结点，构造一棵WPL最小的哈夫曼树，由此得到的二进制前缀编码就是最优前缀编码，也称哈夫曼编码。可以验证，用这样的编码传送电文可使总长最短。 图6-22 哈夫曼编码 图6-23 最优编码示例 2019/2/25

87 例如，设一文本的字符序列是：DATA TRERTER ARE AREA ART，此文本的字符集为{A，D，T，R，E}，各字符出现的次数为{6，1，4，6，4}。以此为权值，构造一棵最优二叉树（哈夫曼树），如图6-23所示。 约定从各非终端结点发出的左分支表示0，右分支表示1。于是，由根结点到叶结点的路径上所有0和1组成的序列，就是该叶结点所表字符的哈夫曼编码。如下所示： 字符 A D T R E 编码 10 010 011 11 00 由此可见，根据权值构造哈夫曼树得出的哈夫曼编码，使字符出现次数（频率）与码长呈反比关系，如此得到的电文总码长最短；同时，又避免了每一个字符编码是另一个字符编码的前缀，保证了译码的唯一性。 2019/2/25

88 6.7 本章小结 本章主要介绍了树和二叉树两种数据结构的定义以及它们的存储结构和运算定义。
6.7 本章小结 本章主要介绍了树和二叉树两种数据结构的定义以及它们的存储结构和运算定义。 树是以分支关系定义的层次结构，结构中的数据元素之间存在着“一对多”的关系。树中除根结点没有前驱外，其它每个结点只有一个前驱；所有结点都有零个或多个后继。因此树型结构为自然界和计算机应用中出现的具有层次关系或分支关系的数据，提供了一种自然的表示方法。 如可用树型结构描述人类社会的族谱和各种社会组织机构等。 在计算机学科和应用领域中，树也得到广泛应用。例如在编译程序中，可用树来表示源程序的语法结构等。树还是一种典型的递归结构。 二叉树是另一种树型结构，是度为2的有序树。本章重点讨论了二叉树。二叉树中每个结点至多有两个孩子，它有明确的左、右之分。 一棵深度为h的二叉树，最少含有h个结点，最多含有2h-1个结点；一棵具有n个结点的二叉树，其最小深度为 log2n」+1。 2019/2/25

89 二叉树具有顺序和链式两种存储结构。对于完全二叉树通常采用顺序存储结构，对于普通二叉树通常采用链式存储结构。
树和二叉树的遍历算法是实现各种操作的基础。是把非线性结构变成线性结构的一种排列方式。对这种非线性结构的遍历需要选择合适的搜索路径，以确保在这条路径上可以访问到结构中的所有数据元素。它包括先序、中序、后序三种不同的遍历次序（树没有中序遍历）。要求读者能熟练掌握二叉树的前序，中序，后序遍历的递归算法，以及树和二叉树之间，森林和树之间转换的具体方法，熟悉线索二叉树的定义及其线索化算法。 作为应用，最后介绍了最优二叉树和最优前缀编码的构造方法。最优二叉树是一种“带权路径长度WPL”最短的二叉树，最优前缀编码（哈夫曼编码）是最优二叉树的一种应用。 2019/2/25