第6章　树和二叉树n.ppt

《第6章　树和二叉树n.ppt》由会员分享，可在线阅读，更多相关《第6章　树和二叉树n.ppt（198页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章树和二叉树n Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望学习目标掌掌握握树树的的定定义义、表表示示方方法法、基基本本性质、存储结构和遍历算法；性质、存储结构和遍历算法；掌掌握握二二叉叉树树的的定定义义、基基本本性性质质、存储结构、和各种运算。存储结构、和各种运算。6.1树的类型定义树的类型定义6.2 6.2 二叉树的类型定义二叉树的类型定义6.3二叉树的存储结构二叉树的存储结构6.4二叉树的遍历二叉树的遍历6.5线索二叉树线索二叉树6.6树和森林的表示方

2、法树和森林的表示方法6.7树和森林的遍历树和森林的遍历6.8哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码6.1树的类型定义树的类型定义6.1树的逻辑结构及其操作树的逻辑结构及其操作.树（树（Tree)是一个非空的有限元素的集合，元素是一个非空的有限元素的集合，元素之间具有如下关系：由且仅有一个特殊元之间具有如下关系：由且仅有一个特殊元素，他没有前驱（称为树根素，他没有前驱（称为树根Root）,其余其余元素都有且仅有一个前驱，所有元素可以元素都有且仅有一个前驱，所有元素可以有零个或多个后继。有零个或多个后继。ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T

3、2树根例如例如:树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式ABCDEFGH树形结构结点间具有分层次的连接关系HBCDEFGA现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学学校校的的行行政政关关系系、书书的的层层次次结结构构、人人类类的的家家族族血血缘缘关关系等。系等。对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它

4、数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互不相交的有限集不相交的有限集T1,T2,Tm，其中每一，其中每一棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系R：基本操作：基本

5、操作：查查找找类类插插入入类类删删除除类类Root(T)/求树的根结点求树的根结点查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历InitTree(&T)/初始化置空树初始化置空

6、树插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树ClearTree(&T)/将树清空将树清空删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树基基 本本 术术 语语结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:树中的一个数据元素分

7、支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM内部结点内部结点:孩子结点孩子结点:双亲结点双亲结点:兄弟结点兄弟结点:除根之外的分支结点结点的子树的根称为该结点的孩子（后继）一个结点是它各子树的根结点的双亲（前驱）具有相同双亲的结点DHIJM祖先祖先:子孙子孙:从根结点到该结点路径上所有结点都称为该结点的祖先。该结点所有子树上的结点都称为该结点的子孙MDHIJ(从根到结点的)路径路径：结点的层次结点的层次:树的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL根结点定义为第层，根的儿子定义为第层，以此类推，记作（）树中叶子结点所在的最大层次堂兄弟

8、堂兄弟:双亲在同一层上的结点()有确定的根；()树根和子树根之间为有向关系。有向树有向树：有序树有序树：子树之间存在确定的次序关系。无序树无序树：子树之间不存在确定的次序关系。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF注意：注意：根没有双亲，叶子没有孩子堂兄弟的双亲是兄弟关系吗？ABCDEFGHIJMKL树的常见表示方法1.直观表示法用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系，根在上，叶子在下（即树向下生长）ABCDEFGHIJMKL树的常见表示方法2

9、.集合表示法根据树的集合定义，写出集合划分。a,b,e,f,c,d,g3.文氏图表示法集合表示的一种直观表示，用图表示集合。ABEHICGFD4、目录表示法将树描述成一本书。书章节节小节5、广义表表示法将树描述成广义表。子树对应的是子表(a(b(e),(f),(c),(d,(g)ABCDEFGKHIJ已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，则该二叉树的高度为（）。假定根结点的高度为0。A.3 B.4C.5 D.6B6.2 二叉树的类型定义二叉树的类型定义为为何何要要重重点点研研究究每每结结点点最最多多只只有有两两个个“叉叉”的树？的树？二叉树的结构最简单，规律性最强

10、；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。ABCDEFGHK根结点左子树右子树二叉树或为空树空树，或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。二叉树的特点（和树比较）v二叉树有两棵子树（可以为空）；而树可以有多棵。v二叉树是有序树（有左右之分）；而树是无序树.v二叉树结点的度最大是2；二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树问：具有问：具有3个结点的二叉树可个结点的二叉树可能有几种不同形态？能有

11、几种不同形态？应用举例应用举例以用二叉树表示表达式以用二叉树表示表达式 a+b*(c-d)-e/f a+b*(c-d)-e/f e e d d c c b b f f a a+*/-二叉树的主要基本操作二叉树的主要基本操作：查查找找类类插插入入类类删删除除类类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(

12、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);DeleteChild(T,p,LR);删删除除类类二叉树二叉树的重要特性的重要特性用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对

13、所有的j，1ji，命题成立；二叉树上每个结点至多有两棵子树，则第i 层的结点数=2i-2 2=2i-1。性质性质1：在二叉树的第i层上至多有2i-1 个结点。(i1)性质性质2：深度为k 的二叉树上至多含2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为k 的二叉树上的结点数至多为20+21+2k-1=2k-1。一棵高度为5的二叉树中，最多包含有_个结点。假定根结点的高度为0。63性质性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2的结点，则必存在关系式：n0=n2+1。证明：证明：设设二叉树结点总数n=n0+n1+n2又又二叉树上分支总数b=n1+2n2 而b=

14、n-1=n0+n1+n2-1由此，由此，n0=n2+1。abcdefghij在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2*n思考题：思考题：C求空子树的个数等价于：求空子树的个数等价于：2n0+n1得值有n=n0+n1+n2和和n0=n2+12n0+n1 =n+1两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。对二叉树的结点按照逐层从上到下、对二叉树的结点按照逐层从上到下、每层从左到右进行编号，于是每个每层从左到右进行编号，于是每个结点都有一个序号。结点都有一个序号。123456789 10 11

15、 12 13 14 15完全二叉完全二叉树树：树中所含的n 个结点和满二叉树中编号为编号为1 至至n 的结的结点点一一对应。abcdefghij完全二叉树的特点：1、只有最后一层是不满的，不满层的结点最先出现在、只有最后一层是不满的，不满层的结点最先出现在左边左边2、至多只有最下面的两层结点的度小于、至多只有最下面的两层结点的度小于23、任何左子树的高度不会小于右子树的高度，且左、任何左子树的高度不会小于右子树的高度，且左右子树的高度最大相差右子树的高度最大相差1；4。叶子结点最多出现在最后。叶子结点最多出现在最后2层上。层上。abcdefghij性性质质4：具有n 个结点的完全二叉树的深深度

16、度为 log2n +1。证明：证明：设设完全二叉树的深度为k 则根据第二条性质得2k-1-1 n 2k-1即 k-1 log2 n k 因为因为k 只能是整数，因此，只能是整数，因此，k=log2n +1。在一棵具有35个结点的完全二叉树中，该树的高度为（）。A.5 B.6C.7D.8练习题：练习题：B性质性质5：若对含n 个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i（1=in，则该结点无左孩子，否则，编号为2i 的结点为其左孩子左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。1.在一棵完全二叉树

17、中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。假定根结点的编号为0A.2iB.2i-1C.2i+1D.2i+2C练习题：练习题：6.3二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序存储表示存储表示一、一、二叉树的顺序存储表示二叉树的顺序存储表示一、存储结构一、存储结构1 1、存储方式：用地址连续的空间单元存、存储方式：用地址连续的空间单元存储二叉树的各个元素，但为了表示关系，储二叉树的各个元素，但为了表示关系，元素存放时，首先确定一个序号，该序号元素存放时，首先确定一个序号，该序号是对二叉树是对二叉树按照完全二叉树

18、形式按照完全二叉树形式编号而得编号而得适合完全二叉树，最差的情况是右斜树适合完全二叉树，最差的情况是右斜树T1611ABCFED12489105637121314150000FE000DC0BA15141312111098765432100例如例如:特点：层次关系非常明确，双亲特点：层次关系非常明确，双亲i/2,i/2,孩子孩子2i,2i+12i,2i+1，但，但是必须知道结点的编号。是必须知道结点的编号。必须按完全二叉树的形式存储，将造成存储的浪费。必须按完全二叉树的形式存储，将造成存储的浪费。例如例如:ABCDEFABDCEF0123456789101112131401326缺点：插入、删

19、除需要移动元素，空间效率低。缺点：插入、删除需要移动元素，空间效率低。#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTreebt;二叉树的顺序存储表示虚拟实现二叉树的顺序存储表示虚拟实现二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表 存存储储方方式式：用用任任意意的的空空间间单单元元来来存存储储二二叉叉树树的的各各个个元元素素，在在存存储储元元素素的的同同时时，也也存存储其左右孩子的地址。

20、储其左右孩子的地址。ADEBCF rootlchilddatarchild结点结构结点结构:1.1.二叉链表二叉链表特点特点:占用空间不随树的形态变化占用空间不随树的形态变化 n n个结点的二叉树，占用空间为：个结点的二叉树，占用空间为：n*(n*(存储一个元素的空间存储一个元素的空间+2*+2*存储一个指针存储一个指针的空间）的空间）对求孩子操作容易，但求双亲难；对求孩子操作容易，但求双亲难；插入、删除元素不需要移动，但调整指针多；插入、删除元素不需要移动，但调整指针多；空指针多空指针多多少多少?typedefstructBiTNode/结点结构结点结构TElemTypedata;struc

21、tBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;lchilddatarchild结点结构结点结构:C语言的类型描述如下语言的类型描述如下:ADEBCF root 2三叉链表三叉链表parentlchilddatarchild结点结构结点结构:typedefstructTriTNode/结点结构结点结构TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指针structTriTNode*parent;/双亲指针TriTNode,*TriTree;parentlchilddatarchild结点结构结点结构

22、:C语言的类型描述如下语言的类型描述如下:0123456dataparent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRLABCDEFtypedefstructBPTNode/结点结构结点结构TElemTypedata;int*parent;/指向双亲的指针charLRTag;/左、右孩子标志域BPTNodetypedefstructBPTree/树结构树结构BPTNodenodesMAX_TREE_SIZE;intnum_node;/结点数目introot;/根结点的位置BPTree6.4二叉树的遍历二叉树的遍历一、一、问题的提出问题的提出二、二、先左后右的遍历算法先左后右的遍

23、历算法三、三、算法的递归描述算法的递归描述五五、遍历算法的应用举例遍历算法的应用举例四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。“遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。对对“二二叉叉树树”而而言言，

24、可可以以有有三三条搜索路径：条搜索路径：1先上后下先上后下的按层次遍历；2先先左左（子树）后后右右（子树）的遍历；3先先右右（子树）后后左左（子树）的遍历。一、按层遍历算法一、按层遍历算法void Levelorder(BiTree*BT)const MaxLength=30;BiTree*qMaxLength;/定义队列 int front=0,rear=0;/定义队首和队尾指针 BiTree*p;if(BT!=NULL)/将树根指针进队 qrear=BT;rear=(rear+1)%MaxLength;A AE EB BD DC CG GF Fwhile(front!=rear)p=qfr

25、ont;front=(front+1)%MaxLength;coutdataleft!=NULL)qrear=p-left;rear=(rear+1)%MaxLength;if(p-right!=NULL)qrear=p-right;rear=(rear+1)%MaxLength;/while endA AE EB BD DC CG GF F二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：ABCD

26、EFGH000000000biginend先序遍历顺序先序遍历顺序:A B D F G C E HABDFGCEH先（根）序的先（根）序的遍历算法：遍历算法：123456789 10 11 12输出序列：1,2,4,8,9,5,10,11,3,6,12,7若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：ABCDEFGH000000000biginend中序遍历顺序中序遍历顺序:ABDFGC E HBFDGACEH中（根）中（根）序的遍历序的遍历算法：算法：12345679 10 11 12输出序列：4,9

27、,2,10,5,11,1,12,6,3,7若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：ABCDEFGH000000000biginend后序遍历顺序后序遍历顺序:F G D B H E C AABDFGCEH后（根）后（根）序的遍序的遍历算法：历算法：12345679 10 11 12输出序列：9,4,10,11,5,2,12,6,7,3,1序号 01234567 8 910 11 12data 20846515 30 00 0 10 18 035已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其

28、中0表示空指针，请分别写出该二叉树的前序、中序、后序遍历的序列。前序序列：2085151018463035中序序列：5810151820303546后序序列：5101815835304620假定一棵二叉树的广义表表示为a(b(c),d(e,f)，分别写出对它进行前序、中序、后序、按层遍历的结果。前序：_中序：_后序：_按层：_abcdefcbaedfcbefdaabdcef软件设计师 2004上半年设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是_(10)_。Ax是y的左兄弟Bx是y的右兄弟Cx是y的祖先Dx是y的后裔

29、C三、算法的递归描述三、算法的递归描述voidPreorder(BiTreeT,void(*visit)(TElemType&e)/先序遍历二叉树if(T)visit(T-data);/访问结点Preorder(T-lchild,visit);/遍历左子树Preorder(T-rchild,visit);/遍历右子树 VoidPreOderTraverse(BiTreeT)if(T!=NULL)visit(T-data);PreOrderTraverse(T-lchild);PreOrderTraverser(T-rchild);/*先序遍历先序遍历*/主程序主程序Pre(T)返回返回pre(

30、TR);返回返回pre(TR);ACBDTBvisit(B);pre(TL);BTAvisit(A);pre(TL);ATDvisit(D);pre(TL);DTCvisit(C);pre(TL);C返回T左是空返回左是空返回pre(TR);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(TR);voidInorderTraverse(BiTreeT,void(*visit)(TElemType&e)/中序遍历二叉树if(T)InorderTraverse(T-lchild,visit);/遍历左子树visit(T-data);/访问结点Inor

31、derTraverse(T-rchild,visit);/遍历右子树中序遍历算法中序遍历算法voidPostOrderTraverse(BiTreeT,void(*visit)(TElemType&e)/中序遍历二叉树if(T)PostOrderTraverse(T-lchild,visit);/遍历左子树PostOrderTraverse(T-rchild,visit);/遍历右子树visit(T-data);/访问结点 后序遍历算法后序遍历算法四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述BiTNode*GoFarLeft(BiTreeT,Stack*S)if(!T)return

32、NULL;while(T-lchild)Push(S,T);T=T-lchild;returnT;voidInorder_I(BiTreeT,void(*visit)(TelemType&e)Stack*S;t=GoFarLeft(T,S);/找到最左下的结点while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);elseif(!StackEmpty(S)/栈不空时退栈t=Pop(S);elset=NULL;/栈空表明遍历结束/while/Inorder_I五五、遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计

33、二叉树中叶子结点的个数(先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构5 5、二叉树的其他运算和习题、二叉树的其他运算和习题1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。voidCountLeaf(BiTreeT,

34、int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加

35、1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。intDepth(BiTreeT)/返回二叉树的深度if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;3、复制二叉树、复制二叉树其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右

36、子树右子树(后序遍历后序遍历)BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;returnT;生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T-lchild)newlptr=

37、CopyTree(T-lchild);/复制左子树elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树elsenewrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);returnnewT;/CopyTreeABCDEFGHKDCBHKGFEA例如：下列二叉树例如：下列二叉树的复制过程如下：的复制过程如下：newT4 4、建立二叉树的存储建立二叉树的存储结构结构不同的定义方法相应有不同的不同的定义方法相应有不同的存储结构的建立算法存储结构的建立算法按照给定的先序序列建立二叉

38、链表按照给定的先序序列建立二叉链表由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树按照给定的先序序列建立二叉链表按照给定的先序序列建立二叉链表根根左子树左子树右子树右子树定义一棵二叉树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A”表示以下列字符串表示StatusCreateBiTree(BiTree&T)scanf(“%c”,&ch);if(ch=)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=

39、ch;/生成根结点CreateBiTree(T-lchild);/构造左子树CreateBiTree(T-rchild);/构造右子树returnOK;/CreateBiTreeABCDA BCD上页算法执行过程举例如下：ATBCD仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根abcdefgcbdaegf例如例如:aabbccddeeffggabcdefg先序序列中序序列已知一

40、棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：_C,B,F,E,I,J,H,G,D,A已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为0）和度为2、度为1的结点及叶结点个数。中根序列：c,b,d,e,a,g,i,h,j,f后根序列：c,e,d,b,i,j,h,g,f,a 高度：_ 度为2：_ 度为1：_ 叶子：_高度：5度为2：3度为1：3叶子：4五、二叉树其他运算五、二叉树其他运算1.初始化初始化二叉树二叉树voidInitBTree(BiTree&T)T=NUL

41、L;2.检查二叉树检查二叉树是否是否为为空空boolBTreeEmpty(BiTree&T)returnT=NULL;3.清除二叉树voidDeleteBTree(BiTree&T)if(T!=NULL)DeleteBTree(T-left);/删除左子树删除左子树DeleteBTree(T-right);/删除右子树删除右子树deleteT;/删除根结点删除根结点voidClearBTree(BiTree&T)DeleteBTree(T);T=NULL;1、已知二叉树中的结点类型用比BiTreeNode表示，被定义为:struct BiTreeNode datatype data;BiTre

42、eNode*leftChild,*rightChild,*parent;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。BiTreeNode*PN(BiTreeNode*T,datatype&x)if(T=NULL)returnNULL;elseBiTreeNode*mt;if(T-data=x)returnT-parent;elseif(mt=PN(T-leftChild,x)returnmt;elseif(mt=PN

43、(T-rightChild,x)returnmt;returnNULL;算法功能：2已知二叉搜索树中的结点类型用BinTreeNode表示，被定义:structstruct BinTreeNode ElemType data;BinTreeNode*leftChild,*rightChild;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定pt所指向的二叉搜索树的广义表表示为:25(10(5,16(12),40(32(,38)，按照下面算法，(1)执行unknown(pt,40)调用后返回的值为_。(2)执行unknown(pt,38)调用

44、后返回的值为_。(3)执行unknown(pt,5)调用后返回的值为_。(4)执行unknown(pt,60)调用后返回的值为_。intunknown(BinTreeNode*t,ElemTypex)if(t=NULL)return0;elseif(t-data=x)return1;elseif(t-datax)return1+unknown(t-leftChild,x);elsereturn1+unknown(t-rightChild,x);3、已知二叉树中的结点类型用比BiTreeNode表示，被定义为:struct BiTreeNode datatype data;BiTreeNode*

45、leftChild,*rightChild,*parent;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。BiTreeNode*PN(BiTreeNode*T,datatype&x)if(T=NULL)returnNULL;elseBiTreeNode*mt;if(T-data=x)returnT-parent;elseif(mt=PN(T-leftChild,x)returnmt;elseif(mt=PN(T-rig

46、htChild,x)returnmt;returnNULL;算法功能：从树根指针为T的二叉树中查找值为x的结点，返回指向父结点的指针4、已知二叉树中的结点类型用已知二叉树中的结点类型用BinTreeNode表示，被定义为表示，被定义为:struct BinTreeNode char data;BinTreeNode*leftChild,*rightChild;其其中中datadata为为结结点点值值域域，leftChildleftChild和和rightChildrightChild分分别别为为指指向向左左、右右子子女女结结点点的的指指针针域域。假假定定指指针针btbt指指向向一一棵棵二二叉叉

47、树树，该该二二叉叉树树的的广广义义表表表表示示为为a a(b(b(a,(a,d d(f)(f),),c c(e(e(,a a(k)(k),),b)b)，整整数变量数变量C C的值为的值为0 0，若：，若：(1)执行执行BTC1(bt,a,C)调用后，调用后，C的值为的值为_;(2)执行执行BTC1(bt,b,C)调用后，调用后，C的值为的值为_;(3)执行执行BTC1(bt,c,C)调用后，调用后，C的值为的值为_;(4)执行执行BTC1(bt,g,C)调用后，调用后，C的值为的值为_;voidBTC1(BinTreeNode*BT,charx,int&k)if(BT!=NULL)if(BT-

48、data=x)k+;BTC1(BT-leftChild,x,k);BTC1(BT-rightChild,x,k);5、已知二叉树中的结点类型用已知二叉树中的结点类型用BinTreeNode表示，被定义为表示，被定义为:structBinTreeNodeElemTypedata;BinTreeNode*leftChild,*rightChild;其其中中datadata为为结结点点值值域域，leftChildleftChild和和rightChildrightChild分分别别为为指指向向左左、右右子子女女结结点点的的指指针针域域。根根据据下下面面函函数数的的定定义义指指出出函函数数的的功功能能

49、。算法中参数算法中参数BTBT指向一棵二叉树的根结点。指向一棵二叉树的根结点。intDST(BinTreeNode*&BT,ElemTypex)if(BT=NULL)return0;else if(BT-data=x)BT=NULL;return1;elseif(DST(BT-leftChild,x)return1;if(DST(BT-rightChild,x)return1;elsereturn0;算法功能算法功能：删除根结点为x的子树，若删除成功则返回1，否则返回06.5线索二叉树线索二叉树何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索

50、链表？一、一、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:ABCDEFGHK中序中序序列:BDCAHGKFE后序后序序列:DCBHKGFEA空指针的个数=n+1ABCDEFGHKABECDFGHK指向该线性序列中的“前驱”和“后继”的指针指针，称作“线索线索”与其相应的二叉树，称作“线索二叉树线索二叉树”包含“线索”的存储结构，称作“线索链线索链表表”ABCDEFGHKDCBEABCDEFGHKABECDFGHK每个结点增加两个域：每个结点增加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存