数据结构课件树.ppt

1、数 据 结 构, 第6章 树和二叉树,目 标,理解树、二叉树的定义、相关术语； 掌握二叉树的二叉链表存储方式、二叉树性质； 掌握二叉树的四种遍历方式及遍历的实现算法； 理解二叉树的线索化方法； 灵活运用二叉树的遍历方法解决相关的应用问题 理解树、森林和二叉树间的转换 理解树、森林的遍历,本章内容,6.1 树的定义和基本术语,6.2 二叉树,6.3 二叉树的遍历和线索二叉树,6.4 树和森林,6.5 哈夫曼树及其应用,6.2 二叉树,6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,1二叉树 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者

2、由一个称为根(root)的元素及两个互不相交的、被分别称为左子树和右子树的二叉树组成。 当集合为空时，称该二叉树为空二叉树。 在二叉树中，元素称作结点。 二叉树是有序树。 二叉树有五种形态。,6.2.1 二叉树的定义,二叉树的五种基本形态：,6.2.1 二叉树的定义,2二叉树的相关概念 结点的度；叶子结点；分支结点； 左孩子、右孩子、双亲、兄弟； 路径、路径长度； 祖先、子孙； 结点的层数；树的深度；树的度； 满二叉树；完全二叉树,6.2.1 二叉树的定义,6.2 二叉树,6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,6.2.2 二叉树的主要性质,性质1 一

3、棵非空二叉树的第i层上最多有2i-1个结点（i1）。 性质2 一棵深度为k的二叉树中，最多具有2k-1个结点。 证明 设第i层的结点数为xi（1ik），深度为k的二叉树的结点数为M，xi最多为2i-1，则有：,性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21。 证明：结点总数nn0n1n2 （6-1） 在二叉树中，除根结点外，其余结点只有唯一的一个前驱。则有：分支数n1 （6-2） 这些分支是由度为1和度为2的结点发出的，所以：分支数n12n2 （6-3） 综合上三式可得：n0n21,6.2.2 二叉树的主要性质,性质4 具有n个结点的完全二叉树的深

4、度k为log2n+1。 证明：当一棵完全二叉树的深度为k、结点个数为n时，满足2k1n2k。 对不等式取对数，有k1log2nk 由于k是整数，所以有klog2n+1。,6.2.2 二叉树的主要性质,性质5 对于具有n个结点的完全二叉树，如果按从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则任意的序号为i的结点，有： 如果i1，则双亲结点的序号为i/2；如果i1，则i是根结点，无双亲结点。 如果2in，则左孩子结点的序号为2i；如果2in，则无左孩子；如果2i1n，则右孩子结点的序号为2i1；如果2i1n，则无右孩子。 注意：若对二叉树的根结点从0开始编号，都会发生变化。,6.

5、2.2 二叉树的主要性质,选择题 1、按二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6 2、深度为5的二叉树至多有（ ）个结点。 A、16 B、31 C、32 D、10 3、对一个满二叉树，m个树叶，n个结点，深度为h，则（ ）。 A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-1 答案：1（C） 2（B） 3（D）,6.2.2 二叉树的主要性质,选择题 4、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数至少为（ ）。 A、2h B、2h-1 C、2h+1 D、h+1 5、对于一棵深度为4的三叉树，最多具有（ ）个结点。

6、 A、30 B、36 C、40 D、54 答案：1（B） 2（C）,6.2.2 二叉树的主要性质,填空题 1、深度为k的完全二叉树至少有（ ）个结点，至多有（ ）个结点，若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（ ）。 2、一棵有n（n0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非叶子结点。 答案：1(2k-1, 2k-1,2k-1) 2(n/2 , n/2+1 ),6.2.2 二叉树的主要性质,6.2 二叉树,6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,6.2.3 二叉树的存储结构,1顺序存储结构 顺序存储实现：

7、 用一组连续的存储单元存放二叉树中的结点。 关系依据二叉树的性质5存储。利用数组元素的下标值确定结点在二叉树中的位置及结点间的关系。,完全二叉树的顺序存储示意：,6.2.3 二叉树的存储结构,一般二叉树的顺序存储示意：,6.2.3 二叉树的存储结构,图 一般二叉树的顺序存储结构,一棵深度为k的右单支树，需分配2k1?个存储单元。,6.2.3 二叉树的存储结构,顺序存储实现：完全二叉树和满二叉树采用顺序存储比较合适。 采用顺序存储方式的最坏情况是单分支树。 二叉树顺序存储表示 #define MAX_TREE_SIZE 100 Typedef TElemType SqBiTreeMAX_TREE

8、_SIZE; SqBiTree bt;,2链式存储结构 （1）二叉链表存储 链表中每个结点由三个域组成，结点的存储结构为： 其中，data域存放结点信息；lchild 与rchild分别存放指向左孩子和右孩子的指针。,6.2.3 二叉树的存储结构,二叉树的二叉链表示。,6.2.3 二叉树的存储结构,（2）三叉链表存储 每个结点由四个域组成，具体结构为： 其中，data、lchild以及rchild三个域的意义同二叉链表结构； parent域为指向该结点双亲结点的指针。,6.2.3 二叉树的存储结构,二叉树的三叉链表示。,6.2.3 二叉树的存储结构,二叉链表是最常用的二叉树存储方式。 二叉链表

9、存储表示 typedef struct Node ElemType data; struct Node *lchild;*rchild; BiTNode,*BiTree; BiTree bt； /bt被定义为根指针,6.2.3 二叉树的存储结构,6.2.3 二叉树的存储结构,二叉树的基本操作 （1）创建操作 （2）遍历二叉树 先序遍历、中序遍历 后序遍历、按层遍历,小 结,理解树、二叉树定义及相关术语 掌握二叉树的性质，并用性质解题 掌握二叉链表存储形式,本章内容,6.1 树的定义和基本术语,6.2 二叉树,6.3 二叉树的遍历和线索二叉树,6.4 树和森林,6.5 哈夫曼树及其应用,6.3

10、二叉树的遍历线索二叉树,6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树,6.3.1 二叉树的遍历方式,二叉树的遍历：指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 遍历是二叉树中常用到的一种操作。 通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。,6.3.1 二叉树的遍历方式,二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 先序遍历（DLR）定义： 若二叉树为空，遍历结束。否则， 访问根结点； 先序遍历根结点的左子树； 先

11、序遍历根结点的右子树。,6.3.1 二叉树的遍历方式,二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 中序遍历（LDR）定义： 若二叉树为空，遍历结束。否则， 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。,6.3.1 二叉树的遍历方式,二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 后序遍历（LRD）定义： 若二叉树为空，遍历结束。否则， 后序遍历根结点的左子树； 后序遍历根结点的右子树。 访问根结点；,6.3.1 二叉树的遍历方式,二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 层次遍历定义： 若二叉树为空，遍历结束。否则，从二叉树的第一层（根结点）开始

12、，从上至下逐层遍历，同一层，则按从左到右的顺序逐个访问结点。,6.3.1 二叉树的遍历方式,练习1： 给出下面指定二叉树的四种遍历方式下的结点序列。,6.3.1 二叉树的遍历方式,练习2： 根据给定的遍历结点序列恢复二叉树。 LDR：DCBGEAHFIJK DLR：ABCDEGFHJIK,哪些遍历组合可以唯一确定一棵二叉树？,6.3.1 二叉树的遍历方式,结论 DLR，LDR可以确定一棵二叉树； LDR，LRD可以确定一棵二叉树； LDR，层次遍历可以确定一棵二叉树,6.3.1 二叉树的遍历方式,练习3： 根据给定的遍历结点序列恢复二叉树。 LDR： B C A E D G H F I LRD

13、： C B E H G I F D A,6.3 二叉树的遍历,6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树,6.3.2 二叉树遍历的递归算法,先序遍历递归算法： void PreOrder（BiTree bt） if (bt=NULL) return; Visite（bt-data）; PreOrder（bt-lchild）; PreOrder（bt-rchild）; ,6.3.2 二叉树遍历的递归算法,中序遍历递归算法： void InOrder（BiTree bt） if (bt

14、=NULL) return; InOrder（bt-lchild）; Visite（bt-data）; InOrder（bt-rchild）; ,6.3.2 二叉树遍历的递归算法,后序遍历递归算法： void PostOrder（BiTree bt） if (bt=NULL) return; PostOrder（bt-lchild）; PostOrder（bt-rchild）; Visite（bt-data）; ,6.3.2 二叉树遍历的递归算法,根据二叉树的递归定义，很容易写出二叉树先序、中序和后序遍历的递归算法。但并非所有程序设计语言都允许递归；另一方面，递归程序虽然简洁，但可读性不好，执

15、行效率也不高。 因此，就存在如何把一个递归算法转化为非递归算法的问题。 分析二叉树的先序、中序和后序遍历的递归算法的执行过程。,6.3 二叉树的遍历,6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树,6.3.3 二叉树遍历的非递归算法,递归算法的执行过程： 从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。 先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返

16、回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。,6.3.3 二叉树遍历的非递归算法,递归算法的执行过程： 在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，可以用栈来帮助实现这一遍历路线。 先序遍历过程：先访问结点，将该结点入栈，然后沿左子树深入，深入一个结点同样重复刚才过程；当沿左分支深入不下去时，则返回，即从栈中弹出一个结点，然后从该结点的右子树开始继续深入；仍为访问、入栈、继续深入，深入不下去时再返回，直到栈中无结点为止。,6.3.3 二叉树遍历的非递归算法,先序遍历的非递归算法： 说明：二叉树以二叉链表形式存放； 定义一个顺序栈SeqStack s; voi

17、d NRPreOrder（BiTree bt） SeqStack s; Init_SeqStack( s ); if (bt=NULL) return; BiTNode *p=bt;,6.3.3 二叉树遍历的非递归算法,while( !(p=NULL /*访问右子树*/ ,6.3.3 二叉树遍历的非递归算法,中序遍历的非递归算法： 与先序遍历过程比较，中序的区别就是每次返回时访问结点。 后序遍历的非递归算法： 与先序遍历过程比较，结点在第二次出栈时访问。结点第一次出栈只表示访问完该结点的左子树，还需再次入栈，第二次出栈才表示该结点的右子树也访问完毕，该遍历该结点。,6.3.3 二叉树遍历的非递

18、归算法,中序遍历和后序遍历的非递归算法自己编写。 不用栈实现非递归算法的方法 三叉链表； 利用线索二叉树,6.3 二叉树的遍历,6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树,6.3.4 二叉树的层次遍历算法,层次遍历实现算法 分析层次遍历过程 在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问。 符合队列特征,6.3.4 二叉树的层次遍历算法,层次遍历实现算法 设一个队列，遍历从二叉树的根结点开始，首先将

19、根结点入队，执行下面两个操作： 出队一个结点，访问该结点； 若该结点的左、右孩子结点非空，则将其左孩子和右孩子结点顺序入队。 直到队列为空时，层次遍历结束。,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( !Empty_Queue(Q) Out_Queue(Q,p);

20、printf(“%c”,p-data); 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.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树,6.3.5 线索二叉树,1线索二叉树的定义 为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息。 利用二叉树的二叉链表存储结构中的空指针域来保存该结点的直接前驱结点和直接后继结点，该指针被称为线索（thread），加了线索的二叉树称为线索二叉树。 注意： ,2画线索二叉树 线索树有