《二叉树与森林课件.ppt》由会员分享，可在线阅读，更多相关《二叉树与森林课件.ppt（180页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构(A)(课程号课程号:80L129Q)办公室办公室:第第9教学楼北教学楼北502室室Data Structure&Algorithm(Course No.:80L129Q)Dr.Zhihai WANG(Prof.)Dr.Zhihai WANG(Prof.)Email:Telephone:86-10-51683859Office:North 502,Building 9School of Computer&Information Technology,Beijing Jiaotong University,Beijing,100044,China第第6章章 树型结构及其算法树型结
2、构及其算法王志海王志海办公室办公室:第第9教学楼北教学楼北502室室北京交通大学计算机与信息技术学院北京交通大学计算机与信息技术学院教学大纲：教学大纲：教学内容教学内容树的基本概念；二叉树的性质和存储结构；遍历二叉树；线索二叉树;树的存储结构和遍历；哈夫曼树及其应用。4 Zhihai WANG,2015本章主要内容本章主要内容树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码6 Zhihai WANG,2015本章主要内容本章主要内容树的类型定义树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树
3、和森林树和森林的遍历哈夫曼树与哈夫曼编码7 Zhihai WANG,2015树的定义树的定义树(tree)是n(n 0)个结点的有限集。当n=0时称为空树；在任意一棵非空树中，有且仅有一个结点称为根(root)结点，其余的结点可分为m(m 0)个互不相交的有限集T1,T2,Tm,其中每一个集合又称为一棵树，并且称为根的子树(subtree)。同理，每一棵子树又可以分为若干个互不相交的有限集。8 Zhihai WANG,2015与与查找查找有关的基本操作有关的基本操作Root(T)/求树的根结点 Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结
4、点LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T,Visit()/遍历10 Zhihai WANG,2015与与插入插入有关的基本操作有关的基本操作InitTree(&T)/初始化置空树 CreateTree(&T,definition)/按定义构造树Assign(T,cur_e,value)/给当前结点赋值InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树11 Zhihai W
5、ANG,2015例如例如:ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根13 Zhihai WANG,2015树型结构树型结构 vs.线性结构线性结构线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)15 Zhihai WANG,2015树的基本术语树的基本术语(6-1
6、)树的结点：包含一个数据元素及若干个指向其子树的分支；结点的度：一个结点拥有的子树数目(分支数)；DHIJM树的度树的度：一棵树上所有结点度的最大值；：一棵树上所有结点度的最大值；叶子结点叶子结点(终端结点终端结点):度为零的结点；度为零的结点；分支结点分支结点(非终端结点非终端结点):度大于零的结点；度大于零的结点；16 Zhihai WANG,2015树的基本术语树的基本术语(6-3)兄弟：具有同一父结点的子结点互称兄弟；堂兄弟：其双亲在同一层的结点互为堂兄弟；祖先结点：从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；ABCDEFGHIJMKL1
7、8 Zhihai WANG,2015树的基本术语树的基本术语(6-4)结点的层次：从根结点到该结点所经过的路径长度加1；树的深度：树中叶子结点具有的最大层次数；ABCDEFGHIJMKL19 Zhihai WANG,2015树的基本术语树的基本术语(6-5)有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树；第一个孩子：在有序树中，最左边的子树的根称为第一个孩子；最后一个孩子：最右边 的子树的根称为 最后一个孩子.ABCDEFGHIJMKL20 Zhihai WANG,2015树的基本术语树的基本术语(6-6)森林是m(m 0)棵互不相交的树的集合。对树中每个
8、结点而言，其子树的集合即为森林。任何一棵非空树是一个二元组Tree=(root,F)其中root 被称为根结点，F 被称为子树森林 ABCDEFGHIJMKLrootF21 Zhihai WANG,2015本章主要内容本章主要内容树的类型定义二叉树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码22 Zhihai WANG,2015二叉树的一个例子二叉树的一个例子ABCDEFGHK根结点左子树右子树24 Zhihai WANG,2015二叉树的五种基本形态二叉树的五种基本形态N空树空树只含根结点只含根结点NNNLRR右子树为
9、空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树25 Zhihai WANG,2015二叉树的主要基本操作二叉树的主要基本操作查 找 类插插 入入 类类删删 除除 类类26 Zhihai WANG,2015二叉树与二叉树与查找查找有关的基本操作有关的基本操作(2)先序遍历操作：PreOrderTraverse(T,Visit();中序遍历操作：InOrderTraverse(T,Visit();后序遍历操作：PostOrderTraverse(T,Visit();层序遍历操作：LevelOrderTraverse(T,Visit();28 Zhihai WANG,
10、2015二叉树与二叉树与插入插入有关的基本操作有关的基本操作InitBiTree(&T);/构造空的二叉树；Assign(T,&e,value);/结点赋值函数CreateBiTree(&T,definition);/建树函数；InsertChild(T,p,LR,c);/插入P的左/右子树操作。29 Zhihai WANG,2015本章主要内容本章主要内容树的类型定义二叉树的类型定义二叉树的性质二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码31 Zhihai WANG,2015性质性质 1在二叉树的第 i 层上至多有2i-1 个结点。(i1)32
11、 Zhihai WANG,2015用归纳法证明性质用归纳法证明性质1证明:1、i=1 时，只有一个根结点，显然 2 i-1=20=1 正确；2、假设第i-1层上至多有2 i-2个结点成立,由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2 i-2=2 i-1证明完毕。33 Zhihai WANG,2015性质性质 2 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为：20+21+2k-1=2k-1。34 Zhihai WANG,2015性质性质3 3对任何一棵二叉树，若它含有n0
12、 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：设 二叉树上结点总数 n=n0+n1+n2又 二叉树上分支总数 b=n1+2n2（1）除根结点之外，其余结点都有一个分支进入，所以 b=n-1，把n代入，b=n0+n1+n2 1（2）由此（1）-（2），得 n0=n2+1。35 Zhihai WANG,2015性质性质3的例子的例子123457123436 Zhihai WANG,2015两类特殊的二叉树两类特殊的二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。特点:每一层上的结点数都是最大结点数。123456789 10 11 12 13 14 153
13、7 Zhihai WANG,2015两类特殊的二叉树两类特殊的二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。特点1:叶子结点只可能在层次最大的两层上出现；特点2:对任意结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。123456789 10 11 1238 Zhihai WANG,2015性质性质4(适合于完全二叉树适合于完全二叉树):具有 n 个结点的完全二叉树的深度为 log2n+1。证明：设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号
14、为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。41 Zhihai WANG,2015性质性质5 的例子的例子这个完全二叉树有10 个结点，编号为1的结点是根，当然其无双亲；编号为5 的结点的双亲结点是5/2=2号结点；因为 2*610，所以编号大于6的结点都无左孩子；而4号结点的左孩子的编号为 2*4=8号结点；123456789 1042 Zhihai WANG,2015本章主要内容本章主要内容树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与
15、哈夫曼编码43 Zhihai WANG,2015二叉树的存储结构二叉树的存储结构二叉树的顺序存储表示二叉树的链式存储表示44 Zhihai WANG,2015二叉树的顺序存储表示二叉树的顺序存储表示用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。顺序存储适用于完全二叉树顺序存储适用于完全二叉树1234578 9 10 11 12612345678910 11 1245 Zhihai WANG,2015二叉树的顺序存储表示二叉树的顺序存储表示对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。12345000067123456 7一般
16、二叉树一般二叉树:（0表示不存在的结点）表示不存在的结点）46 Zhihai WANG,2015顺序存储顺序存储的的C语言描述语言描述#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTree bt;47 Zhihai WANG,2015二叉树的链式存储表示二叉树的链式存储表示 二叉链表 三叉链表 双亲链表 线索链表线索链表(见下一节见下一节)48 Zhihai WANG,20151.1.二叉链表二叉链表lchild data rchild结点结构结点结构:含有两个
17、指针域的含有两个指针域的结点结构结点结构rootADEBCF 49 Zhihai WANG,2015C 语言的类型描述如下语言的类型描述如下:typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;50 Zhihai WANG,20152三叉链表三叉链表parent lchild data rchild结点结构结点结构:含有三个指针域的结点结构含有三个指针域的结点结构ADEBCF root 51 Zhihai WANG,2015C 语
18、言的类型描述如下语言的类型描述如下:typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针左右孩子指针 struct TriTNode *parent;/双亲指针双亲指针 TriTNode,*TriTree;lchild data parent rchild结点结构结点结构:52 Zhihai WANG,2015例子例子ABCDEFG二叉树二叉树 二叉链表二叉链表 三叉链表三叉链表BCDEFGA rootABCDEFGroot53 Zhihai WANG,20153 3双亲
19、链表双亲链表0123456结点结构结点结构:data parent LRTagLRRRL54 Zhihai WANG,2015C 语言的类型描述语言的类型描述typedef struct BPTNode /结点结构 TElemType data;int parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode typedef struct BPTree /树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree55 Zhihai WANG,2015本章主要内容本章主要内容树
20、的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码56 Zhihai WANG,2015二叉树的遍历二叉树的遍历问题的提出问题的提出先左后右的遍历算法先左后右的遍历算法算法的递归描述算法的递归描述遍历算法的非递归描述遍历算法的非递归描述遍历算法的应用举例遍历算法的应用举例57 Zhihai WANG,20151.问题的提出问题的提出顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，可以对结点作各种处理，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性
21、结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。58 Zhihai WANG,2015三条搜索路径三条搜索路径对“二叉树”而言，可以有三条搜索路径：1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。59 Zhihai WANG,20152.先左后右的遍历算法先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法60 Zhihai WANG,2015先（根）序的遍历算法先（根）序的遍历算法若二叉树为空树，则空操
22、作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。-+/e*afb-cd61 Zhihai WANG,2015中（根）序的遍历算法中（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。-+/e*afb-cd62 Zhihai WANG,2015后（根）序的遍历算法后（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。-+/e*afb-cd63 Zhihai WANG,20153.算法的递归描述（算法的递归描述（3-1）先序遍历二叉树算法void Preo
23、rder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问根结点 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 64 Zhihai WANG,20153.算法的递归描述（算法的递归描述（3-2）中序遍历二叉树算法void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Inorder(T-lchild,visit);/遍历左子树 visit(T-data);/访问根结点
24、 Inorder(T-rchild,visit);/遍历右子树 65 Zhihai WANG,20153.算法的递归描述（算法的递归描述（3-3）后序遍历二叉树算法void Postorder(BiTree T,void(*visit)(TElemType&e)/后序遍历二叉树 if(T)Postorder(T-lchild,visit);/遍历左子树 Postorder(T-rchild,visit);/遍历右子树 visit(T-data);/访问根结点 递归算法简明精练，但效率较低。递归算法简明精练，但效率较低。66 Zhihai WANG,2015二叉树的遍历二叉树的遍历问题的提出先左
25、后右的遍历算法先左后右的遍历算法算法的递归描述算法的递归描述遍历算法的非递归描述遍历算法的非递归描述遍历算法的应用举例遍历算法的应用举例67 Zhihai WANG,20154.遍历二叉树的非递归算法遍历二叉树的非递归算法在非递归算法中要用栈来保存遍历过程中经历的结点的左孩子和右孩子。使用栈来实现中序遍历二叉树的基本思想：abecd从二叉树的根结点开始，沿左子树一直走到从二叉树的根结点开始，沿左子树一直走到末端为止，在向前搜索的过程中将所遇结点末端为止，在向前搜索的过程中将所遇结点进栈，待遍历完左子树时，从栈顶退出结点进栈，待遍历完左子树时，从栈顶退出结点并访问，然后再遍历右子树。并访问，然后
26、再遍历右子树。68 Zhihai WANG,2015中序遍历算法的非递归描述中序遍历算法的非递归描述(1-1)BiTNode*GoFarLeft(BiTree T,Stack*S)if(!T)return NULL;while(T-lchild)/找到最左下的结点 Push(S,T);T=T-lchild;return T;69 Zhihai WANG,2015中序遍历算法的非递归描述中序遍历算法的非递归描述(1-2)void Inorder_I(BiTree T,void(*visit)(TelemType&e)/中序遍历二叉树的非递归算法1 Stack*S;t=GoFarLeft(T,S)
27、;/找到最左下的结点 while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);else if(!StackEmpty(S)/栈不空时退栈 t=Pop(S);else t=NULL;/栈空表明遍历结束 /while/Inorder_I 70 Zhihai WANG,2015中序遍历算法的非递归描述中序遍历算法的非递归描述(2-1)算法思想：假设二叉树采用二叉链表存储，用一个顺序栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，访问之，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，如此这样，直到栈空为止。7
28、1 Zhihai WANG,2015中序遍历算法的非递归描述中序遍历算法的非递归描述(2-2)void inorder(BiTree b)/中序遍历二叉树的非递归算法二 BiTree*stackm0,*p;int top=0;p=b;do while(p!=NULL)/扫描所有左结点 top+;stacktop=p;p=p-lchild;72 Zhihai WANG,2015中序遍历算法的非递归描述中序遍历算法的非递归描述(2-3)if(top0)p=stacktop;/p所指结点为无左子树的结点 /或其左子树已遍历过 top-;printf(“%d”,p-data);/访问结点 p=p-rc
29、hild;/扫描右子树 while(p!=NULL|top!=0)73 Zhihai WANG,2015前序遍历的非递归算法（前序遍历的非递归算法（1）假设二叉树采用二叉链表存储,使用一个栈 stack实现非递归的前序遍历。算法思想：先分析前序遍历时结点输出顺序的特点(根先输出,右孩子后输出)74 Zhihai WANG,2015前序遍历的非递归算法（前序遍历的非递归算法（2）void preorder(BiTree b)/前序遍历二叉树的非递归算法 BiTree*stackm0;int top;if(b!=NULL)top=1;/根结点入栈 stacktop=b;while(top0)/栈不
30、为空时循环 p=stacktop;/退栈并访问该结点 top-;printf(“%d”,p-data);75 Zhihai WANG,2015前序遍历的非递归算法（前序遍历的非递归算法（3）n 左右孩子中，哪一个先入栈呢？if(p-rchild!=NULL)/右孩子入栈 top+;stacktop=p-rchild;if(p-lchild!=NULL)/左孩子入栈 top+;stacktop=p-lchild;/while /if 76 Zhihai WANG,2015后序遍历的非递归算法（后序遍历的非递归算法（1）算法思想：1.用一个栈保存返回的结点;2.先扫描根结点的所有左结点并入栈，出栈
31、一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈；3.当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。77 Zhihai WANG,2015后序遍历的非递归算法（后序遍历的非递归算法（2）如果从左子树返回到根，下一步是继续遍历右子树；如果从右子树返回到根，则应访问根结点。这就产生了一个问题：在退栈回到根结点时如何区别是从左子树返回还是从右子树返回?这里采用两个栈 stack 和 tag，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标志（0为左子树，1为右子树）。退栈时在退出结点指针的同时区分是遍历左子树返回的还是遍历右子树返回的，以决定下一
32、步是继续遍历右子树还是访问根结点。78 Zhihai WANG,2015后序遍历的非递归算法（后序遍历的非递归算法（3）void postorder(BiTree b)/后序遍历二叉树的非递归算法 BiTree*stackm0,*p;int tagm0,top=0;p=b;do while(p!=NULL)/扫描左结点 top+;stacktop=p;tagtop=0;p=p-lchild;while(top0)&tagtop=1)/p的左右子树都访问过 79 Zhihai WANG,2015后序遍历的非递归算法（后序遍历的非递归算法（4）while(top0)&tagtop=1)/p的左右子
33、树都访问过 printf(“%d”,stacktop-data);top-;/访问结点并出栈 p=stacktop;if(top0)&(tagtop=0)/扫描右子树 p=p-rchild;tagtop=1;while(p!=NULL|top!=0)80 Zhihai WANG,2015按层次顺序遍历二叉树的算法按层次顺序遍历二叉树的算法1按层次顺序（同一层次自左至右）遍历二叉树的算法算法思想（宽度优先算法）：假设二叉树采用二叉链表结构，依题意，本算法要采用一个队列q，先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，如
34、此直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。81 Zhihai WANG,2015按层次顺序遍历二叉树的算法按层次顺序遍历二叉树的算法2#define MAXLEN 100void translevel(BiTree b)/按层次遍历 struct node BiTree*vecMAXLEN;int f,r;q;q.f=0;q.r=0;/置队列为空队列 if(b!=NULL)printf(“%d”,b-data);q.vecq.r=b;/结点指针进入队列结点指针进入队列 q.r=q.r+1;82 Zhihai WANG,2015按层次顺序遍历二叉树的算法按层
35、次顺序遍历二叉树的算法3while(q.flchild!=NULL)/输出左孩子，并入队列 printf(“%d”,b-lchild-data);q.vecq.r=b-lchild;q.r=q.r+1;if (b-rchild!=NULL)/输出右孩子，并入队列输出右孩子，并入队列 printf(“%d”,b-rchild-data);q.vecq.r=b-rchild;q.r=q.r+1;83 Zhihai WANG,2015二叉树的遍历二叉树的遍历问题的提出先左后右的遍历算法先左后右的遍历算法算法的递归描述算法的递归描述遍历算法的非递归描述遍历算法的非递归描述遍历算法的应用举例遍历算法的应
36、用举例84 Zhihai WANG,2015遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数(先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)4、复制二叉树、复制二叉树(后序遍历后序遍历)3、求二叉树值为、求二叉树值为X的祖先的祖先(后序遍历后序遍历)自自学学5、建立二叉树的存储结构、建立二叉树的存储结构6、根据遍历序列构造二叉树、根据遍历序列构造二叉树85 Zhihai WANG,2015统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中
37、“访问结点”的操作改为：若是叶子，则计数器增1。86 Zhihai WANG,20151、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。abecd87 Zhihai WANG,2015void CountLeaf(BiTree T,int&count)/统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数 if(T)if(!T-lchil
38、d)&(!T-rchild)count+;/对叶子结点计数 /if/CountLeafCountLeaf(T-lchild,count);CountLeaf(T-rchild,count);88 Zhihai WANG,2015Int CountLeaf(BiTree T)/统计二叉树中叶子结点的个数方法二统计二叉树中叶子结点的个数方法二 if(T=NULL)return 0;else if(T-lchild=NULL&T-rchild=NULL)return 1;else return CountLeaf(T-lchild)+CountLeaf(T-rchild);统计二叉树中叶子结点的个数
39、方法二统计二叉树中叶子结点的个数方法二89 Zhihai WANG,20152、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的深二叉树的深度应为其左、右子树深度的最大值加度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度求得左、右子树深度的最大值，然后加的最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子树右子树深度深度之间的关系。90 Zhihai WANG,2015int Depth(BiTree T)/返
40、回二叉树的深度返回二叉树的深度 if(!T)depthval=0;else return depthval;depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);91 Zhihai WANG,20155、建立二叉树的存储结构、建立二叉树的存储结构建立二叉树存储结构有多种算法建立二叉树存储结构有多种算法(1)(1)以字符串的形式以字符串的形式 根根-左子树左子树-右子树右子树 （先序形式）（先序形式）定义一棵二叉树定义一棵二叉树(2)(
41、2)根据表达式建相应的二叉树根据表达式建相应的二叉树(3)(3)由二叉树的先序和中序序列建二叉树由二叉树的先序和中序序列建二叉树92 Zhihai WANG,2015(1)以字符串的形式以字符串的形式 根根-左子树左子树-右子树右子树 （先序形式）（先序形式）定义一棵二叉树定义一棵二叉树例如例如:以空白字符“”表示A(B(,C(,),D(,)空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A()”表示以下列字符串表示ABCD93 Zhihai WANG,2015Status CreateBiTree(BiTree&T)/按先序输入二叉树结点的值按先序输入二叉树结点的值 scan
42、f(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点生成根结点 CreateBiTree(T-lchild);/构造左子树构造左子树 CreateBiTree(T-rchild);/构造右子树构造右子树 return OK;/CreateBiTree94 Zhihai WANG,2015A B C D A BCD上页算法执行过程举例如下：上页算法执行过程举例如下：ATBCD95 Zhihai WANG,2015(2)根据表达式建相应的二叉树根据表达式建相应
43、的二叉树已知表达式已知表达式(a+b)c d/e d/e-abcde+/先序遍历先序遍历:-+abc/de/de中序遍历中序遍历:a+bc-d/e后序遍历后序遍历:a b+cde/-前缀表达式前缀表达式-中缀表达式中缀表达式-后缀表达式后缀表达式特点特点：操作数操作数为叶子叶子结点运算符运算符为分支分支结点96 Zhihai WANG,2015a+b(a+b)c d/ea+bc 分析表达式和二叉树的关系分析表达式和二叉树的关系:ab+abc+abc+(a+b)cabcde-+/97 Zhihai WANG,2015算法思想算法思想:使用两个栈，一个存放叶子或子树，另一个存放运算符使用两个栈，一
44、个存放叶子或子树，另一个存放运算符1.读入一个字符读入一个字符;2.如果是如果是数数,建建叶子叶子结点结点,入树栈入树栈 暂存暂存;3.如果是如果是运算符运算符,则和字符栈的栈顶元素比较优先则和字符栈的栈顶元素比较优先级级:1)若当前的优先级若当前的优先级“高高”,则入运算符栈暂存则入运算符栈暂存;2)若栈顶的优先级若栈顶的优先级“高高”,则运算符栈的栈顶则运算符栈的栈顶元素出栈元素出栈(根根),从树栈中弹出两个元素从树栈中弹出两个元素(右左孩子右左孩子)建子树建子树,新建的子树再入树栈保存新建的子树再入树栈保存98 Zhihai WANG,2015建叶子结点的算法为：void CrtNode
45、(BiTree&T,char ch)T=(BiTNode*)malloc(sizeof(BiTNode);T-data=ch;T-lchild=T-rchild=NULL;Push(PTR,T);/叶子结点入叶子结点入PTR树栈保存树栈保存99 Zhihai WANG,2015建子树的算法为：void CrtSubtree(Bitree&T,char c)T=(BiTNode*)malloc(sizeof(BiTNode);T-data=c;Pop(PTR,rc);T-rchild=rc;/两个叶子结点出栈两个叶子结点出栈 Pop(PTR,lc);T-lchild=lc;/建子树建子树 /遍历
46、时先左后右，左子树先入栈，遍历时先左后右，左子树先入栈，/所以必须先弹出右子树所以必须先弹出右子树 Push(PTR,T);/子树入子树入PTR树栈保存树栈保存100 Zhihai WANG,2015void CrtExptree(BiTree&T,char exp)InitStack(S);Push(S,#);InitStack(PTR);p=exp;ch=*p;/PTR数栈放树和结点，数栈放树和结点，S栈放字符和运算符栈放字符和运算符 while(!(GetTop(S)=#&ch=#)if(!IN(ch,OP)CrtNode(t,ch);/读入的是字符，读入的是字符，/建立叶子结点并入栈，
47、建立叶子结点并入栈，#号号:表达式的开始和结束，表达式的开始和结束，OP:OP:运算符集合运算符集合 else /代表读入的是运算符代表读入的是运算符 if(ch!=#)p+;ch=*p;/未结束时指针后未结束时指针后移移 /while Pop(PTR,T);/从从PTR栈中弹出最后的一棵树栈中弹出最后的一棵树/CrtExptree 101 Zhihai WANG,2015switch(ch)case(:Push(S,ch);break;/表示读入的表示读入的ch是是“(”case):Pop(S,c);/表示读入的表示读入的ch是是“)”while(c!=()/栈顶不是栈顶不是“(”CrtSu
48、btree(t,c);/按栈顶元素建子树并入栈按栈顶元素建子树并入栈 Pop(S,c);break;defult:/表示读入的表示读入的ch是其他运算符是其他运算符/switch 102 Zhihai WANG,2015while(!Gettop(S,c)&(precede(c,ch)/栈顶元素栈顶元素c c的运算优先级的运算优先级大于大于刚读入的刚读入的chch运算符运算符的优先级的优先级 CrtSubtree(t,c);/按栈顶元素建子树按栈顶元素建子树 Pop(S,c);/弹出栈顶元素弹出栈顶元素 if(ch!=#)Push(S,ch);/将将chch运算符入栈运算符入栈break;10
49、3 Zhihai WANG,2015 仅知二叉树的先序序列“abcdefg”能否唯一确定一棵二叉树？(3)由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子左子树树左子左子树树右子右子树树右子右子树树根根根根不能不能104 Zhihai WANG,2015a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列105 Zhihai WANG,2015void CrtBT(BiTree&T,char pre,char ino,in
50、t ps,int is,int n)/已知已知preps.ps+n-1为二叉树的先序序列为二叉树的先序序列，/inois.is+n-1为二叉树的中序序列，本算法由此为二叉树的中序序列，本算法由此两个序列构造二叉链表两个序列构造二叉链表,ps为先序序列的开始位置，为先序序列的开始位置，is为中序序列的开始位置，为中序序列的开始位置，n为序列长度为序列长度 if(n=0)T=NULL;else k=Search(ino,preps);/查询查询先序序列中的先序序列中的 /第一个字符第一个字符在中序序列中的位置在中序序列中的位置 if(k=-1)T=NULL;else /CrtBT 106 Zhih