计算机软件技术基础ppt课件.ppt

《计算机软件技术基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术基础ppt课件.ppt（145页珍藏版）》请在三一办公上搜索。

1、本章中主要介绍下列内容： 树的逻辑定义和存储结构 二叉树的逻辑定义、存储结构 二叉树的基本操作算法 树和二叉树的转换 哈夫曼树及其应用,第六章 树和二叉树,本章学习要求掌握：树和二叉树的性质，有关术语及基本概念。 掌握：二叉树的两种存储方法，重点是链式存储。掌握：各种次序的遍历算法，能灵活运用遍历算法实现二叉树的各种运算。掌握：几种建立二叉树的方法。了解：二叉树的线索化及其实质，了解在各种线索树中查找给定结点的前趋和后继的方法。了解：树、森林与二叉树之间的转换方法。了解：树的各种存储结构及其特点；树和森林的二种次序的遍历。掌握：哈夫曼树的基本概念，最优二叉树和哈夫曼编码方法。,6.1 树基本概

2、念6.2 二叉树的基本操作与存储实现6.3 二叉树的遍历6.4 线索二叉树6.5 二叉树的应用6.6 树的定义与相关术语6.7 树的基本操作与存储6.8 树、森林与二叉树的转换6.9 树和森林的遍历,6.1 树的基本概念,1.树的定义 树是一种常非线性结构树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。,递归定义的,树的几种形态,2.树的特点,（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点（2）树中所有结点可以有零个或多个后继结点,树

3、结构和非树结构的示意 图,3. 树的表示方法：,(b ) 凹入表,（a）树形表示,A,B,C,D,E,F,I,J,G,H,(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括号表示法,C,D,E,I,J,F,G,H,A,B,(c) 文氏图,4. 基本术语结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点,也叫终端结点分支结点度0的结点，也叫非终端结点结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层树的度一棵树中最大的结点度数树的深度(depth)树中结点的最大层次有序树、无序树 如果树中

4、每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林 是m（m0）棵互不相交的树的集合。,在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点兄弟(sibling)同一双亲的孩子祖先、子孙如果有一条路径从结点M到结点N，那么M就称为N的祖先，N成为M的子孙堂兄弟 双亲在同一层的结点互为堂兄弟。,叶子：K，L，F，G，M，I，J,结点B，C，D为兄弟结点K，L为兄弟,结点A的度：结点B的度：结点M的度：,结点A的孩子：结点B的孩子：,结点I的双亲：结点L的双亲：,树的度：,结

5、点A的层次：结点M的层次：,树的深度：,结点F，G为堂兄弟结点A是结点F，G的祖先,其它术语:有序树和无序树、森林,3,2,0,D,E,4,1,4,3,B，C，D,E，F,术语,结点A的度：2结点B的度：2结点M的度：0,叶子：K，L，F，M，J,结点A的孩子：B，D结点B的孩子：E，F,结点J的双亲：D结点L的双亲：E,结点B，D为兄弟结点K，L为兄弟,树的度：2,结点A的层次：1结点M的层次：4,树的深度：4,结点F，H为堂兄弟结点A是结点F，H的祖先,5. 树的基本运算常用操作： （1） 构造一个树 CreateTree (T) （2）清空以T为根的树 ClearTree(T) （3）判

6、断树是否为空 TreeEmpty(T) （4）获取给定结点的第i个孩子 Child(T,node,i) （6）获取给定结点的双亲 Parent(T,node) （6）遍历树Traverse(T) 对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依后序遍历方法依次访问每棵子树，最后访问根结点。,6.2 二叉树,6.2.1 二叉树的定义1.定义 二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互

7、不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。,递归定义的,二叉树结构的图形表示示例,G H,D E F,B C,A,2.二叉树的5种形态：,3. 二叉树的基本运算 （1） 构造一棵二叉树 CreateBTree ( BT) （2）清空以BT为根的二叉树 ClearBTree(BT) （3）判断二叉树是否为空 BTreeEmpty(BT) （4）获取给定结点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node) （5）给定结点

8、的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node) （5）获取给定结点的双亲 Parent(BT,node) （6）遍历二叉树Traverse(BT),6.2.2 二叉树性质,性质1：, 第i层上最大结点数是第i-1层的2倍，即 故命题得证,证明：用归纳法证明之,假设对所有j(1ji)命题成立，即第j层上至多有 个结点,那么，第i-1层至多有 个结点,又二叉树每个结点的度至多为2,性质2：深度为k的二叉树至多有 个结点(k1),证明：由性质1，可得深度为k 的二叉树最大结点数是,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2

9、，则n0=n2+1,证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,几种特殊形式的二叉树,满二叉树定义：,特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右

10、分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1,证明：根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有,2 k-1-1n2k-1,2 k-1 n 2k,K-1 log2n k,性质4：,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2 (2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,2i +2,2i 2i+1 2i+2 2i+

11、3 i+1 2i 2i+1,i,i i+1,6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。 1. 顺序存储结构 其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,完全二叉树的存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中,1. 顺序存储结构:用一组连续的存储单元按照完全二叉树的 每个结点编号的顺序存放结点内容。,6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。,一般二叉树的顺序存储：将一般二叉树添加虚结点转为完全二叉树，然后进行存

12、储,特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树,在C语言中，这种存储形式的类型定义如下所示：#define MaxTreeNodeNum 100typedef struct datatype dataMaxTreeNodeNum; /* 根存储在下标为1的数组单元中 */ int n; /* 当前完全二叉树的结点个数 */ QBTree;,（1）构造一棵完全二叉树void CreateBTree(QBTree *BT,DataType data ,int n) if (n= MaxTreeNodeNum) n= MaxTreeNodeNum -1; for (i=1

13、; idatai=datai; BT-n=n;,（2）获取给定结点的左孩子 int LeftCHild(QBTree BT , int node) if (2*nodeBT.n) return 0; else return 2*node;RightChild(BT,node)与这个操作类似，读者可试着自行完成。,（3）获取给定结点的双亲 int Parent(QBTree BT , int node) if (1node ,2. 链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间

14、利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示： 其中，lchild和rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。,data,2.链式存储结构二叉链表,typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild;BiTNode,*BiTree;,在n个结点的二叉链表中，有n+1个空指针域,头指针bt,带头结点的二叉链表,三叉链表:二叉链表寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结

15、点结构如下所示。,头指针bt,6.2.4 二叉树的基本操作及实现,建立一棵带头结点的空二叉树 Initiate(bt)创建二叉树 Create(x,lbt,rbt)插入左孩子 InsertL(bt,x,parent)插入右孩子 InsertR(bt,x,parent)删除只有一个结点的左子树 DeleteL(bt,parent)删除右子树 DeleteR(bt,parent)查找 Search(bt,x)遍历 Traverse(bt),typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild;BiTNode,*B

16、iTree;,6.3 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。,6.3.1按根、左子树和右子树的遍历,按根、左子树和右子树三部分进行遍历二叉树的顺序存在下面6种可能：,其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与

17、人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,二叉树的遍历方法先序遍历：若二叉树为空，则结束遍历操作；否则访问根结点；然后分别先序遍历左子树、右子树中序遍历：若二叉树为空，则结束遍历操作；否则先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：若二叉树为空，则结束遍历操作；先后序遍历左、右子树，然后访问根结点,D L R,先序遍历序列：A B D C,先序遍历:先访问根结点,然后分别先序遍历左子树、右子树,L D R,中序遍历序列：B D A C,中序遍历:先中序遍历左子树，然后访问根结点

18、，最后中序遍历右子树,L R D,后序遍历序列： D B C A,后序遍历:先后序遍历左、右子树，然后访问根结点,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,下面我们再给出两种遍历二叉树的方法： （1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。,D G B A E C H F,G H,D E F,B C,A

19、,任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。,G H,D E F,B C,A,遍历算法：由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。递归算法,void PreOrder(BiTree bt) if(bt=NULL)return； printf(%dt,bt-data); PreOrder(bt-lchild); PreOrder(bt-rchild)

20、; ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,6.3.2二叉树遍历的非递归算法,（1）先序遍历的非递归实现,可利用堆栈将递归算法改写成非递归的形式BiTree stackMAXNODE;,非递归先序遍历二叉树的主要操作：p=bt;while(1) while(p不空) visit(p-data); /进栈之前访问p结点； push(p,stack); p=p-lchild; if(栈空)return; p=pop(stack); p=p-rchild; ,访问：A,访问：AB,访问：ABC,访问：ABCD,while(p不空) visit(p-data); pu

21、sh(p,stack); p=p-lchild; ,p=pop(stack);p=p-rchild;,访问：ABCDE,访问：ABCDEG,访问：ABCDEGF,栈空结束,=bt;while(1) while(p不空) push(p,stack); p=p-lchild; if(栈空)return; p=pop(stack); visit(p-data); /出栈时访问p结点； p=p-rchild; ,（2）中序遍历的非递归实现,（3）后序遍历的非递归实现,Typedef struct BiTree link; int flag=0; /进栈的次数 stacktype;stacktype s

22、tackMAXNODE;/顺序栈stacktype XP；,结点要入两次栈，出两次栈，在第二次出栈时访问。,=bt;while(1) while(p不空) XP.link=p；XP.flag=1； push(XP,stack); /第一次进栈 p=p-lchild; if(栈空)return; XP=pop(stack);p=XP.link;sign=XP.flag; if(sign=2) /第二次出栈 visit(p-data); p=NULL; else /第一次出栈 XP.link=p；XP.flag=2； push(XP,stack); /第二次进栈 p=p-rchild;,while

23、(p不空) XP.link=p；XP.flag=1； push(XP,stack); /第一次进栈 p=p-lchild; ,XP=pop(stack);p=XP.link;sign=XP.flag; if(sign=2) /第二次出栈 visit(p-data); p=NULL; else /第一次出栈 XP.link=p；XP.flag=2； push(XP,stack); /第二次进栈 p=p-rchild;,C第一次出栈,C第二次进栈,C第二次出栈访问C,B第一次出栈第二次进栈,访问C G,访问C G E,访问C G E F D B,访问C G E F D B A,6.3.3 按层次遍

24、历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,按层次遍历该二叉树的序列为： ABCDEFGH,二叉树用顺序存储结构表示时，按层遍历的算法实现,(a)完全二叉树,(b)非完全二叉树,图 5-20,void LevelOreder(QBTree BT) for (i=1;i=BT.n;i+) if (BT.datai!=#) Visite(BT.datai);,算法实现,二叉树用链式存储结构表示时，按层遍历的算法实现 访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历

25、操作；否则重复下列操作。 取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。,在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；,void LevelOrder(BTree *BT) if (!BT) exit; InitQueue(Q); p=BT;

26、 /初始化 Visite(p); EnQueue( /处理右孩子 ,6.3.4 二叉树遍历算法的应用,二叉树是递归定义，可以写出它的递归遍历算法，同时借助遍历算法可以实现一些基本的应用，如： 节点计数、创建二叉树、计算二叉树的高度等等,1.先序遍历查找数据元素,BiTree Search(BiTree bt,datatype x) if（空树）return NULL； if(bt-data=x)return bt; P为查找左子树的结果； if（找到）return p； else P为查找右子树的结果； return p； ,2.统计二叉树中叶子结点个数算法,int countleaf(BiT

27、ree bt) if（空树）return 0； if(bt-lchild=NULL return(countleaf(bt-lchild)+countleaf(bt-right)； ,这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。,void Leaf(BTree BT , int *count) if (BT) Leaf(BT-child , /计算右子树的叶子结点个数 ,3. 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要

28、在所有空二叉树的位置上填补一个特殊的字符，比如，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。,按先序遍历序列建立二叉树的二叉链表，已知先序序列为： ABC00DE0G00F000,#typedef char datatype;void createBinTree(BiTree *t) 输入一个字符ch; if(ch=#) *t=NULL;return; *t=(BiTNode *)malloc(sizeof(BiTNod

29、e); (*t)-data=ch; createBinTree( ,4.由中序和先序遍历序列建立二叉树的二叉链表,已知先序序列为： ABCDEGF 中序序列为： CBEGDFA,设先序序列的序号范围为ij（初始情况为1n），中序序列的序号范围为kh （初始情况为1n） ；,算法过程： 创建根结点； 找到先序序列的i对应的中序序列中的位置m； 划定左、右子树的范围； 创建左子树； 创建右子树；,5.交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就

30、属于这类情况。 void change_left_right(BTree BT) if (BT) change_left_right(BT-lchild); change_left_right(BT-rchild); BT-lchildBT-rchild; ,6.求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。int hight(BTree BT) /h1和h2分别是以BT为根的左右子树的高度 if (BT=NULL) return 0; else h1=hight(BT-lchild

31、); h2=hight(BT-right); return maxh1,h2+1; ,问题的提出：二叉树中有很多闲置的指针，能否利用它们为访问二叉树提供便利，如下图所示：,如：求解某结点在某种遍历次序下的前驱或后继结点,6.4线索二叉树,6.4.1 线索的概念,求前驱和后继的方法：,遍历通过指定次序的遍历发现结点的前驱或后继，费时间，低效增设前驱和后继指针在每个结点中增设两个指针，分别指示该结点在指定次序下的前驱或后继。增加空间开销利用二叉链表中的空指针域（n个结点的二叉树有n+1个空指针域），将二叉链表中的空的指针域改为指向其前驱和后继：空的左孩子指针指向其前驱，空的右孩子指针指向其后继称这

32、种新的指针为（前趋或后继）线索，所得到的二叉树被称为线索二叉树，将二叉树转变成线索二叉树的过程被称为线索化。线索二叉树根据所选择的次序可分为先序、中序和后序线索二叉树。,比较好的方法,线索化,为什么？,？,（a）未加区分标志的先序线索二叉树的二叉链表示例,然而，仅仅按照这种方式简单地修改指针的值还不行，因为这将导致难以区分二叉链表中各结点的孩子指针和线索。例如，图6.15中结点C的lchild指针域所指向的结点是其左孩子还是其前趋？为此，在每个结点中需再引入两个区分标志ltag和rtag，并且约定如下： ltag=0： lchild指示该结点的左孩子。 ltag=1： lchild指针该结点的

33、前趋。 rtag=0： rchild指示该结点的右孩子。 rtag=1： rchild指针该结点的后继。,线索二叉链表结构描述如下：typedef char datatype； /*不妨设数据类型为字符型 */ typedef struct Threadnode int ltag,rtag; datatype data; struct Threadnode *lchild, *rchild;Threadnode , *Thread_Tree;,图6.15 b 线索二叉树的二叉链表形式示例,0,0,0,0,1,1,1,1,1,1,先序线索二叉树,0,0,0,0,1,1,1,1,1,1,中序线索二

34、叉树,0,0,0,0,1,1,1,1,1,1,后序线索二叉树,头结点：ltag=0, lchild指向根结点rtag=1, rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点,带头结点的中序线索二叉树,6.4.2 线索的算法实现,对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚已访问过的结点，即若指针t指向当前结点，则pre指向它的前驱，以便增设线索。,1.建立一棵中序线索化二叉树

35、,BiThree pre;int Inorder(BiThree *head,BiThree T)申请头结点*head空间； (*head)-ltag=0; (*head)-rtag=1; (*head)-rchild=*head; if(T为空) *head-lchild=*head; return 1; (*head)-lchild=T; pre=*head; InThreading(T); pre-rchild=*head;pre-rtag=1; (*head)-rchild=pre; return 1;,void InTreading(BiThrTree p)/* 递归中序线索化二叉树

36、 */if(p=NULL)return;InTreading(p-lchild); /* 中序线索化左子树 */ if(p-lchild=NULL) /* 建立前驱线索 */ p-ltag=1; p-lchild=pre; /* 左孩子域指向前驱*/ if(pre-rchild=NULL) /* 建立后继线索 */ p-rtag=1; pre-rchild=p; pre=p; /*中序线索化右子树 */ InTreading(p-rchild); ,2.中序线索二叉树的遍历算法,void InOrderTh ( Threadnode * t) /*对中序线索二叉树进行中序遍历*/ Thread

37、node * p;if (t) p=t; while (p-ltag=0) p=p-lchild; /*找最左下的结点，即中序遍历的第一个结点*/ while (p) / * 访问当前结点并找出当前结点的中序后继 */ visite(p-data); /*访问当前结点*/ p= InPostNode (p); /* 在中序线索二叉树上寻找结点p的中序后继结点 */ ,如何实现Inpostnode？,4.在中序线索二叉树中找结点后继的方法：（1）若rtag=1, 则rchild域直接指向其后继（2）若rtag=0, 则结点的后继应是其右子树的左链尾（ltag=1)的结点,3.在中序线索二叉树中找

38、结点前驱的方法：（1）若ltag=1, 则lchild域直接指向其前驱（2）若ltag=0, 则结点的前驱应是其左子树的右链尾（rtag=1)的结点,在中序线索二叉树上寻找结点p的中序前驱结点的算法如下：Threadnode *InPreNode（Threadnode * p）/*在中序线索二叉树上寻找结点p的中序前驱结点 */ Threadnode * pre; pre=p-lchild; if (p-ltag!=1) while (pre-rtag=0) pre=pre-rchild; return(pre);,在中序线索二叉树上寻找结点p的中序后继结点的算法如下：Threadnode *

39、InPostNode（Threadnode * p）/* 在中序线索二叉树上寻找结点p的中序后继结点 */ Threadnode * post; post=p-rchild; if (p-rtag= =0) while (post-ltag=0) post=post-lchild; return (post);,5.在中序线索二叉树上查找值为x的结点（带头结点）,BiThrTree Search(BiThrTree head,datatype x) BiThrTree p=head-lchild; if(p=head)return NULL; 找到中序遍历的第一个结点； 从该结点开始顺着后继进

40、行查找、比较； if(找到)return p; else return NULL; ,6.在中序线索二叉树上查找任意结点在先序下的后继,情况一：该结点p为分支结点,情况二：该结点p为叶子,后继为由右线索向上直到某个结点有右孩子或头结点为止,-rchild为后继;,if（有左孩子）,-lchild为后继;,else /有右孩子无左孩子,7.在中序线索二叉树上查找任意结点在后序下的前驱,情况一：该结点p为分支结点,情况二：该结点p为叶子,后继为由左线索向上直到某个结点有左孩子或头结点为止,-lchild为前驱;,if（有右孩子）,-rchild为前驱;,else /有左孩子无右孩子,6.6树与森林

41、,定义：树(tree)是n(n=0)个结点的有限集，在一棵非空树T有：有且仅有一个特定的结点，称为树的根(root)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点根树中各子树是互不相交的集合,6.6.1 树的存储结构,1.双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置,-1表示无双亲,如何找孩子结点,#define MaxNodeNum 100typedef struct DataType data; int

42、parent; Parentlist;typedef struct Parentlist elemMaxNodeNum; int n; /* 树中当前的结点数目 */ParentTree;,2.孩子表示法,多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度d,如何找双亲结点,孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表,孩子结点： typedef struct ChildNode int child; /该结点在表头数组中下标 struct ChildNode *nextch

43、ild; /指向下一孩子结点 ;表头结点： typedef struct datatype data; /数据域 struct ChildNode *firstchild; /指向第一个孩子结点 NodeType; NodeType tMAXNODE;,3.带双亲的孩子链表,4.孩子兄弟表示法（二叉树表示法）,实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点,typedef struct TreeNode datatype data; struct TreeNode *lchild, *nextsibling;NodeType,*CSTree;

44、,typedef struct TreeNode datatype data; struct TreeNode *lchild, *nextsibling;NodeType,*CSTree;,特点操作容易破坏了树的层次,6.6.2树、森林与二叉树转换,将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连

45、线调整：将结点按层次排列，形成树结构,森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,6.6.3树和森林的遍历,1 树的遍历,遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列,常用方法先根（序）遍历后根（序）遍历按层次遍历,先序遍历：,A,B,E,F,I,G,先根（序）遍历：先访问树的根

46、结点，然后依次先根遍历根的每棵子树,根 子树B 子树D,D,后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点,后序遍历：,E,I,F,G,B,D,子树B 子树D 根,A,层次遍历：,A,B,D,E,F,G,I,按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点,第1层,第2层,第3层,第4层,为什么没有中序遍历？,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,例,树：,对应二叉树：,先序遍历：,A,B,E

47、,F,I,G,C,D,H,J,K,L,N,O,M,中序遍历：,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,树的先序遍历与对应二叉树的先序遍历结果相同！树的后序遍历与对应二叉树的中序遍历结果相同！,2森林的遍历,常用方法先根（序）遍历后根（序）遍历,先根（序）遍历： （1）先访问森林中第一棵树的根结点； （2）先根遍历第一棵树的根结点的子树森林； （3）先根遍历去掉第一棵树后的子森林,先序遍历：,B,E,F,I,G,A,C,D,H,J,K,L,N,O,M,后序遍历：,E,I,F,G,B,C,D,A,J,K,N,O,L,后根（序）遍历： （1）后根遍历第一棵树的根结点的子树森林；

48、（2）访问第一棵树的根结点； （3）后根遍历去掉第一棵树后的子森林,M,H,先序遍历：,后序遍历：,F,I,A,B,C,D,H,K,L,N,O,M,I,F,B,C,D,A,K,N,O,L,M,H,例,森林：,对应二叉树：,先序遍历：,F,I,A,B,C,D,H,K,L,N,O,M,中序遍历：,I,F,B,C,D,A,K,N,O,L,M,H,森林的先序遍历与对应二叉树的先序遍历结果相同！森林的后序遍历与对应二叉树的中序遍历结果相同！,问题：,已知树（森林）的先序遍历序列和后序遍历序列，是否可以唯一确定该树（森林）？,6.7最优二叉树哈夫曼树,1.问题的引入,判定树一,判定树二,问题：哪一种的比较

49、算法较好？,设有学生100，000个,总比较次数S1 = （各等级总人数*每人比较次数） =100000*0.10*4+100000*0.30*4+100000*0.40*3 +100000*0.15*2+100000*0.05*1 =100000*(0.10*4+0.30*4+0.40*3+0.15*2+0.05*1) =100000*3.15=315,000(次)平均比较次数WPL1=(100000*3.15)/100000=3.15 = （各等级所占比例*比较次数）,总比较次数S2 =220,000(次) 平均比较次数WPL2= （各等级的比例*比较次数） =0.10*2+0.30*2+

50、0.40*2+0.15*3 +0.05*3 =2.2,怎样找出平均比较次数最少的算法？,路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径长度：路径上的分支数树的路径长度：从树根到所有叶子结点的路径长度之和,2.哈夫曼树的基本概念,平均比较次数WPL= （各等级的比例*比较次数） = （各叶子结点的权值*根到叶子结点的路径长度）,树的带权路径长度：树中各个叶子结点的路径长度与相应权值的乘积之和,例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,WPL=7*3+5*3+2*1+4*2=46,WPL=7*2+5*2+2*2+4*2=36,WPL=7*1+5*2+2