数据结构课件(树和二叉树)课件

《数据结构课件(树和二叉树)课件》由会员分享，可在线阅读，更多相关《数据结构课件(树和二叉树)课件（93页珍藏版）》请在装配图网上搜索。

1、6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 1数据结构课件(树和二叉树)数据结构数据结构第六章第六章 树和二叉树树和二叉树2022-6-26.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 2数据结构课件(树和二叉树)ABCDEFGHIJKLM树树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.

2、6 树和森林 6.7 哈夫曼树与哈夫曼编码 3数据结构课件(树和二叉树)6.1 6.1 树的类型定义树的类型定义数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R： 若若D为空集，则称为空树；为空集，则称为空树； 否则否则:（1）在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,（2）当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不相交的个互不相交的有限集有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵符其中每一棵子集本身又是一棵符合本定义的树，称为根合本定义的树，称为根root的子树。的子树

3、。基本操作：基本操作：查找：查找： Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); TreeEmpty(T); T r e e D e p t h ( T ) ; TraverseTree(T, Visit( );6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 4数据结构课件(树和二叉树)6.1 6.1 树的类型定义树的类型定义插入：插入： InitTree(&T); CreateTree(&T,

4、definition); Assign(T, cur_e, value); InsertChild(&T, &p, i, c);删除：删除： ClearTree(&T); DestroyTree(&T); DeleteChild(&T, &p, i); DestroyTree(&T);6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 5数据结构课件(树和二叉树)6.1 6.1 树的类型定义树的类型定义和线性结构的比较和线性结构的比较 线性结构线性结构 树结构树结构第一个数据元素第一

5、个数据元素(无前驱无前驱)； 根结点根结点(无前驱无前驱)；最后一个数据元素最后一个数据元素(无后继无后继)； 多个叶子结点多个叶子结点(无后继无后继)；其它数据元素其它数据元素 树中其它结点树中其它结点(一个前驱、一个后继一个前驱、一个后继) 。 (一个前驱、多个后继一个前驱、多个后继)。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 6数据结构课件(树和二叉树)ABCDEFGHIJKLM树形表示树形表示A (B (E (K, L), F), C(G ), D( H( M),

6、I, J)嵌套括号表示法嵌套括号表示法树的表示方法：树的表示方法： I JFKLGMCCDBEA文氏图文氏图凹入表凹入表ABFEKLCDHIGMJ6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 7数据结构课件(树和二叉树)基本术语基本术语结点结点: 数据元素数据元素 + 若干指向子树的分支。若干指向子树的分支。结点的度结点的度: 分支的个数。分支的个数。树的度树的度: 树中所有结点的度的最大值。树中所有结点的度的最大值。叶子结点叶子结点: 度为零的结点。度为零的结点。分支结点分支

7、结点: 度大于零的结点；度大于零的结点； 路径路径和和路径长度路径长度。孩子孩子结点、结点、双亲双亲结点、结点、兄弟兄弟结点、堂兄弟、结点、堂兄弟、祖先祖先结点、结点、子孙子孙结点。结点。边边：双亲节点：双亲节点x到子结点到子结点y的有序对的有序对(x，y)。结点的层次结点的层次: 假设根结点的层次为假设根结点的层次为1，第，第i 层的结点的层的结点的子树根结点的层次为子树根结点的层次为i+1。规定根的层数为规定根的层数为0。树的深度：树的深度：树中叶子结点所在的最大层次。树中叶子结点所在的最大层次。 森林：森林：是是m（m0）棵互不相交的树的集合任何一棵）棵互不相交的树的集合任何一棵非空树是

8、一个二元组非空树是一个二元组Tree = （root，F）其中：其中：root被称为根结点，被称为根结点，F被称为子树森林。被称为子树森林。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 8数据结构课件(树和二叉树)6.2 6.2 二叉树的类型定义二叉树的类型定义二叉树的定义二叉树的定义定义：定义：二叉树是由二叉树是由n(n=0)个结点的有限集合构个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并

9、且左右子树都是二叉树。不相交的左右子树组成，并且左右子树都是二叉树。与树的关系：与树的关系：这也是一个递归定义。这也是一个递归定义。区别区别： 二叉树结点的子树要区分左子树和右二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。子树，还是右子树。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 9数据结构课件(树和二叉树)(a)空二叉树空二叉树A (b)根和空的根和空的左右子树左右子树AB (

10、c)根和左子树根和左子树二叉树的二叉树的5 5种基本形态种基本形态A(d)根和右子树根和右子树BA (e)根和左右子树根和左右子树BC6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 10数据结构课件(树和二叉树)二叉树的主要基本操作：二叉树的主要基本操作：查找：查找： Root(T); Value(T, e);Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e)

11、; BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();插入：插入： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);删除：删除： ClearBiTree(&T); DestroyBiTree(&T); Delete

12、Child(T, p, LR); 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 11数据结构课件(树和二叉树)性质性质1： 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i=1)。 证明：证明：采用归纳法证明此性质。采用归纳法证明此性质。当当i=1时，只有一个根结点，时，只有一个根结点，2i-1=20 =1,命题成立。命题成立。现在假定第现在假定第i1层上命题成立，则第层上命题成立，则第i1层上至层上至多有多有2i-2个结点。由于二叉树每个结点的度最大为个

13、结点。由于二叉树每个结点的度最大为2，故在第故在第i层上最大结点数为第层上最大结点数为第i1层上最大结点数的二层上最大结点数的二倍，倍， 即即22i-22i-1。命题得到证明。命题得到证明。二叉树的重要特性：二叉树的重要特性：6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 12数据结构课件(树和二叉树)性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有2k1个结点（个结点（k=1).证明：证明：深度为深度为k的二叉树的最大的结点时为二叉的二叉树的最大的结点时为二叉树中每层上

14、的最大结点数之和，由性质树中每层上的最大结点数之和，由性质1得到每层上的得到每层上的最大结点数最大结点数2i-1（第（第i层上的最大结点数）层上的最大结点数）二叉树的重要特性：二叉树的重要特性：12k1i1i2k6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 13数据结构课件(树和二叉树)二叉树的重要特性：二叉树的重要特性：性质性质3： 对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n0，度为度为2的结点数为的结点数为n2，则，则n0n21。证明：证明：

15、设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点，二叉树中总结点数为数为N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2，所以有：，所以有：Nn0n1n2 （1） 再看二叉树中的分支数，除根结点外，其余结点都再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设有一个进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数， 则有：则有：NB1。由于这些分支都是由度为。由于这些分支都是由度为1和和2的结点射出的，的结点射出的，所以有：所以有：Bn1+2*n2 NB1n12n21 （2)由式（由式（1）和（）和（2）得到：）得到： n0+n1

16、+n2=n1+2*n2+1 n0n216.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 14数据结构课件(树和二叉树)满二叉树满二叉树2453671123456(a)完全二叉树完全二叉树123457(b)非完全二叉树非完全二叉树12367( c)非完全二叉树非完全二叉树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 15数据结构课件(树和二叉树)两种特殊形态的二叉树：

17、两种特殊形态的二叉树： 一棵深度为一棵深度为k且由且由2k-1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。如果深度为如果深度为k、由、由n个结点的二叉树中各结点能够与个结点的二叉树中各结点能够与深度为深度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相对标号的结点相对应，则称这样的二叉树为应，则称这样的二叉树为完全二叉树完全二叉树。完全二叉树的特点完全二叉树的特点是：是：（1）所有的叶结点都出现在第）所有的叶结点都出现在第k层或层或k1层。层。（2）对任一结点，如果其右子树的最大层次为）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为则其左子树的最大

18、层次为h或或h1。满二叉树和完全二叉树满二叉树和完全二叉树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 16数据结构课件(树和二叉树) 性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n1。符号符号x表示不大于表示不大于x的最大整数。的最大整数。 证明：证明：假设此二叉树的深度为假设此二叉树的深度为k，则根据性质，则根据性质2及完全及完全二叉树的定义得到：二叉树的定义得到：2k-11n=2k-1 或或 2k-1=n2k取对数得到：取对数得到：

19、k1log2nk 因为因为k是整数。所以有：是整数。所以有：klog2n1。二叉树的重要特性二叉树的重要特性6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 17数据结构课件(树和二叉树)性质性质5： 如果对一棵有如果对一棵有n个结点的完全二叉树的结点按个结点的完全二叉树的结点按层序编号（从第层序编号（从第1层到第层到第log2n+1层，每层从左到右层，每层从左到右),则则对任一结点对任一结点i（1=i1，则其双亲是结点，则其双亲是结点i/2。 （2）如果）如果2in，则结点，则结

20、点i为叶子结点，无左孩子；否为叶子结点，无左孩子；否则，其左孩子是结点则，其左孩子是结点2i。 （3）如果）如果2i1n，则结点，则结点i无右孩子；否则，其右孩无右孩子；否则，其右孩子是结点子是结点2i1。证明：略！证明：略！完全二叉树的特点完全二叉树的特点: :6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 18数据结构课件(树和二叉树)6.3 6.3 二叉树的存储结构二叉树的存储结构1.顺序存储结构顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。它是用一组连续的存储

21、单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有从树根起，自上层至下层，每层自左至右的给所有结点编号。结点编号。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结

22、构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 19数据结构课件(树和二叉树)LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树ABCDEFGHIJKL6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 20数据结构课件(树和二叉树)ABCDEFG 表示该处没有元素表示该处没有元素存在仅仅为了好理解存在仅仅为了好理解ABCDEFG一般二叉树一般二叉树6.1 树的类型定义 6.2 二叉树的类型

23、定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 21数据结构课件(树和二叉树)1.1.顺序存储结构顺序存储结构缺点：缺点：有可能对存储空间造成极大的浪费，在最有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为坏的情况下，一个深度为H且只有且只有H个结点的个结点的右单支树右单支树确需要确需要2h-1个结点存储空间。而且，若经常需要插入与个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！删除树中结点时，顺序存储方式不是很好！6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储

24、结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 22数据结构课件(树和二叉树)1.1.顺序存储结构顺序存储结构ABCDindexindex 0 01 1 2 23 34 4 5 5 6 6 7 78 8 9 9 1010 1111 1212 1313 1414 1515A A B B C C D D- - - -6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 23数据结构课件(树和二叉树)lchildDatarchildABCDEF

25、GH（2 2）二叉链表法）二叉链表法ABCDEFGH6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 24数据结构课件(树和二叉树)Typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;2 2）二叉链表法）二叉链表法二叉树的二叉链表存储表示二叉树的二叉链表存储表示6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5

26、 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 25数据结构课件(树和二叉树)Status CreateBiTree(BiTree *T) /*创建一棵二叉树创建一棵二叉树*/ scanf(&ch); if(ch= =) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Tdata=ch; CreateBiTree(Tlchild); CreateBiTree(Trchildd); return OK; 6.3 6.3 二叉树的存储结构二叉树的存储结构链式存储结构的算法：链式存储结构的算法：

27、6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 26数据结构课件(树和二叉树)三叉链表法三叉链表法ABCDEFGHDBCEFGHArchildparentdatalchild6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 27数据结构课件(树和二叉树)Typedef struct TBiTNode TelemType data; struct TBiTNode *l

28、child,*rchild,*parent; BiTNode,*BiTree;三叉链表法三叉链表法二叉树的三叉链表存储表示二叉树的三叉链表存储表示6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 28数据结构课件(树和二叉树)6.4 6.4 二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出顺着某一条搜索路径巡访二叉树中的结点，使得每顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。个结点均被访问一次，而且仅被访问一次。“访问访问”的含义可以很广，

29、如：输出结点的信息的含义可以很广，如：输出结点的信息等。等。 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1先上后下的按层次遍历；先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。先右（子树）后左（子树）的遍历。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 29数据结构课件(树和二叉树)6.4 6.4 二叉树的遍历二叉树的遍历二、先左后右的遍历算法二、先左后右的遍历算法 先（根）

30、序的遍历算法：先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点； （2）先序遍历左子树；）先序遍历左子树； （3）先序遍历右子树。）先序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：若二叉树为空树若二叉树为空树,则空操作；否则则空操作；否则,（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点； （3）中序遍历右子树。）中序遍历右子树。后（根）序的遍历算法：后（根）序的遍历算法：若二叉树为空树若二叉树为空树,则空操作则空操作;否则否则,（1）后序遍历左子树；）后序遍历左子树； （2）后序遍历右子树

31、；）后序遍历右子树； （3）访问根结点。）访问根结点。 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 30数据结构课件(树和二叉树)6.4 6.4 二叉树的遍历二叉树的遍历示例示例/-abcd图图1 (a-b)/(c+d)/bca-+d图图2 a-(b/c+d)/bca-+d图图3 a-b/c+d先序：先序：/-ab+cd中序：中序：a-b/c+d后序：后序：ab-cd+/先序：先序：-a+/bcd中序：中序：a-b/c+d后序：后序：abc/d+-先序：先序：+-a/bcd中

32、序：中序：a-b/c+d后序：后序：abc/-d+分别称为表达式的前缀表示法、中缀表示法和后缀表示分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。法（逆波兰表示法）。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 31数据结构课件(树和二叉树)6.4 6.4 二叉树的遍历二叉树的遍历三、算法的递归描述三、算法的递归描述 void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树先序遍历二叉树 i

33、f (T) visit(T-data）; / 访问结点访问结点Preorder(T-lchild, visit); / 遍历左子树遍历左子树Preorder(T-rchild, visit); / 遍历右子树遍历右子树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 32数据结构课件(树和二叉树)void InOrderTraverse (BiTree T, void( *visit)(TElemType &e)/中序遍历中序遍历if(T)InOrderTraverse (T-lc

34、hild, visit); visit(T-data）; / 访问结点访问结点InOrderTraverse (T-rchild, visit);void PostOrderTraverse (BiTree T, void( *visit)(TElemType &e)/后序遍历后序遍历if(T)PostOrderTraverse (T-lchild, visit);PostOrderTraverse (T-rchild, visit); visit(T-data）; / 访问结点访问结点6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索

35、二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 33数据结构课件(树和二叉树)四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述先序遍历的非递归算法。先序遍历的非递归算法。t指向根，指向根，p为指针，指为指针，指向当前结点。使用一个堆栈向当前结点。使用一个堆栈s（），（），top为栈指针为栈指针 1 if t=NULL 2 then 输出输出 这是一棵空树这是一棵空树 3 else p=t，top=0 4 DO 5 while p！=NULL 6 输出输出 data（p）; 7 top+;8 if topn9 then 调用调用 栈满栈满 10 else stop=p，p=lch

36、ild（p）11 if top！=012 p=stop; top-; p=rchild（p）13while( top=0 & p=null)算法结束算法结束数据结构课件(树和二叉树)6.4 6.4 二叉树的遍历二叉树的遍历四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述1 if t=NULL2 then 输出输出 这是一棵空树这是一棵空树 3 else p=t，top=0 4 DO 5 while p！=NULL 6 输出输出 data（p）;7 top+;8 if topn9 then 调用调用 栈满栈满10 else stop=p，p=lchild（p）11 if top！=012

37、 p=stop; top-; p=rchild（p）13while( top=0 & p=null)算法结束算法结束注注:结点旁结点旁的数字是的数字是该结点的该结点的存储地址存储地址二叉树执行先序遍历二叉树执行先序遍历算法的过程算法的过程栈栈6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 35数据结构课件(树和二叉树)中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法，使用堆栈中序遍历的非递归算法，使用堆栈s（），（），top为指针，为指针，t指向根，指向根，p为指针，

38、指向当前结点为指针，指向当前结点1 top=0,p=t2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn )6 then 调用调用 栈满栈满7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 输出输出 data(p) 11 pn )6 then 调用调用 栈满栈满7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 输出输出 data(p) 11 plchild)& (!T-rchild)count+;CountLeaf( T-lch

39、ild, count); / 统计左子树中叶子结点个数统计左子树中叶子结点个数CountLeaf( T-rchild, count);/ 统计右子树中叶子结点个数统计右子树中叶子结点个数6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 38数据结构课件(树和二叉树)五、遍历算法的应用举例五、遍历算法的应用举例2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft

40、= Depth( T-lchild );depthRight= Depth( T-rchild );depthval = 1+(depthLeft depthRight? depthLeft:depthRight); return depthval; 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 39数据结构课件(树和二叉树)五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二叉树(后序遍历后序遍历)/ 生成一个二叉树的结点生成一个二叉树的结点BiTNode *G

41、etTreeNode(TElemType item,BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode)exit(1); T- data = item; T- lchild = lptr； T- rchild = rptr; return T;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 40数据结构课件(树和二叉树)五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二

42、叉树(后序遍历后序遍历)BiTNode *CopyTree(BiTNode *T) if (!T )return NULL;if (T-lchild ) newlptr = CopyTree(T-lchild);else newlptr = NULL;if (T-rchild ) newrptr = CopyTree(T-rchild);else newrptr = NULL;newnode = GetTreeNode(T-data, newlptr, newrptr);return newnode;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历

43、 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 41数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树是按一定的规则将二叉树中结点排列成遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性一个线性序列；这实际上是把一个非线性结构进行线性化的操作。化的操作。以二叉链表作为存储结构时，对于某个结点只能找以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继。要想得到只能通过遍历的动态

44、过程才行。驱或后继。要想得到只能通过遍历的动态过程才行。怎样保存遍历过程中得到的信息呢？怎样保存遍历过程中得到的信息呢？（1增加两个指针增加两个指针（2利用结构中的空链域，并设立标志。即采用如利用结构中的空链域，并设立标志。即采用如下的形式：下的形式：lchild ltagdatartagrchild6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 42数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树何谓线索二叉树？何谓线索二叉树？ 指向该线性序列中的指向该线性序列中

45、的“前驱前驱”和和“后继后继”的的指针指针，称，称作作“线索线索”。包含。包含“线索线索”的存储结构，称作的存储结构，称作“线索链线索链表表”；与其相应的二叉树，称作；与其相应的二叉树，称作“线索二叉树线索二叉树”。对线索链表中结点的约定：对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则若该结点的左子树不空，则lchild域的指针指向其域的指针指向其左子左子树树，且左标志域，且左标志域 ltag的值为的值为0； 否则，否则，lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志，且左标志lt

46、ag的值的值为为1。若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右域的指针指向其右子树，且右标志域子树，且右标志域rtag的值为的值为0；否则，否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志，且右标志rtag的值为的值为1。 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 43数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树0 A 01B 00D 1 1C 11E 1TADBEC中序序列：中序序列：BCAED6.1

47、 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 44数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树线索链表的结构描述：线索链表的结构描述：typedef enum Link, Thread PointerThr; / Link=0:指针，指针，Thread=1:线索线索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild, *rchild; / 左右指针左右指针PointerThr LTag, R

48、Tag; / 左右标志左右标志 BiThrNode, *BiThrTree;数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继线索化线索化：对二叉树以某种次序遍历使其变为线索二叉树的：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做过程叫做线索化线索化。下面以下面以中序中序为例看看如何在线索二叉树中为例看看如何在线索二叉树中找结点的后继找结点的后继。（1树中所有叶子结点和只有左子树的右指针均为线索，树中所有叶子结点和只有左子树的右指针均为线索，直接指示了结点的后继；直接指示了结点的后继；（2其他非终端结点的右链均为指针，无法得到后继的信其他非终端结点的右链

49、均为指针，无法得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。子树时访问的第一个结点，即右子树中最左下的结点。（3反之，在中序线索树中找结点前驱的规律是：若左标反之，在中序线索树中找结点前驱的规律是：若左标志是志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子，则左链为线索，指示其前驱；否则，遍历该结点的左子树时最后访问的结点（左子树中最右下的结点为其前驱树时最后访问的结点（左子树中最右下的结点为其前驱)。ABCEIDHF GGKnullnull数据结构课件(树和二叉树

50、)6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继在在后序线索树后序线索树中找结点中找结点x的后继较复杂，可分三种情况：的后继较复杂，可分三种情况：（1若结点若结点x是二叉树的根是二叉树的根,则其后继为空则其后继为空;（2若结点若结点x是其双亲的右孩子或是左孩子且其双亲没有是其双亲的右孩子或是左孩子且其双亲没有右子树右子树,则其后继即为双亲结点。则其后继即为双亲结点。（3若结点若结点x是其双亲的左孩子，且其双亲有右子树，则是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点。其后继为双亲的右子树上按后序遍历出的第一个结点。由此可见，在后序线索化树上找

51、后继时需知道结点的双亲，由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表。因此需要使用三叉链表。可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中，但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。则应采用线索链表作存储结构。数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算

52、法:for ( p = firstNode(T); p; p = Succ(p) )Visit(p);中序线索化链表的遍历算法中序线索化链表的遍历算法:中序遍历的第一个结点中序遍历的第一个结点 ？在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？ABCEIDHF GGKnullnull数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算法:Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) / T指向头结点，头指向头结点，头结点的左链结点的左链lc

53、hild指向根结点，头结点的右链指向根结点，头结点的右链rchild， 指向指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树，对每个数据元素调用函数二叉树，对每个数据元素调用函数Visit。p = T-lchild; / p指向根结点指向根结点while (p != T) / 空树或遍历结束时，空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR;/ 访问其左访问其左子树为空的结点子树为空的结点 while (p-RTag=Thr

54、ead & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问后继结点访问后继结点 p = p-rchild; / p进至其右子树根进至其右子树根 return OK; / InOrderTraverse_ThrT-+/*-abe fc d6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 49数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树三、如何建立线索链表？三、如何建立线索链表？在中序遍历过程中修改结点的左、右指针域，在中

55、序遍历过程中修改结点的左、右指针域，以保存当前访问结点的以保存当前访问结点的“前驱前驱”和和“后继后继”信息。信息。遍历过程中，附设指针遍历过程中，附设指针pre,并始终保持指针并始终保持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱。所指结点的前驱。数据结构课件(树和二叉树)6.5 6.5 线索二叉树线索二叉树三、如何建立线索链表？三、如何建立线索链表？Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 中中序遍历二叉树序遍历二叉树T，并将其中序线索化，并将其中序线索化，Thrt指向头结点。指向头结点。if (!

56、(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW);Thrt-LTag = Link; Thrt-RTag =Thread; / 建头结点建头结点Thrt-rchild = Thrt; / 右指针回指右指针回指if (!T) Thrt-lchild = Thrt; / 若二叉树空，则左指针回指若二叉树空，则左指针回指else Thrt-lchild = T; pre = Thrt;InThreading(T); / 中序遍历进行中序线索化中序遍历进行中序线索化pre-rchild = Thrt; pre-RTag = Thre

57、ad; / 最后一个结点线索化最后一个结点线索化Thrt-rchild = pre; return OK; / InOrderThreading数据结构课件(树和二叉树)void InThreading(BiThrTree p) if (p) InThreading(p-lchild); / 左子树线索化左子树线索化if (!p-lchild) p-LTag = Thread; p-lchild = pre; / 建前驱线索建前驱线索if (!pre-rchild) pre-RTag = Thread; pre-rchild = p; / 建后继线索建后继线索pre = p; / 保持保持pr

58、e指向指向p的前驱的前驱InThreading(p-rchild); / 右子树线索化右子树线索化 / InThreading6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 52数据结构课件(树和二叉树)6.6 6.6 树和森林树和森林一、树的三种存储结构一、树的三种存储结构1. 双亲表示法双亲表示法:在这种表示中，容易找到父结点及其所有的祖先；在这种表示中，容易找到父结点及其所有的祖先；也能找到结点的子女和兄弟（虽然比较麻烦）。但它没有也能找到结点的子女和兄弟（虽然比较麻烦）。

59、但它没有表示出结点之间的左右次序，所以表示出结点之间的左右次序，所以无法求树中某个指定结无法求树中某个指定结点的最左子结点和右兄弟结点等基本运算点的最左子结点和右兄弟结点等基本运算。ABCDEFGHIJKLM8M5L5K4J4I4H3G2F2E1D1C1B-1A123456789101112136.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 53数据结构课件(树和二叉树)一、一、树的三种存储结构树的三种存储结构1. 双亲表示法双亲表示法:用一组连续空间存储树的结点，并附设一个指用

60、一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：示器指示其双亲结点的位置。结构类型如下：#define MAX_TREE_SIZE 100结点结构结点结构:typedef struct PTNode /* 树中结点结构树中结点结构 */Elem data; /* 结点中的元素结点中的元素 */int parent; / 双亲位置域双亲位置域 PTNode;树结构树结构:typedef struct PTNode nodesMAX_TREE_SIZE;int r, n; / 根结点的位置和结点个数根结点的位置和结点个数 PTree数据结构课件(树和二叉树)一、树的三

61、种存储结构一、树的三种存储结构2. 孩子链表表示法孩子链表表示法:ABCDEFGHIJKLMMLKJIHGFEDCBA12345678910111213234 56 13 78910 1112 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 55数据结构课件(树和二叉树)一、树的三种存储结构一、树的三种存储结构2、孩子链表表示法、孩子链表表示法:结点表中的每一元素又包含一个子表，存放该结点结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示，子

62、的所有子结点。结点表顺序存放，子表用链接表示，子表中的元素按从左到右的次序存放。结构类型如下：表中的元素按从左到右的次序存放。结构类型如下：双亲结点结构双亲结点结构typedef struct Elem data;ChildPtr firstchild; / 孩子链的头指针孩子链的头指针 CTBox;树结构树结构:typedef struct CTBox nodesMAX_TREE_SIZE;int n, r; / 结点数和根结点的位置结点数和根结点的位置 CTree;孩子结点结构孩子结点结构:typedef struct CTNode int child;struct CTNode *nex

63、t; *ChildPtr;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 56数据结构课件(树和二叉树)一、树的三种存储结构一、树的三种存储结构带双亲的孩子链表表示法带双亲的孩子链表表示法:ABCDEFGHIJKLM222 56 13 78910 1112 8M5L5K4J4I4H3G2F2E1D1C1B-1A123456789101112136.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.

64、7 哈夫曼树与哈夫曼编码 57数据结构课件(树和二叉树)一、树的三种存储结构一、树的三种存储结构3、树的二叉链表、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法typedef struct CSNodeElem data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;ABCDEFGHIJKLMABCDEKFGHMIJL6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 58数据结构课件(树和二叉树)二、树、

65、树林与二叉树的转换二、树、树林与二叉树的转换1、树、树林转换为二叉树、树、树林转换为二叉树由于树和二叉树都可以用二叉链表作存储结构，由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。个对应关系。从二叉链表表示的定义可知，任何一棵和树对从二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。这样，若把森林中第应的二叉树，其右子树必空。这样，若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以导二棵树的根结点看成是第一棵树的兄弟，则可以导出森林和二叉树之间的对应关系。出森林和二叉树之间的对应关系

66、。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 59数据结构课件(树和二叉树)二、树、树林与二叉树的转换二、树、树林与二叉树的转换树转换为二叉树树转换为二叉树转换规则：转换规则：步骤：步骤：1.将同父亲的兄弟结点连接；将同父亲的兄弟结点连接；2.对每一个非叶结点只保留第一个孩子链，删对每一个非叶结点只保留第一个孩子链，删除其他孩子的链；除其他孩子的链；3.将树向左旋转将树向左旋转450。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 60数据结构课件(树和二叉树)树转换为二叉树树转换为二叉树事例事例ABEDCHJIGFABEDCHJIGF6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 61数据结构课件(树和二叉树)树转换为二叉树树转换为二叉树