第6章 树和二叉树

1、数据结构与算法数据结构与算法电子工业出版社电子工业出版社数据结构与算法数据结构与算法 作作 者：胡明者：胡明 王红梅王红梅 出版社：电子工业出版社出版社：电子工业出版社 邮邮 箱：箱：数据结构与算法数据结构与算法电子工业出版社电子工业出版社树的逻辑结构树的逻辑结构树的存储结构树的存储结构二叉树的逻辑结构二叉树的逻辑结构二叉树的存储结构及实现二叉树的存储结构及实现二叉树遍历的非递归算法二叉树遍历的非递归算法 树、森林与二叉树的转换树、森林与二叉树的转换哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码第第 6 章章 树和二叉树树和二叉树本章的主要内容是本章的主要内容是数据结构与算法数据结构与算法电子工业出

2、版社电子工业出版社例例6-1 文件系统文件系统6.1 引言引言如何存储这个文件目录结构并统计大小呢？如何存储这个文件目录结构并统计大小呢？数据结构与算法数据结构与算法电子工业出版社电子工业出版社例例6-2 二叉表示树二叉表示树6.1 引言引言如何建立二叉表示树并进行计算呢？如何建立二叉表示树并进行计算呢？一个算术表达式可以用二叉树来表示，这样的二叉树称为一个算术表达式可以用二叉树来表示，这样的二叉树称为二叉表示树。表达式二叉表示树。表达式(A+B)*(C+D*E) 的二叉表示树如下：的二叉表示树如下： 数据结构与算法数据结构与算法电子工业出版社电子工业出版社树的定义树的定义树：树：n（n0）个

3、个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； 当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个个互不相交互不相交的有限集合的有限集合T1, ,T2, , ,Tm，其中其中每个集合又是一棵树，并称为这个根结点的每个集合又是一棵树，并称为这个根结点的子树子树。6.2 树的逻辑结构树的逻辑结构树的定义是采用递归方法树的定义是采用递归方法数据结构与算法数据结构与算法电子工业出版社电子工业出版社(a) 一棵树结构一棵树结构

4、 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 树的定义树的定义ACBGFEDHIACBGFDACBGFDE6.2 树的逻辑结构树的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社树的应用举例树的应用举例文件结构文件结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic6.2 树的逻辑结构树的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社树的基本术语树的基本术语p 结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。p 树的度：树的度：树中各结点度的最大值。树中各结点度的最

5、大值。CGBDEFKLHMIJA6.2 树的逻辑结构树的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社p 叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。p 分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA树的基本术语树的基本术语6.2 树的逻辑结构树的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社p 孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个结点的树中某结点子树的根结点称为这个结点的孩孩子结点子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双

6、亲结点双亲结点；p 兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 CGBDEFKLHMIJA树的基本术语树的基本术语6.2 树的逻辑结构树的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社p 路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关系：结点有如下关系：结点ni是是ni+1的双亲（的双亲（1=idata); /访问根结点的数据域访问根结点的数据域 PreOrder(root-lchild); /前序递归遍历前序递归遍历root的左子树的左子树 PreOrder(root-rchild); /前序递归遍历前

7、序递归遍历root的右子树的右子树 6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社中序遍历中序遍历递归算法递归算法 void InOrder (BiNode *root) if (root = NULL) return; /递归调用的结束条件递归调用的结束条件 else InOrder(root-lchild); /中序递归遍历中序递归遍历root的左子树的左子树 printf(root-data); /访问根结点的数据域访问根结点的数据域 InOrder(root-rchild); /中序递归遍历中序递归遍历root的右子树的右子树 6.5

8、二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社后序遍历后序遍历递归算法递归算法void PostOrder(BiNode *root) if (root = NULL) return; /递归调用的结束条件递归调用的结束条件 else PostOrder(root-lchild); /后序递归遍历后序递归遍历root的左子树的左子树 PostOrder(root-rchild); /后序递归遍历后序递归遍历root的右子树的右子树 printf(root-data); /访问根结点的数据域访问根结点的数据域 6.5 二叉树的存储结构二叉树的存储结构数据

9、结构与算法数据结构与算法电子工业出版社电子工业出版社层序遍历层序遍历ABCDEFG遍历序列：遍历序列：AAB CBDCE F GD E F G6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社层序遍历层序遍历 队列队列Q初始化；初始化； 2. 如果二叉树非空，将根指针入队；如果二叉树非空，将根指针入队；3. 循环直到队列循环直到队列Q为空为空 3.1 q=队列队列Q的队头元素出队；的队头元素出队； 3.2 访问结点访问结点q的数据域；的数据域； 3.3 若结点若结点q存在左孩子，则将左孩子指针入队；存在左孩子，则将左孩子指针入队； 3.4 若结点若

10、结点q存在右孩子，则将右孩子指针入队；存在右孩子，则将右孩子指针入队；6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社建立二叉树建立二叉树6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社建立二叉树：建立二叉树：i1为前序序列的起始下标，为前序序列的起始下标，i2为中序序列的为中序序列的起始下标，起始下标，k为序列长度为序列长度6.5 二叉树的存储结构二叉树的存储结构BiNode *Creat(BiNode *root, int i1, int i2, int k) if (k data = prei

11、1; /根结点为前序序列的第根结点为前序序列的第1个元素个元素 m = pos(prei1, pin, i2); /查找根结点在中序序列中的位置查找根结点在中序序列中的位置 leftlen = m - i2; /左子树的长度左子树的长度 rightlen = k -(leftlen + 1); /右子树的长度右子树的长度 root-lchild = Creat(root-lchild, i1+1, i2, leftlen); root-rchild = Creat(root-rchild, i1+leftlen+1, m+1, rightlen); return root;数据结构与算法数据结

12、构与算法电子工业出版社电子工业出版社二叉树算法设计练习二叉树算法设计练习 遍历二叉树是二叉树各种操作的基础，遍历算法遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。容，可以派生出很多关于二叉树的应用算法。 void InOrder ( (BiNode *root) ) if ( (root=NULL) ) return; else InOrder( (root-lchild) ); co

13、ut-data; InOrder( (root-rchild) ); 数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树算法设计练习二叉树算法设计练习设计算法求二叉树的结点个数。设计算法求二叉树的结点个数。 void Count(BiNode *root) /count为全局量并已初始化为为全局量并已初始化为0 if (root = NULL) return; else Count(root-lchild); count+; Count(root-rchild); 数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树算法设计练习二叉树算法设计练习设计算法按前序次序打印二叉

14、树中的叶子结点。设计算法按前序次序打印二叉树中的叶子结点。 void PreOrder(BiNode *root) if (root = NULL) return; else if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树算法设计练习二叉树算法设计练习设计算法求二叉树的深度。设计算法求二叉树的深度。 int Depth(BiNode *root) if (root = NULL) return

15、0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; 数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树算法设计练习二叉树算法设计练习设计算法求树中结点设计算法求树中结点 x 的第的第 i 个孩子。个孩子。 TNode *Search(TNode *root, DataType x, int i) if (root-data = x) j=1; p=root-firstchild; while (p!=NULL & jrightsib; if (p != NULL) re

16、turn p; else return NULL; Search(root-firstchild, x, i); Search(root-rightsib, x, i);数据结构与算法数据结构与算法电子工业出版社电子工业出版社三叉链表三叉链表GFEDBAABCDEFGC在二叉链表中，如何求某结点的双亲？在二叉链表中，如何求某结点的双亲？6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社三叉链表三叉链表 lchild dataparent rchild在二叉链表的基础上增加了一个指向双亲的指针域。在二叉链表的基础上增加了一个指向双亲的指针域。结点结构

17、结点结构其中：其中：data、lchild和和rchild三个域的含义同二叉链表三个域的含义同二叉链表的结点结构；的结点结构；parent域为域为指向该结点的双亲结点的指针。指向该结点的双亲结点的指针。 6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社ABCDEFGABDEFCG三叉链表三叉链表6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社ABCDEFG三叉链表的静态链表形式三叉链表的静态链表形式0123456data parent lchild rchildABCDEFG-1 0 0 1 2 2

18、 3 1 3 4-1-1-1-1 2-1 5 6-1-1-16.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社线索链表线索链表如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中序遍历序列：D G B A F C F如果二叉树如果二叉树不不改变，如何保存？改变，如何保存？顺顺序序存存储储D G B A F C F6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社线索链表线索链表如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中

19、序遍历序列：D G B A F C F如果二叉树改变，如何保存？如果二叉树改变，如何保存？链链接接存存储储 D F 6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社线索链表线索链表如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中序遍历序列：D G B A F C F如何将二叉链表与中序链表结合？如何将二叉链表与中序链表结合？链接链接存储存储 D F 6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社线索链表线索链表p线索：线索：将二叉链表中的空指针域指向前驱结

20、点和后将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；继结点的指针被称为线索；p线索化：线索化：使二叉链表中结点的空链域存放其前驱或使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；后继信息的过程称为线索化；p线索链表：线索链表：加上线索的二叉链表称为线索链表。加上线索的二叉链表称为线索链表。如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点将二叉链表中的空指针域指向其前驱结点和后继结点6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社 ltag lchild dat

21、a child rtag0: lchild指向该结点的左孩子指向该结点的左孩子1: lchild指向该结点的前驱结点指向该结点的前驱结点0: rchild指向该结点的右孩子指向该结点的右孩子1: rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=结点结构结点结构线索链表线索链表6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社enum flag Child, Thread; /枚举类型枚举类型typedef int DataType; / DataType为二叉树的数据类型为二叉树的数据类型typedef struct Thr

22、Node /定义线索链表的结点结构定义线索链表的结点结构 DataType data; ThrNode *lchild, *rchild; flag ltag, rtag; ThrNode, *root; /root为指向线索链表的头指针为指向线索链表的头指针线索链表线索链表 ltag lchild data child rtag结点结构结点结构6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树的遍历方式有二叉树的遍历方式有4种，故有种，故有4种意义下的前驱和后种意义下的前驱和后继，相应的有继，相应的有4种线索二叉树：种线索二叉树： 前序线索

23、二叉树前序线索二叉树 中序线索二叉树中序线索二叉树 后序线索二叉树后序线索二叉树 层序线索二叉树层序线索二叉树线索二叉树线索二叉树6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社FABDCEG中序线索二叉树中序线索二叉树线索二叉树线索二叉树中序序列：中序序列：D G B A E C F6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社分析：分析：建立线索链表，实质上就是将二叉链表中的空建立线索链表，实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信指针改为指向前驱或后继的线索，而

24、前驱或后继的信息只有在遍历该二叉树时才能得到。息只有在遍历该二叉树时才能得到。建立二叉链表建立二叉链表遍历二叉树，将遍历二叉树，将空指针改为线索空指针改为线索建立线索链表建立线索链表6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建立过程已经建立起二叉链表已经建立起二叉链表6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建

25、立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点p16.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre1p16.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程

26、的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p16.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p116.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序

27、线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p1116.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p11116.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG000000000

28、00000中序线索链表中序线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p111116.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社A头指针头指针BCDEFG00000000000000中序线索链表中序线索链表的建立过程的建立过程中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre111111116.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社在遍历过程中

29、，访问当前结点在遍历过程中，访问当前结点root的操作为：的操作为：如果如果root的左、右指针域为空，则将相应标志置的左、右指针域为空，则将相应标志置1；若若root的左指针域为空，则令其指向它的前驱，这的左指针域为空，则令其指向它的前驱，这需要设指针需要设指针pre始终指向刚刚访问过的结点，显然始终指向刚刚访问过的结点，显然pre的初值为的初值为NULL；若若pre的右指针域为空，则令其指向的右指针域为空，则令其指向它的后继，即当前访问的结点它的后继，即当前访问的结点root; 令令pre指向刚刚访问过的结点指向刚刚访问过的结点root；6.5 二叉树的存储结构二叉树的存储结构建立线索链表

30、建立线索链表数据结构与算法数据结构与算法电子工业出版社电子工业出版社1. 建立二叉链表，将每个结点的左右标志置为建立二叉链表，将每个结点的左右标志置为0；2. 遍历二叉链表，建立线索；遍历二叉链表，建立线索； 2.1 如果二叉链表如果二叉链表root为空，则空操作返回；为空，则空操作返回； 2.2 对对root的左子树建立线索；的左子树建立线索； 2.3 对根结点对根结点root建立线索；建立线索； 2.3.1 若若root没有左孩子，则为没有左孩子，则为root加上前驱线索加上前驱线索; 2.3.2 若若root没有右孩子没有右孩子，则将则将root右标志置为右标志置为1； 2.3.3 若结

31、点若结点pre右标志为右标志为1，则为，则为pre加上后继线索；加上后继线索； 2.3.4 令令pre指向刚刚访问的结点指向刚刚访问的结点root； 2.4 对对root的右子树建立线索。的右子树建立线索。6.5 二叉树的存储结构二叉树的存储结构建立线索链表建立线索链表数据结构与算法数据结构与算法电子工业出版社电子工业出版社void inThrBiTree(ThrNode *root) /pre是全局变量，初始化为空是全局变量，初始化为空 if (root = NULL) return; inThrBiTree(root-lchild); /递归处理递归处理root的左子树的左子树 if (r

32、oot-lchild = NULL) /对对root的左指针进行处理的左指针进行处理 root-ltag = 1; root-lchild = pre; /设置设置pre的前驱线索的前驱线索 if (root-rchild = NULL) /对对root的右指针进行处理的右指针进行处理 root-rtag = 1; if (pre-rtag = 1) pre-rchild = root; /设置设置pre的后继线索的后继线索 pre = root; inThrBiTree(root-rchild); /递归处理递归处理root的右子树的右子树6.5 二叉树的存储结构二叉树的存储结构建立线索链表

33、建立线索链表数据结构与算法数据结构与算法电子工业出版社电子工业出版社中序线索链表查找后继中序线索链表查找后继FABDCEG 如果结点如果结点p的右标志为的右标志为1，则表明该结点的右指针是线索；则表明该结点的右指针是线索； 如果结点如果结点p的右标志为的右标志为0，则表明该结点有右孩子。根据则表明该结点有右孩子。根据中序遍历的操作定义，它的后中序遍历的操作定义，它的后继结点应该是遍历其右子树时继结点应该是遍历其右子树时第一个访问的结点，即右子树第一个访问的结点，即右子树中的最左下结点。中的最左下结点。6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版

34、社ThrNode *Next(ThrNode *p) if (p-rtag = 1) /右标志为右标志为1，可直接得到后继结点，可直接得到后继结点 q = p-rchild; else q = p-rchild; /工作指针工作指针q指向结点指向结点p的右孩子的右孩子 while (q-ltag = 0) /查找最左下结点查找最左下结点 q = q-lchild; return q;中序线索链表查找后继中序线索链表查找后继6.5 二叉树的存储结构二叉树的存储结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树前序遍历的非递归算法的二叉树前序遍历的非递归算法的关键关键：在前序遍历过

35、：在前序遍历过某结点的整个左子树后，如何找到该结点的某结点的整个左子树后，如何找到该结点的右子树右子树的的根指针。根指针。解决办法：解决办法：在访问完该结点后，将该结点的指针保存在访问完该结点后，将该结点的指针保存在在栈栈中，以便以后能通过它找到该结点的右子树。中，以便以后能通过它找到该结点的右子树。 在前序遍历中，设要遍历二叉树的根指针为在前序遍历中，设要遍历二叉树的根指针为root，则则有两种可能：有两种可能： 若若root!=NULL，则表明？如何处理？则表明？如何处理？ 若若root=NULL，则表明？如何处理？则表明？如何处理？前序遍历前序遍历非递归算法非递归算法6.5 二叉树遍历的

36、非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社访问结点序列访问结点序列:A栈栈S内容内容:B D A B前序遍历的前序遍历的非递归非递归实现实现 ADBC6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社访问结点序列访问结点序列:A栈栈S内容内容:B D A前序遍历的前序遍历的非递归非递归实现实现 ADBC D6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社访问结点序列访问结点序列:A栈栈S内容内容:B D C前序遍历的前序遍历的非递归

37、非递归实现实现 ADBCC6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社1.栈栈s初始化；初始化；2.循环直到循环直到root为空且栈为空且栈s为空为空 2.1 当当root不空时循环不空时循环2.1.1 输出输出root-data; 2.1.2 将指针将指针root的值保存到栈中；的值保存到栈中； 2.1.3 继续遍历继续遍历root的左子树的左子树2.2 如果栈如果栈s不空，则不空，则2.2.1 将栈顶元素弹出至将栈顶元素弹出至root；2.2.2 准备遍历准备遍历root的右子树；的右子树； 前序遍历前序遍历非递归算法（伪代码

38、）非递归算法（伪代码）6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社前序遍历前序遍历非递归算法（伪代码）非递归算法（伪代码）void PreOrder(BiNode *root) top = -1; /采用顺序栈，并假定不会发生上溢采用顺序栈，并假定不会发生上溢 bt = root; while (bt != NULL | top != -1) while (bt != NULL) printf(bt-data); S+top = bt; /将根指针将根指针bt入栈入栈 bt = bt-lchild; if (top != -1)

39、/栈非空栈非空 bt = Stop-; bt = bt-rchild; 6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社中序遍历中序遍历非递归算法非递归算法在二叉树的中序遍历中，访问结点的操作发生在该结点的在二叉树的中序遍历中，访问结点的操作发生在该结点的左子树遍历完毕并准备遍历右子树时，所以，在遍历过程左子树遍历完毕并准备遍历右子树时，所以，在遍历过程中遇到某结点时并不能立即访问它，而是将它压栈，等到中遇到某结点时并不能立即访问它，而是将它压栈，等到它的左子树遍历完毕后，再从栈中弹出并访问之。中序遍它的左子树遍历完毕后，再从栈中弹出

40、并访问之。中序遍历的非递归算法只需将前序遍历的非递归算法中的输出语历的非递归算法只需将前序遍历的非递归算法中的输出语句句coutdata移到移到bt = stop-之后即可。之后即可。 6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社中序遍历中序遍历非递归算法非递归算法void InOrder(BiNode *root) top = -1; /采用顺序栈，并假定不会发生上溢采用顺序栈，并假定不会发生上溢 bt = root; while (bt != NULL | top != -1) while (bt != NULL) S+top

41、 = bt; /将根指针将根指针bt入栈入栈 bt = bt-lchild; if (top != -1) /栈非空栈非空 bt = Stop-; printf(root-data); bt = bt-rchild; 6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社后序遍历后序遍历非递归算法非递归算法在后序遍历过程中，结点要入两次栈，出两次栈：在后序遍历过程中，结点要入两次栈，出两次栈： 第一次出栈：只遍历完左子树，该结点不出栈，利用栈顶第一次出栈：只遍历完左子树，该结点不出栈，利用栈顶结点找到它的右子树，准备遍历它的右子树；结点找到

42、它的右子树，准备遍历它的右子树； 第二次出栈：遍历完右子树，将该结点出栈，并访问它。第二次出栈：遍历完右子树，将该结点出栈，并访问它。因此，为了区别同一个结点的两次出栈，设置标志因此，为了区别同一个结点的两次出栈，设置标志flag。栈元素类型定义如下：栈元素类型定义如下：typedef struct BiNode *ptr; int flag; element; /1表示第表示第1次出栈，次出栈，2表示第表示第2次出栈次出栈6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社后序遍历后序遍历非递归算法非递归算法设根指针为设根指针为bt，则

43、可能有以下两种情况：，则可能有以下两种情况： 若若bt不等于不等于NULL，则，则bt及标志及标志flag（置为（置为1）入栈，遍历）入栈，遍历其左子树；其左子树； 若若bt等于等于NULL，此时若栈空，则整个遍历结束；若栈不，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志结点的标志flag = 1，则表明栈顶结点的左子树已遍历完毕，则表明栈顶结点的左子树已遍历完毕，将将flag修改为修改为2，并遍历栈顶结点的右子树；若栈顶结点的标，并遍历栈顶结点的右子树；若栈顶结点的标志志flag = 2，

44、则表明栈顶结点的右子树也遍历完毕，输出栈顶，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。结点。6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社后序遍历后序遍历非递归算法非递归算法void PostOrder(BiNode *root) element Sn, top = -1; bt = root; while (bt != NULL | top != -1) while (bt != NULL) top+; Stop.ptr = bt; Stop.flag = 1; /root连同标志连同标志flag入栈入栈 bt = bt-l

45、child; while (top != -1 & Stop.flag = 2) bt = Stop-.ptr; printf(bt-data); if (top != -1) Stop.flag = 2; bt = stop.ptr-rchild; 6.5 二叉树遍历的非递归算法二叉树遍历的非递归算法数据结构与算法数据结构与算法电子工业出版社电子工业出版社是哪些树结构的是哪些树结构的存储结构存储结构? ?树和二叉树之间具有对应关系树和二叉树之间具有对应关系AEBCFDGA BCED F GABCDEFG6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电

46、子工业出版社电子工业出版社树和二叉树之间的对应关系树和二叉树之间的对应关系 树：兄弟关系树：兄弟关系二叉树：双亲和右孩子二叉树：双亲和右孩子 树：双亲和长子树：双亲和长子二叉树：双亲和左孩子二叉树：双亲和左孩子AEBCFDGABCDEFG6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社6.6 树、森林与二叉树的转换树、森林与二叉树的转换 1.兄弟加线兄弟加线.树和二叉树之间的对应关系树和二叉树之间的对应关系ABCDEFG数据结构与算法数据结构与算法电子工业出版社电子工业出版社2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去

47、与其他孩子的连线其他孩子的连线.ABCDEFG树和二叉树之间的对应关系树和二叉树之间的对应关系 1.兄弟加线兄弟加线.6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社3.顺时针转动顺时针转动,使之使之层次分明层次分明.树和二叉树之间的对应关系树和二叉树之间的对应关系2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线. 1.兄弟加线兄弟加线.ABCDEFG6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社3.顺时针转动顺时针转动,使之使之层

48、次分明层次分明.树和二叉树之间的对应关系树和二叉树之间的对应关系2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线. 1.兄弟加线兄弟加线.GDABECF6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社树转换为二叉树树转换为二叉树 加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 去线去线对树中的每个结点，只保留它与第一个对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间孩子结点之间的连线，删去它与其它孩子结点之间的连线。的连线。 层次调整层次

49、调整以根结点为轴心，将树顺时针转动以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。一定的角度，使之层次分明。 6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社CBEDFGAABEFCDG前序遍历前序遍历AEBCFDGABEFCDG前序遍历前序遍历6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社EFBCGDA后序遍历后序遍历EFBCGDA中序遍历中序遍历CBEDFGAAEBCFDG6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出

50、版社电子工业出版社森林转换为二叉树森林转换为二叉树 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的根从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点结点作为前一棵二叉树根结点的右孩子，当所有二的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树换得到的二叉树。6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社FEDCBAGHIJBAFEDCGHIKKIFEHABCGD6.6 树、森林与二叉树的转

51、换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社二叉树转换为树或森林二叉树转换为树或森林 加线加线若某结点若某结点x是其双亲是其双亲y的左孩子，则把结点的左孩子，则把结点x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都与结点，都与结点y用线连用线连起来；起来； 去线去线删去原二叉树中所有的双亲结点与右孩子结删去原二叉树中所有的双亲结点与右孩子结点的连线；点的连线； 层次调整层次调整整理由、两步所得到的树或森林，整理由、两步所得到的树或森林，使之层次分明。使之层次分明。 6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子

52、工业出版社电子工业出版社FHGEAICDBFHGDCEBAIFEDCBAHGI加线加线去线去线层次调整层次调整IHGBCDAFE6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数据结构与算法电子工业出版社电子工业出版社森林的遍历森林的遍历森林有两种遍历方法：森林有两种遍历方法：前序（根）遍历：前序遍历森林即为前序遍历森前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。林中的每一棵树。 后序（根）遍历：后序遍历森林即为后序遍历森后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。林中的每一棵树。 6.6 树、森林与二叉树的转换树、森林与二叉树的转换数据结构与算法数

53、据结构与算法电子工业出版社电子工业出版社【问题问题】已知已知Windows操作系统的文件目录结构，请统计每个操作系统的文件目录结构，请统计每个文件和文件夹的大小。文件和文件夹的大小。【算法算法】可以用树结构表示这种文件目录结构，输出即是对树可以用树结构表示这种文件目录结构，输出即是对树进行后序遍历的结果，括号内的数字代表文件大小，其中文件进行后序遍历的结果，括号内的数字代表文件大小，其中文件的大小即是文件本身的大小，文件夹的大小是本身大小和目录的大小即是文件本身的大小，文件夹的大小是本身大小和目录下所有文件的大小之和。下所有文件的大小之和。设树用孩子兄弟表示法存储，存储结构定义如下：设树用孩子

54、兄弟表示法存储，存储结构定义如下：typedef struct FSNode char name32; /文件（或文件夹）名文件（或文件夹）名 int size; /文件（或文件夹）大小文件（或文件夹）大小 FSNode *firstchild, *rightsib; /指向最左孩子和右兄弟指向最左孩子和右兄弟 FSNode;6.7 应用举例应用举例文件系统文件系统数据结构与算法数据结构与算法电子工业出版社电子工业出版社【算法算法】首先需建立一棵树。这里采用按层次序建立树的孩子首先需建立一棵树。这里采用按层次序建立树的孩子兄弟表示法存储结构，算法如下：兄弟表示法存储结构，算法如下：6.7 应用

55、举例应用举例文件系统文件系统数据结构与算法数据结构与算法电子工业出版社电子工业出版社相关概念相关概念叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的对叶子结点赋予的一个有意义的数值量。数值量。 二叉树的带权路径长度：二叉树的带权路径长度：设二叉树具有设二叉树具有n个带权值的个带权值的叶子结点，从根结点到各个叶子结点的路径长度与叶子结点，从根结点到各个叶子结点的路径长度与相相应叶子结点权值的乘积之和。应叶子结点权值的乘积之和。 记为：记为：WPL=6.7 应用举例应用举例哈夫曼树哈夫曼树 nkkklw1第第k个叶子的权值；个叶子的权值；从根结点到第从根结点到第k个叶子的路径长度个叶子

56、的路径长度数据结构与算法数据结构与算法电子工业出版社电子工业出版社哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带权结点，带权路径路径长度最小的二叉树长度最小的二叉树。例：给定例：给定4个叶子结点，其权值分别为个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的可以构造出形状不同的多个二叉树。多个二叉树。 WPL=32 WPL=41 WPL=302347234774236.7 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社哈夫曼树的特点：哈夫曼树的特点：1. 权值越大的叶子结点越靠近根结点，而权值越小的权值越大的

57、叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。叶子结点越远离根结点。 2. 只有度为只有度为0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结（分支结点）的结点，不存在度为点，不存在度为1的结点的结点. 2347WPL=32 WPL=41 WPL=30234774236.7 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社哈夫曼算法基本思想：哈夫曼算法基本思想： 初始化初始化：由给定的：由给定的n个权值个权值w1，w2，wn构造构造n棵只有一个根结点的二叉树，从而得到一个二叉树棵只有一个根结点的二叉树，从而得到一个二叉树集合集合FT1，T

58、2，Tn； 选取与合并选取与合并：在：在F中选取根结点的权值中选取根结点的权值最小最小的两的两棵二叉树分别作为左、右子树构造一棵新的二叉树棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；结点的权值之和； 删除与加入删除与加入：在：在F中删除作为左、右子树的两棵中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到二叉树，并将新建立的二叉树加入到F中；中； 重复重复、两步，当集合、两步，当集合F中只剩下一棵二叉树中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。时，这棵二叉树便是哈夫曼树。 6.7

59、 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社第第1步：初始化步：初始化W2，4，5 ，3 哈夫曼树的构造过程哈夫曼树的构造过程3524第第2步：选取与合并步：选取与合并32 5第第3步：删除与加入步：删除与加入5432 56.7 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社W2，4，5 ，3 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2步步5432 554 9重复第重复第3步步 554 9326.7 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社W2，3，4

60、，5 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2步步重复第重复第3步步 554 932 554 932146.7 应用举例应用举例哈夫曼树哈夫曼树数据结构与算法数据结构与算法电子工业出版社电子工业出版社哈夫曼算法的存储结构哈夫曼算法的存储结构 1. 设置一个数组设置一个数组huffTree2n- -1保存哈夫曼树中各保存哈夫曼树中各点的点的信息，数组元素的结点结构信息，数组元素的结点结构 。 weight lchild rchild parent其中：其中：weight：权值域，保存该结点的权值；：权值域，保存该结点的权值； lchild：指针域，结点的左孩子结点在数组中的下标；：指针域，结点的左孩子结点在