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

第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 1 数据结构 第六章 树和二叉树 * 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 2 A B CD EFGHI J KL M 树 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 3 6.1 树的类型定义 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 否则: （1）在D中存在唯一的称为根的数据元素root, （2）当n1时，其余结点可分为m(m0)个互不相交的 有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵符 合本定义的树，称为根root的子树。 基本操作： 查找： Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); TreeEmpty(T); TreeDepth(T); TraverseTree(T, Visit( ); 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 4 6.1 树的类型定义 插入： InitTree( CreateTree( Assign(T, cur_e, value); InsertChild( 删除： ClearTree( DestroyTree( DeleteChild( DestroyTree( 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 5 6.1 树的类型定义 和线性结构的比较 线性结构 树结构 第一个数据元素(无前驱)； 根结点(无前驱)； 最后一个数据元素(无后继)； 多个叶子结点(无后继)； 其它数据元素 树中其它结点 (一个前驱、一个后继) 。 (一个前驱、多个后继)。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 6 A B CD EFGHI J KL M 树形表示 A (B (E (K, L), F), C(G ), D( H( M), I, J) 嵌套括号表示法 树的表示方法： I J F K L G M C C DB E A 文氏图 凹入表 A B F E K L C D H I G M J 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 7 基本术语 结点: 数据元素 + 若干指向子树的分支。 结点的度: 分支的个数。 树的度: 树中所有结点的度的最大值。 叶子结点: 度为零的结点。 分支结点: 度大于零的结点； 路径和路径长度。 孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点 、子孙结点。 边：双亲节点x到子结点y的有序对(x，y)。 结点的层次: 假设根结点的层次为1，第i 层的结点的 子树根结点的层次为i+1。规定根的层数为0。 树的深度：树中叶子结点所在的最大层次。 森林：是m（m0）棵互不相交的树的集合任何一棵 非空树是一个二元组Tree = （root，F）其中： root被称为根结点，F被称为子树森林。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 8 6.2 二叉树的类型定义 二叉树的定义 定义：二叉树是由n(n=0)个结点的有限集合构 成，此集合或者为空集，或者由一个根结点及两棵互 不相交的左右子树组成，并且左右子树都是二叉树。 与树的关系：这也是一个递归定义。 区别： 二叉树结点的子树要区分左子树和右 子树，即使只有一棵子树也要进行区分，说明它是左 子树，还是右子树。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 9 (a) 空二叉树 A (b) 根和空的 左右子树 A B (c) 根和左子树 二叉树的5种基本形态 A (d) 根和右子树 B A (e) 根和左右子树 BC 第六章第六章 6.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); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); 插入： InitBiTree( Assign(T, CreateBiTree( InsertChild(T, p, LR, c); 删除： ClearBiTree( DestroyBiTree( DeleteChild(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个结点。由于二叉树每个结点的度最大为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的二叉树的最大的结点时为二叉 树中每层上的最大结点数之和，由性质1得到每层上的 最大结点数2i-1（第i层上的最大结点数） 二叉树的重要特性： 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 13 二叉树的重要特性： 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度 为2的结点数为n2，则n0n21。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点 数为N，因为二叉树中所有结点均小于或等于2，所以有 ： Nn0n1n2 （1） 再看二叉树中的分支数，除根结点外，其余结点都 有一个进入分支，设B为二叉树中的分支总数， 则有：N B1。由于这些分支都是由度为1和2的结点射出的， 所以有：Bn1+2*n2 NB1n12n21 （2) 由式（1）和（2）得到： n0+n1+n2=n1+2*n2+1 n0n21 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 14 满二叉树 2 45 3 6 7 1 1 23 4 56 (a)完全二叉树 1 2 3 4 5 7 (b)非完全二叉树 1 2 3 6 7 ( c)非完全二叉树 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 15 两种特殊形态的二叉树： 一棵深度为k且由2k-1个结点的二叉树称为满二叉树 。 如果深度为k、由n个结点的二叉树中各结点能够与深 度为k的顺序编号的满二叉树从1到n标号的结点相对应 ，则称这样的二叉树为完全二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为h，则 其左子树的最大层次为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-111，则其双亲是结点i/2。 （2）如果2in，则结点i为叶子结点，无左孩子；否 则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩 子是结点2i1。 证明：略！ 完全二叉树的特点: 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 18 6.3 二叉树的存储结构 1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素 。因此，必须把二叉树的所有结点安排成为一个恰当的 序列，结点在这个序列中的相互位置能反映出结点之间 的逻辑关系，用编号的方法： #define max-tree-size 100 Typedef telemtype sqbitreemax-tree-size; Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有 结点编号。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 19 L K J I H G F E D C B A 1 2 3 4 5 6 7 8 9 10 11 12 完全二叉树 A B C D EF G HIJKL 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 20 A B C D E FG 表示该处没有元素 存在仅仅为了好理解 ABCDEFG 一般二叉树 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 21 1.顺序存储结构 缺点：有可能对存储空间造成极大的浪费，在最 坏的情况下，一个深度为H且只有H个结点的右单支树 确需要2h-1个结点存储空间。而且，若经常需要插入与 删除树中结点时，顺序存储方式不是很好！ 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 22 1.顺序存储结构 A B C D index 01 234 5 6 78 9 10 11 12 13 14 15 AB C D- 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 23 lchildDatarchild A B C D E F G H （2）二叉链表法 A B C DE FGH 第六章第六章 6.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）二叉链表法 二叉树的二叉链表存储表示 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 25 Status CreateBiTree(BiTree *T) /*创建一棵二叉树*/ scanf( if(ch= =“) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Tdata=ch; CreateBiTree(Tlchild); CreateBiTree(Trchildd); return OK; 6.3 二叉树的存储结构 链式存储结构的算法： 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 26 三叉链表法 A BC DE FGH D B C E F G H A rchil d pare nt dat a lchil d 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 27 Typedef struct TBiTNode TelemType data; struct TBiTNode *lchild,*rchild,*parent; BiTNode,*BiTree; 三叉链表法 二叉树的三叉链表存储表示 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 28 6.4 二叉树的遍历 一、问题的提出 顺着某一条搜索路径巡访二叉树中的结点，使得每 个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。 对“二叉树”而言，可以有三条搜索路径： 1先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 29 6.4 二叉树的遍历 二、先左后右的遍历算法 先（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 中（根）序的遍历算法： 若二叉树为空树,则空操作；否则,（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树 。 后（根）序的遍历算法： 若二叉树为空树,则空操作;否则,（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 30 6.4 二叉树的遍历 示例 / - ab cd 图1 (a-b)/(c+d) / bc a - + d 图2 a-(b/c+d) / bc a - + d 图3 a-b/c+d 先序：/-ab+cd 中序：a-b/c+d 后序：ab-cd+/ 先序：-a+/bcd 中序：a-b/c+d 后序：abc/d+- 先序：+-a/bcd 中序：a-b/c+d 后序：abc/-d+ 分别称为表达式的前缀表示法、中缀表示法和后缀表示 法（逆波兰表示法）。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 31 6.4 二叉树的遍历 三、算法的递归描述 void Preorder (BiTree T, void( *visit)(TElemType / 访问结点 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 visit(T-data）; / 访问结点 InOrderTraverse (T-rchild, visit); void PostOrderTraverse (BiTree T, void( *visit)(TElemType PostOrderTraverse (T-rchild, visit); visit(T-data）; / 访问结点 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 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 topn 9 then 调用 栈满 10 else stop=p，p=lchild（p） 11 if top！=0 12 p=stop; top-; p=rchild（p） 13while( top=0 7 top+; 8 if topn 9 then 调用 栈满 10 else stop=p，p=lchild（p） 11 if top！=0 12 p=stop; top-; p=rchild（p） 13while( top=0 p=Lchild(p) 8 if top!=0 9 then p=stop, top- 10 输出 data(p) 11 pn ) 6 then 调用 栈满 7 else stop=p; p=Lchild(p) 8 if top!=0 9 then p=stop, top- 10 输出 data(p) 11 plchild) CountLeaf( T-lchild, 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 = 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 *GetTreeNode(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、复制二叉树(后序遍历) 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 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 41 6.5 线索二叉树 一、何谓线索二叉树？ 遍历二叉树是按一定的规则将二叉树中结点排列成 一个线性序列；这实际上是把一个非线性结构进行线性 化的操作。 以二叉链表作为存储结构时，对于某个结点只能找 到其左右孩子，而不能直接得到结点在任一序列中的前 驱或后继。要想得到只能通过遍历的动态过程才行。 怎样保存遍历过程中得到的信息呢？ （1增加两个指针 （2利用结构中的空链域，并设立标志。即采用如 下的形式： lchild ltag data rtagrchild 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 42 6.5 线索二叉树 何谓线索二叉树？ 指向该线性序列中的“前驱”和“后继”的指针，称作“线 索”。包含“线索”的存储结构，称作“线索链表”；与其相 应的二叉树，称作“线索二叉树”。 对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域，并作如下规定 ： 若该结点的左子树不空，则lchild域的指针指向其左子 树，且左标志域 ltag的值为0； 否则，lchild域的指针指向其“前驱”，且左标志ltag的 值为1。 若该结点的右子树不空，则rchild域的指针指向其右子 树，且右标志域rtag的值为0； 否则，rchild域的指针指向其“后继”，且右标志rtag的 值为1。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 43 6.5 线索二叉树 0 A 0 1B 00D 1 1C 11E 1 T A DB EC 中序序列：BCAED 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 44 6.5 线索二叉树 线索链表的结构描述： typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索 typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree; 6.5 线索二叉树 找结点的后继 线索化：对二叉树以某种次序遍历使其变为线索二叉树的 过程叫做线索化。 下面以中序为例看看如何在线索二叉树中找结点的后继。 （1树中所有叶子结点和只有左子树的右指针均为线索， 直接指示了结点的后继； （2其他非终端结点的右链均为指针，无法得到后继的信 息。然而根据中序遍历的规律可知，结点的后继应是遍历其右 子树时访问的第一个结点，即右子树中最左下的结点。 （3反之，在中序线索树中找结点前驱的规律是：若左标 志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子 树时最后访问的结点（左子树中最右下的结点为其前驱)。 A B C E I D H F G GK null null 6.5 线索二叉树 找结点的后继 在后序线索树中找结点x的后继较复杂，可分三种情况： （1若结点x是二叉树的根,则其后继为空; （2若结点x是其双亲的右孩子或是左孩子且其双亲没有 右子树,则其后继即为双亲结点。 （3若结点x是其双亲的左孩子，且其双亲有右子树，则 其后继为双亲的右子树上按后序遍历出的第一个结点。 由此可见，在后序线索化树上找后继时需知道结点的双亲 ，因此需要使用三叉链表。 可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度 也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中 需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继 ，则应采用线索链表作存储结构。 6.5 线索二叉树 二、线索链表的遍历算法: for ( p = firstNode(T); p; p = Succ(p) ) Visit(p); 中序线索化链表的遍历算法: 中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继 ？ A B C E I D H F G GK null null 6.5 线索二叉树 二、线索链表的遍历算法: Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) / T指向头结点，头 结点的左链lchild指向根结点，头结点的右链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=Thread Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根 return OK; / InOrderTraverse_Thr T - + / * - a b e f c d 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 49 6.5 线索二叉树 三、如何建立线索链表？ 在中序遍历过程中修改结点的左、右指针域， 以保存当前访问结点的“前驱”和“后继”信息。 遍历过程中，附设指针pre,并始终保持指针pre 指向当前访问的、指针p所指结点的前驱。 6.5 线索二叉树 三、如何建立线索链表？ Status InOrderThreading(BiThrTree 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 = Thread; / 最后一个结点线索化 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; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreading 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 52 6.6 树和森林 一、树的三种存储结构 1. 双亲表示法: 在这种表示中，容易找到父结点及其所有的祖先； 也能找到结点的子女和兄弟（虽然比较麻烦）。但它没有 表示出结点之间的左右次序，所以无法求树中某个指定结 点的最左子结点和右兄弟结点等基本运算。 A B CD EFGHI J KL M8M 5L 5K 4J 4I 4H 3G 2F 2E 1D 1C 1B -1A 1 2 3 4 5 6 7 8 9 10 11 12 13 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 53 一、树的三种存储结构 1. 双亲表示法: 用一组连续空间存储树的结点，并附设一个指 示器指示其双亲结点的位置。结构类型如下： #define MAX_TREE_SIZE 100 结点结构: typedef struct PTNode /* 树中结点结构 */ Elem data; /* 结点中的元素 */ int parent; / 双亲位置域 PTNode; 树结构: typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree 一、树的三种存储结构 2. 孩子链表表示法: A B CD EFGHI J KL M M L K J I H G F E D C B A1 2 3 4 5 6 7 8 9 10 11 12 13 234 56 13 7 8910 1112 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 55 一、树的三种存储结构 2、孩子链表表示法: 结点表中的每一元素又包含一个子表，存放该结点 的所有子结点。结点表顺序存放，子表用链接表示，子 表中的元素按从左到右的次序存放。结构类型如下： 双亲结点结构 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox; 树结构: typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree; 孩子结点结构: typedef struct CTNode int child; struct CTNode *next; *ChildPtr; 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 56 一、树的三种存储结构 带双亲的孩子链表表示法: A B CD EFGHI J KL M 222 56 13 7 8910 1112 8 M 5 L 5 K 4 J 4 I 4 H 3 G 2 F 2 E 1 D 1 C 1 B - 1 A1 2 3 4 5 6 7 8 9 10 11 12 13 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 57 一、树的三种存储结构 3、树的二叉链表(孩子-兄弟）存储表示法 typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; A B CD EFGHI J KL M A BCD E K F GH MI J L 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 58 二、树、树林与二叉树的转换 1、树、树林转换为二叉树 由于树和二叉树都可以用二叉链表作存储结构 ，则以二叉链表作媒介可以导出树与二叉树之间的 一个对应关系。 从二叉链表表示的定义可知，任何一棵和树对 应的二叉树，其右子树必空。这样，若把森林中第 二棵树的根结点看成是第一棵树的兄弟，则可以导 出森林和二叉树之间的对应关系。 第六章第六章 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 树转换为二叉树 事例 A B ED C HJ I G F A B ED C HJ I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 61 树转换为二叉树 事例 A B ED C HJ I G F A B E D C H J I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 62 2、森林转换成二叉树 转换规则： 如果FT1, T2, , Tm是森林，则可按如下规则 转换成一棵二叉树Broot, LB, RB。 （1）若F为空，则B为空树； （2）若F非空，则B的根root为森林中第一棵树 的根Root(T1)，B的左子树LB是从T1中根结点的子树 森林F1T11, T12, T1m1转换而成的二叉树；其右子 树RB是从森林FT2, T3, , Tm转换而成的二叉树 。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 63 A B E G C D F HI A B E G C DF HI A B E GC D F H I 2、森林转换成二叉树 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 64 3、二叉树转换为树 转换规则： 1.对有左子树的所有结点与其左孩子的右链上的 所有结点进行连接； 2.删除以前所有的旧右链。 A B E D C H J I G F A B E D C H J I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 65 4、二叉树转换成森林 转换规则： 如果Broot, LB, RB 是一棵二叉树，则可按如 下规则转换成森林FT1, T2, , Tm （1）若B为空，则F为空树； （2）若B非空，则为森林中第一棵树的根Root（ T1）即为 B的根root， T1中根结点的子树森林F1 T11, T12, T1m1 是有B的左子树LB转换而来的森林 ；F中除T1之外的其余树组成的森林FT2, T3, , Tm是由B的右子树转换而成的。 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 66 二叉树转换成森林 示例 A B C FD G E H I A B C F D G E HI 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 67 若树T为空, 返回；否则 访问T的根结点； 依次先根次序遍历各子树T1、 T2Tm； 右图遍历结果为：右图遍历结果为： A B D E H I J C F GA B D E H I J C F G 三、 树和森林的遍历 (1) 先根次序遍历的规则： A B ED C HJ I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 68 若树T为空，返回；否则 依次后根次序遍历各子树T1、 T2Tm； 访问根结点。 右图遍历结果为：右图遍历结果为： D H I J E B F G C AD H I J E B F G C A 树的遍历 (2) 后根次序遍历的规则： A B ED C HJ I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.7 哈夫曼 树与哈夫曼 编码 69 若树T为空，返回；否则 访问根结点； 若第1,i(i1）层结点已被访 问，则从左到右依次访问i+1层结点 ； 右图遍历结果为：右图遍历结果为： A B C D E F G H I JA B C D E F G H I J 树的遍历 (3) 广度优先遍历(层次序遍历) ： A B ED C HJ I G F 第六章第六章 6.1 树的类 型定义 6.2 二叉树 的类型定义 6.3 二叉树 的存储结构 6.4 二叉树 的遍历 6.5 线索二 叉树 6.6 树和森 林 6.