数据结构第6章(1)

1、数 据 结 构 第第6 6章章 树和二叉树树和二叉树北华航天工业学院计算机系 制作目 标理解树、二叉树的定义、相关术语；理解树、二叉树的定义、相关术语；掌握二叉树的二叉链表存储方式、二叉树性质；掌握二叉树的二叉链表存储方式、二叉树性质；掌握二叉树的四种遍历方式及遍历的实现算法；掌握二叉树的四种遍历方式及遍历的实现算法；理解二叉树的线索化方法；理解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题灵活运用二叉树的遍历方法解决相关的应用问题 理解树、森林和二叉树间的转换理解树、森林和二叉树间的转换理解树、森林的遍历理解树、森林的遍历北华航天工业学院计算机系 制作本章内容本章内容6.1

2、树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 二叉树的遍历和线索二叉树二叉树的遍历和线索二叉树6.4 树和森林树和森林6.5 哈夫曼树及其应用哈夫曼树及其应用北华航天工业学院计算机系 制作6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作1 1二叉树二叉树 二叉树（二叉树（Binary TreeBinary Tree）是个有限元素的集合）是个有限元素的集合，该集合或者为空、或者由一个称为，该集合或者为空、或者由一个称为根根(root)(root)的的元素及两个互不相交的、被分别称为元素及两个互不相交的

3、、被分别称为左子树左子树和和右右子树子树的二叉树组成。的二叉树组成。 当集合为空时，称该二叉树为当集合为空时，称该二叉树为空二叉树空二叉树。 在二叉树中，元素称作在二叉树中，元素称作结点结点。 二叉树是二叉树是有序树有序树。 二叉树有二叉树有五种五种形态。形态。6.2.1 二叉树的基本概念北华航天工业学院计算机系 制作 二叉树的五种基本形态：二叉树的五种基本形态：6.2.1 二叉树的基本概念北华航天工业学院计算机系 制作2 2二叉树的相关概念二叉树的相关概念 结点的度结点的度；叶子结点叶子结点；分支结点分支结点； 左孩子、右孩子、双亲、兄弟左孩子、右孩子、双亲、兄弟； 路径、路径长度路径、路径

4、长度； 祖先、子孙祖先、子孙； 结点的层数结点的层数；树的深度树的深度；树的度树的度； 满二叉树；完全二叉树满二叉树；完全二叉树 6.2.1 二叉树的基本概念北华航天工业学院计算机系 制作6.2 二叉树的定义与性质 6.2.1 二叉树的基本概念 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作6.2.2 二叉树的主要性质 性质性质1 1 一棵非空二叉树的第一棵非空二叉树的第i层上最多有层上最多有2i-1个个结点（结点（i1）。）。 性质性质2 2 一棵深度为一棵深度为k的二叉树中，最多具有的二叉树中，最多具有2k1个结点。个结点。 证明 设第i层的结点数为x

5、i（1ik），深度为k的二叉树的结点数为M，xi最多为2i-1，则有：北华航天工业学院计算机系 制作 性质性质3 3 对于一棵非空的二叉树，如果叶子结点对于一棵非空的二叉树，如果叶子结点数为数为n n0，度数为，度数为2 2的结点数为的结点数为n n2，则有，则有:n:n0n n21 1。证明：证明：结点总数结点总数n nn n0 0n n1 1n n2 2 （6-16-1） 在二叉树中，除根结点外，其余结点只有唯一在二叉树中，除根结点外，其余结点只有唯一的一个前驱。则有：的一个前驱。则有：分支数分支数n n1 1 （6-26-2） 这些分支是由度为这些分支是由度为1 1和度为和度为2 2的结

6、点发出的，所的结点发出的，所以：以：分支数分支数n n1 12n2n2 2 （6-36-3） 综合上三式可得：综合上三式可得：n n0 0n n2 21 16.2.2 二叉树的主要性质北华航天工业学院计算机系 制作性质性质4 4 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度k为为 log2n +1。 证明证明：当一棵完全二叉树的深度为：当一棵完全二叉树的深度为k k、结点个、结点个数为数为n n时，满足时，满足2 2k k1 1n2n2k k。 对不等式取对数，有对不等式取对数，有k k1log1log2 2nkn1i1，则双亲结点的序号为，则双亲结点的序号为i/2i/2；如果；

7、如果i i1 1，则，则i i是根结点，无双亲结点。是根结点，无双亲结点。 如果如果2in2in，则左孩子结点的序号为，则左孩子结点的序号为2i2i；如果；如果2in2in，则无左孩子；如果，则无左孩子；如果2i2i1n1n，则右孩子结点，则右孩子结点的序号为的序号为2i2i1 1；如果；如果2i2i1n1n，则无右孩子。，则无右孩子。 注意：若对二叉树的根结点从注意：若对二叉树的根结点从0 0开始编号，都会发开始编号，都会发生变化。生变化。6.2.2 二叉树的主要性质北华航天工业学院计算机系 制作选择题选择题1 1、按二叉树的定义，具有、按二叉树的定义，具有3 3个结点的二叉树有（个结点的二

8、叉树有（ ）种。种。 A A、3 B3 B、4 C4 C、5 D5 D、6 62 2、深度为、深度为5 5的二叉树至多有（的二叉树至多有（ ）个结点。）个结点。 A A、16 B16 B、31 C31 C、32 D32 D、10103 3、对一个满二叉树，、对一个满二叉树，m m个树叶，个树叶，n n个结点，深度为个结点，深度为h h，则（则（ ）。）。 A A、n=h+mn=h+m B B、h+mh+m=2n C=2n C、m=h-1 Dm=h-1 D、n=2n=2h h-1-1答案：答案：1 1（C C） 2 2（B B） 3 3（D D）6.2.2 二叉树的主要性质北华航天工业学院计算机

9、系 制作选择题选择题4 4、设高度为、设高度为h h的二叉树上只有度为和度为的二叉树上只有度为和度为2 2的结点，的结点，则此类二叉树中包含的结点数至少为（则此类二叉树中包含的结点数至少为（ ）。）。 A A、2h B2h B、2h-1 C2h-1 C、2h+1 D2h+1 D、h+1h+15 5、对于一棵深度为、对于一棵深度为4 4的三叉树，最多具有（的三叉树，最多具有（ ）个结）个结点。点。 A A、30 B30 B、36 C36 C、40 D40 D、5454答案：答案：1 1（B B） 2 2（C C） 6.2.2 二叉树的主要性质北华航天工业学院计算机系 制作填空题填空题1 1、深度

10、为、深度为k k的完全二叉树至少有（的完全二叉树至少有（ ）个结点，至多）个结点，至多有（有（ ）个结点，若自上而下，从左到右次序给结点）个结点，若自上而下，从左到右次序给结点编号（从编号（从1 1开始），则编号最小的叶子结点的编号是开始），则编号最小的叶子结点的编号是（ ）。）。2 2、一棵有、一棵有n n（n0n0）个结点的满二叉树共有（）个结点的满二叉树共有（ ）个）个叶子结点和（叶子结点和（ ）个非叶子结点。）个非叶子结点。答案：答案：1(21(2k-1k-1, 2, 2k k-1,2-1,2k-1k-1) 2(n/2) 2(n/2 , n/2+1, n/2+1 ) ) 6.2.2 二

11、叉树的主要性质北华航天工业学院计算机系 制作6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作6.2.3 二叉树的存储结构1顺序存储结构顺序存储结构顺序存储实现：顺序存储实现： 用一组连续的存储单元存放二叉树中的结点。 关系依据二叉树的性质性质5 5存储。利用数组元素的下标值确定结点在二叉树中的位置及结点间的关系。完全二叉树和满二叉树采用顺序存储比较合适。完全二叉树和满二叉树采用顺序存储比较合适。采用顺序存储方式的最坏情况是单分支树。采用顺序存储方式的最坏情况是单分支树。北华航天工业学院计算机系 制作完全二叉树的顺序存

12、储示意：完全二叉树的顺序存储示意：6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作一般二叉树的顺序存储示意一般二叉树的顺序存储示意：6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作 一棵深度为一棵深度为k k的右单支树，需分配的右单支树，需分配2 2k k1 1个存储单元。个存储单元。6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作2链式存储结构链式存储结构（1 1）二叉链表存储）二叉链表存储 链表中每个结点由三个域组成，结点的存储结链表中每个结点由三个域组成，结点的存储结构为：构为： 其中，其中，datadata域存放结点信息；域存放结点信息；lchildlch

13、ild 与与rchildrchild分别存放指向左孩子和右孩子的指针。分别存放指向左孩子和右孩子的指针。6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作 二叉树的二叉链表示（链表也可以带头结点）。二叉树的二叉链表示（链表也可以带头结点）。6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作（2 2）三叉链表存储）三叉链表存储 每个结点由四个域组成，具体结构为：每个结点由四个域组成，具体结构为： 其中，其中，datadata、lchildlchild以及以及rchildrchild三个域的意义三个域的意义同二叉链表结构；同二叉链表结构； parentparent域为指向该结点双亲

14、结点的指针。域为指向该结点双亲结点的指针。6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作 二叉树的三叉链表示。二叉树的三叉链表示。6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作 二叉链表是最常用的二叉树存储方式。二叉链表是最常用的二叉树存储方式。 二叉链表存储表示二叉链表存储表示 typedef struct Node ElemType data; struct Node *lchild;*rchild; BiTNode,*BiTree; BiTree bt； /btbt被定义为根指针被定义为根指针6.2.3 二叉树的存储结构北华航天工业学院计算机系 制作6.2.3 二

15、叉树的存储结构二叉树的基本操作二叉树的基本操作（1 1）创建操作）创建操作（2 2）遍历二叉树）遍历二叉树 先序遍历、中序遍历先序遍历、中序遍历 后序遍历、按层遍历后序遍历、按层遍历北华航天工业学院计算机系 制作小 结理解树、二叉树定义及相关术语理解树、二叉树定义及相关术语掌握二叉树的性质，并用性质解题掌握二叉树的性质，并用性质解题掌握二叉链表存储形式掌握二叉链表存储形式北华航天工业学院计算机系 制作本章内容本章内容6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 二叉树的遍历和线索二叉树二叉树的遍历和线索二叉树6.4 树和森林树和森林6.5 哈夫曼树及其应用哈夫曼树及其

16、应用北华航天工业学院计算机系 制作6.3 二叉树的遍历线索二叉树二叉树的遍历线索二叉树 6.3.1 6.3.1 二叉树的遍历方式二叉树的遍历方式 6.3.2 6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 6.3.3 6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 6.3.4 6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 6.3.5 6.3.5 线索二叉树线索二叉树北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式 二叉树的遍历二叉树的遍历：指按照某种顺序访问二：指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次叉树中的每个结点，使每个结

17、点被访问一次且仅被访问一次。且仅被访问一次。 遍历是二叉树中遍历是二叉树中常用常用到的一种操作。到的一种操作。 通过一次完整的遍历，可使二叉树中结通过一次完整的遍历，可使二叉树中结点信息由点信息由非线性排列变为某种意义上的线性非线性排列变为某种意义上的线性序列序列。北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式二叉树的遍历方式有二叉树的遍历方式有四种四种： 先序、中序、后序和层次遍历先序、中序、后序和层次遍历先序遍历（先序遍历（DLRDLR）定义定义： 若二叉树为空，遍历结束。否则，若二叉树为空，遍历结束。否则，访问访问根结点根结点；先序遍历根结点的先序遍历根结点的

18、左子树左子树；先序遍历根结点的先序遍历根结点的右子树右子树。北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式二叉树的遍历方式有二叉树的遍历方式有四种四种： 先序、中序、后序和层次遍历先序、中序、后序和层次遍历中序遍历（中序遍历（LDRLDR）定义定义： 若二叉树为空，遍历结束。否则，若二叉树为空，遍历结束。否则，中序遍历根结点的中序遍历根结点的左子树左子树；访问访问根结点根结点；中序遍历根结点的中序遍历根结点的右子树右子树。北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式二叉树的遍历方式有二叉树的遍历方式有四种四种： 先序、中序、后序和层次遍

19、历先序、中序、后序和层次遍历后序遍历（后序遍历（LRDLRD）定义定义： 若二叉树为空，遍历结束。否则，若二叉树为空，遍历结束。否则，后序遍历根结点的后序遍历根结点的左子树左子树；后序遍历根结点的后序遍历根结点的右子树右子树。访问访问根结点根结点；北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式二叉树的遍历方式有二叉树的遍历方式有四种四种： 先序、中序、后序和层次遍历先序、中序、后序和层次遍历层次遍历层次遍历定义定义： 若二叉树为空，遍历结束。否则，从二若二叉树为空，遍历结束。否则，从二叉树的叉树的第一层第一层（根结点）开始，（根结点）开始，从上至下从上至下逐逐层遍历

20、，同一层，则按层遍历，同一层，则按从左到右从左到右的顺序逐个的顺序逐个访问结点。访问结点。北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式练习练习1 1： 给 出 下 面给 出 下 面指定二叉树的指定二叉树的四种遍历方式四种遍历方式下的结点序列。下的结点序列。 A B D E I K C G N F 北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式练习练习2 2： 根据给定的遍历结点序列恢复二叉树。根据给定的遍历结点序列恢复二叉树。 LDRLDR：DCBGEAHFIJK DLR DLR：ABCDEGFHJIK 哪些遍历组合可哪些遍历组合可以唯

21、一确定一棵以唯一确定一棵二叉树？二叉树？北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式结论结论 DLRDLR，LDRLDR可以确定一棵二叉树；可以确定一棵二叉树； LDRLDR，LRDLRD可以确定一棵二叉树；可以确定一棵二叉树； LDRLDR，层次遍历可以确定一棵二叉树，层次遍历可以确定一棵二叉树 北华航天工业学院计算机系 制作6.3.1 二叉树的遍历方式二叉树的遍历方式练习练习3 3： 根据给定的遍历结点序列恢复二叉树。根据给定的遍历结点序列恢复二叉树。 LDRLDR： B C A E D G H F I LRD LRD： C B E H G I F D A北华

22、航天工业学院计算机系 制作6.3 二叉树的遍历二叉树的遍历 6.3.1 6.3.1 二叉树的遍历方式二叉树的遍历方式 6.3.2 6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 6.3.3 6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 6.3.4 6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 6.3.5 6.3.5 线索二叉树线索二叉树北华航天工业学院计算机系 制作6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法先序遍历递归算法：先序遍历递归算法： void PreOrder（BiTree bt） if (bt=NULL) return; Visite（bt-da

23、ta）; PreOrder（bt-lchild）; PreOrder（bt-rchild）; 北华航天工业学院计算机系 制作6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法中序遍历递归算法：中序遍历递归算法： void InOrder（BiTree bt） if (bt=NULL) return; InOrder（bt-lchild）; Visite（bt-data）; InOrder（bt-rchild）; 北华航天工业学院计算机系 制作6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法后序遍历递归算法：后序遍历递归算法： void PostOrder（BiTree bt） if (b

24、t=NULL) return; PostOrder（bt-lchild）; PostOrder（bt-rchild）; Visite（bt-data）; 北华航天工业学院计算机系 制作6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 根据根据二叉树的递归定义二叉树的递归定义，很容易写出二叉，很容易写出二叉树先序、中序和后序遍历的递归算法。但并树先序、中序和后序遍历的递归算法。但并非所有非所有程序设计语言程序设计语言都允许递归；另一方面，都允许递归；另一方面，递归程序虽然简洁，但递归程序虽然简洁，但可读性不好，执行效可读性不好，执行效率也不高率也不高。 因此，就存在如何把一个递归算法因此，就

25、存在如何把一个递归算法转化为转化为非递归算法非递归算法的问题。的问题。分析二叉树的先序、中序和后序遍历的递分析二叉树的先序、中序和后序遍历的递归算法的执行过程。归算法的执行过程。北华航天工业学院计算机系 制作6.3 二叉树的遍历二叉树的遍历 6.3.1 6.3.1 二叉树的遍历方式二叉树的遍历方式 6.3.2 6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 6.3.3 6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 6.3.4 6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 6.3.5 6.3.5 线索二叉树线索二叉树北华航天工业学院计算机系 制作6.3.3 二叉树遍历的

26、非递归算法二叉树遍历的非递归算法 递归算法的执行过程：递归算法的执行过程： 从根结点开始从根结点开始沿左子树深入沿左子树深入下去，当深下去，当深入到最左端，无法再深入下去时，则返回，入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到再逐一进入刚才深入时遇到结点的右子树结点的右子树，再进行如此的深入和返回再进行如此的深入和返回，直到最后从根结，直到最后从根结点的右子树返回到点的右子树返回到根结点为止根结点为止。 先序遍历先序遍历是在深入时遇到结点就访问，是在深入时遇到结点就访问，中序遍历中序遍历是在从左子树返回时遇到结点访问，是在从左子树返回时遇到结点访问，后序遍历后序遍历是在从右子

27、树返回时遇到结点访问。是在从右子树返回时遇到结点访问。北华航天工业学院计算机系 制作6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 递归算法的执行过程：递归算法的执行过程： 在这一过程中，返回结点的顺序与深入结点在这一过程中，返回结点的顺序与深入结点的顺序相反，即的顺序相反，即后深入先返回后深入先返回，可以用栈来帮助实，可以用栈来帮助实现这一遍历路线。现这一遍历路线。 先序遍历过程先序遍历过程：先访问结点，将该结点入栈，：先访问结点，将该结点入栈，然后沿左子树深入，深入一个结点同样重复刚才过然后沿左子树深入，深入一个结点同样重复刚才过程；当沿左分支深入不下去时，则返回，即从栈中程；当

28、沿左分支深入不下去时，则返回，即从栈中弹出一个结点，然后从该结点的右子树开始继续深弹出一个结点，然后从该结点的右子树开始继续深入；仍为入；仍为访问、入栈、继续深入访问、入栈、继续深入，深入不下去时再，深入不下去时再返回，直到栈中无结点为止。返回，直到栈中无结点为止。北华航天工业学院计算机系 制作6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 先序遍历的非递归算法：先序遍历的非递归算法：说明：说明：二叉树以二叉链表形式存放；二叉树以二叉链表形式存放； 定义一个顺序栈定义一个顺序栈SeqStack s; void NRPreOrder（BiTree bt） SeqStack s; Ini

29、t_SeqStack( s ); if (bt=NULL) return; BiTNode *p=bt;北华航天工业学院计算机系 制作6.3.3 二叉树遍历的非递归算法 while( !(p=NULL & Empty_SeqStack(s) while(p!=NULL) coutdata; /*访问结点的数据域访问结点的数据域*/ Push_SeqStack(s,p); p=p-lchild； /*往左深入往左深入*/ /*返回返回*/ if (!Empty_SeqStack(s) Pop_SeqStack(s,p); p=p-rchild; /*访问右子树访问右子树*/ 北华航天工业

30、学院计算机系 制作 对于图所示的二叉树，用该算法进行遍历过程中，栈和当前对于图所示的二叉树，用该算法进行遍历过程中，栈和当前指针指针p p的变化情况以及树中各结点的访问次序如下表所示。的变化情况以及树中各结点的访问次序如下表所示。6.3.3 二叉树遍历的非递归实现二叉树遍历的非递归实现北华航天工业学院计算机系 制作6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法中序遍历的非递归算法：中序遍历的非递归算法： 与先序遍历过程比较，中序的区别就是与先序遍历过程比较，中序的区别就是每次每次返回时访问结点返回时访问结点。后序遍历的非递归算法：后序遍历的非递归算法： 与先序遍历过程比较，与先序遍历

31、过程比较，结点在第二次出结点在第二次出栈时访问栈时访问。结点第一次出栈只表示访问完该。结点第一次出栈只表示访问完该结点的左子树，还需再次入栈，第二次出栈结点的左子树，还需再次入栈，第二次出栈才表示该结点的右子树也访问完毕，该遍历才表示该结点的右子树也访问完毕，该遍历该结点。该结点。北华航天工业学院计算机系 制作6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法中序遍历和后序遍历的非递归算法中序遍历和后序遍历的非递归算法自己编写。自己编写。不用栈实现非递归算法的方法不用栈实现非递归算法的方法 三叉链表；三叉链表； 利用线索二叉树利用线索二叉树北华航天工业学院计算机系 制作6.3 二叉树的遍

32、历二叉树的遍历 6.3.1 6.3.1 二叉树的遍历方式二叉树的遍历方式 6.3.2 6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 6.3.3 6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 6.3.4 6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 6.3.5 6.3.5 线索二叉树线索二叉树北华航天工业学院计算机系 制作6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法层次遍历实现算法层次遍历实现算法 分析层次遍历过程分析层次遍历过程 在进行层次遍历时，对一层结点访问完在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左后，再按照它们的访问次序

33、对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问。先遇到的结点先访问。 符合队列特征符合队列特征北华航天工业学院计算机系 制作6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法层次遍历实现算法层次遍历实现算法 设一个队列，遍历从二叉树的根结点开始，设一个队列，遍历从二叉树的根结点开始，首先将根结点入队，执行下面两个操作：首先将根结点入队，执行下面两个操作： 出队一个结点，访问该结点；出队一个结点，访问该结点； 若该结点的左、右孩子结点非空，若该结点的左、右孩子结点非空，则将其左孩子和右孩子结点顺序入队。则将其左孩子和右孩子结点顺

34、序入队。 直到队列为空时，层次遍历结束。直到队列为空时，层次遍历结束。北华航天工业学院计算机系 制作6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法层次遍历实现算法层次遍历实现算法 定义队列定义队列LinkQueue *Q，二叉树以二叉二叉树以二叉链表形式存放。链表形式存放。 void LevelOrder（BiTree bt） LinkQueue *Q; Q=Init_Queue ( ); if (bt=NULL) return; In_Queue(Q,bt);北华航天工业学院计算机系 制作6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 BitNode *p; while( !Em

35、pty_Queue(Q) Out_Queue(Q,p); coutdata; if (p-lchild!=NULL) In_Queue(Q,p-lchild); if (p-rchild!=NULL) In_Queue(Q,p-rchild); 北华航天工业学院计算机系 制作6.3 二叉树的遍历二叉树的遍历 6.3.1 6.3.1 二叉树的遍历方式二叉树的遍历方式 6.3.2 6.3.2 二叉树遍历的递归算法二叉树遍历的递归算法 6.3.3 6.3.3 二叉树遍历的非递归算法二叉树遍历的非递归算法 6.3.4 6.3.4 二叉树的层次遍历算法二叉树的层次遍历算法 6.3.5 6.3.5 线索二

36、叉树线索二叉树北华航天工业学院计算机系 制作6.3.5 6.3.5 线索二叉树线索二叉树1 1线索二叉树的定义线索二叉树的定义为了保留结点在某种遍历序列中直接前驱和直接后为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息。继的位置信息。利用二叉树的二叉链表存储结构中的空指针域来保利用二叉树的二叉链表存储结构中的空指针域来保存该结点的直接前驱结点和直接后继结点，该指针被存该结点的直接前驱结点和直接后继结点，该指针被称为称为线索线索（threadthread），加了线索的二叉树称为），加了线索的二叉树称为线索二线索二叉树叉树。注意：注意： 北华航天工业学院计算机系 制作2 2画线索二叉树画线索二叉树l 线索树有先序线索二叉树、中序线索二叉树和线索树有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。后序线索二叉树三种。l 通常用实线表示二叉树中的指向左、右孩子结通常用实线表示二叉树中的指向左、右孩子结点的指针，用虚线表示线索