《数据结构(第六章 树和二叉树)复习课程.ppt》由会员分享，可在线阅读，更多相关《数据结构(第六章 树和二叉树)复习课程.ppt（158页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构(第六章树和二叉树)主要内容6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用6.1 树的定义和基本术语树的定义 树是一类重要的非线性数据结构，是以分支关系定义的 层次结构。树的定义如下：树(Tree)是n(n0)个结点的有限集T，如果n=0，称为空树；否则：有且仅有一个称为树的根(root)的结点。其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。ABCDEFGHIJKLM6.1 树的定义和基本术语树的表示形式-一颗倒立的树T1T2T3只含有根结点的树含
2、有子树T1、T2和T3的树对于非空树，其特点：树中至少有一个结点根树中各子树是互不相交的集合6.1 树的定义和基本术语树的其他表示形式凹入表示嵌套集合广义表6.1 树的定义和基本术语树的基本术语n结点(node)表示树中的元素，包括数据项及若干指向其子树的分支n结点的度结点拥有的子树个数n叶子度为0的结点n树的度 一棵树中最大的结点度数(子树数）n孩子结点的子树的根称为 该结点的孩子（结点）n双亲孩子结点的上一层结点 叫该结点的(父结点)n兄弟同一双亲的孩子互称兄弟（结点）n结点的层次从根结点算起，根为第一层，它的孩子为第二层ABCDEF G HIJKLM树的示意图6.1 树的定义和基本术语树
3、的基本术语n树的深度（树高）树中结点的最大层次数n堂兄弟其双亲在同一层的结点互称为堂兄弟。n结点的祖先从根结点到该结点所经分支上的所有结点n结点的子孙以某结点为根的子树中的任一结点都称之为该结点的子孙n有序树和无序树：树中各结点的子树 从左到右有次序（不能互换），称该树为有序树，否则为无序树。（有序树：第一个孩子、第二个孩子）n森林m(m0)棵互不相交的树构成的集合ABCDEF G HIJKLM树的示意图6.1 树的定义和基本术语树的基本术语 就逻辑结构而言，可以森林和树相互递归的定义来描述树：任何一棵非空树是一个二元组:Tree=（root，F）其中：root 被称为根结点,F 被称为子树森
4、林 森林:是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.1 树的定义和基本术语树的基本术语(从根结点到结点的)路径：结点的层次:树的深度：由从根结点到该结点所经分支和结点构成。ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次注意：树的叶子结点不一定都在树的最大层次上6.1 树的定义和基本术语树的基本术语线性结构（1:1）树型结构（1:n）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个一个前驱、一个一个后继)其它数据元素(一个前驱、一个或多个后继
5、)对比线性结构和树型结构的结构特点(a1,a2,a3,an-2,an-1,an)ABCDEFGHIJMKL6.1 树的定义和基本术语树的抽象数据定义数据对象 D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系 R：ADT Tree 基本操作：ADT Tree6.1 树的定义和基本术语树的基本操作查 找 类 插 入 类删 除 类6.1 树的定义和基本术语树的基本操作 Root(T)/求
6、树的根结点 查找类：Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T,Visit()/遍历6.1 树的定义和基本术语树的基本操作InitTree(&T)/初始化置空树 插入类：CreateTree(&T,definition)/按定义构造树Assign(T,cur_e,value)/给当前结点赋值InsertChi
7、ld(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树6.1 树的定义和基本术语树的基本操作 ClearTree(&T)/将树清空 删除类：DestroyTree(&T)/销毁树的结构DeleteChild(&T,&p,i)/删除结点p的第i棵子树6.2 二叉树二叉树的定义定义2：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树定义1：二叉树：度不大于2且有左右之分的树(有序树)（即树中每个结点最多只有两棵子树的有序树）（区别于度为2的树或度不大于2的树）。二叉树的递归定义：其左右子树又都是二叉树。6.2 二
8、叉树二叉树的基本特征1、每个结点最多只有两棵子树。2、子树有左右之分，其次序不能任意 颠倒，是一个有序树。6.2 二叉树二叉树的基本特征N空树空树只含根结点只含根结点NNNLRR右子右子树为树为空空树树L左子树左子树为为空空树树左右子左右子树均不均不为空空树二叉树定义：度不大于2（每个结点最多只有两棵子树）的有序树6.2 二叉树二叉树的主要基本操作查 找 类插 入 类删 除 类 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(
9、T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();6.2 二叉树二叉树的主要基本操作查 找 类 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插 入 类6.2 二叉树二叉树的主要基本操作6.2 二叉树二叉树的主要基本操作ClearBiTree(&T);DestroyBiT
10、ree(&T);DeleteChild(T,p,LR);删 除 类6.2 二叉树二叉树的重要特性性质1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；即第j层上至多有2j-1 个结点。因二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2(i-1)-1 2=2i-1。证明j=i时命题成立第i-1层的结点数123457686.2 二叉树二叉树的重要特性性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：基于上一条性质，深度为 k 的二
11、叉树上的结点数至多为 20+21+2k-1=1*（1-2k）/1-2 =2k-1 6.2 二叉树二叉树的重要特性性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：设 二叉树上结点总数 n=n0+n1+n2 又 设二叉树上分支总数为 b ，则：从前驱(入支）角度（从下向上）有b=n-1 从后继（出支）角度（从上向下）有 b=n1+2n2+0*n0 从而有：n0+n1+n2 1=n1+2n2由此，n0=n2+1。1234566.2 二叉树二叉树的重要特性123456789 10 11 12 13 14 15特点：每一层上的结点数都
12、是最大结点数二叉树性质1：第 i 层上至多有2i-1 个结点。二叉树性质2：深度为k的二叉树至多有2k-1 个结点。满二叉树：指的是深度为k且含有2k 1 个结点的二叉树。6.2 二叉树二叉树的重要特性完全二叉树：若一颗二叉树中所含的 n 个结点与满二叉树中编号为 1 至 n 的结点一一对应(编号和位置一一对应)。特点1.叶子结点只可能在层次最大的两层上出现.2.对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+112345678910 11 12 13 14 15abcdefghijkl6.2 二叉树二叉树的重要特性从完全二叉树定义可知，结点的排列顺序遵循从
13、上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右依次排列，若左边空一个位置时不能将结点放入右边。12311458912136710141512311458912671012345671234566.2 二叉树二叉树的重要特性 性质4：具有 n 个结点的完全二叉树的深度为：log2n+1。证明：设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k-1 或 2k-1 n 2k 两边取对数得：k-1 log2 n k k log2 n +1 n，则该结点无左孩子结点，否则，编号为 2i 的结点为其左孩子结点；(3)
14、若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。示意图j层j+1层 假设编号为i的结点处在第j层的最左边。前j-1层为满二叉树，前j-1层共有2j-1-1 个结点，最后一个结点序号:2j-1-1，则第j层最左边的结点为第2j-1个(即i=2j-1)。同理，有第j+1层，故前j层为满二叉树，前j层共有2j-1 个结点，最后一个结点序号：2j-1，则第j+1层最左边的结点为第2j个。i2=2jj221-x=2i2i+1i2i+22i+3i+1i/26.2 二叉树二叉树的重要特性6.2 二叉树二叉树的重要特性将i的位置推广到一般情况的示意图LCHILD(i)LCHI
15、LD(i+1)RCHILD(i)RCHILD(i+1)6.2 二叉树二叉树的存储结构二叉树的链式存储二叉树的顺序存储6.2 二叉树二叉树的顺序存储 二叉树的顺序存储表示是用一组连续存储空间（一维数组）依次从上到下、从左到右存储完全二叉树中的所有结点，亦即完全二叉树编号为 i 的结点存到一维数组的第 i-1 的位置中。若该二叉树为非完全二叉树，则必须将相应位置空出来或用0补充，使存放的结果符合完全二叉树形状。为方便存储常需要把二叉树中补充成完全二叉树形状，如下图所示。6.2 二叉树二叉树的顺序存储完全二叉树0 1 2 3 4 5 6 7 8 9 10 116.2 二叉树二叉树的顺序存储Xabcd
16、efga b c d e f g0 1 2 3 4 5 6a b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10 二叉树的顺序存储表示的特点：仅适合存储完全二叉树，不适合一般二叉树。极端情况：深度为k的二叉树是仅有k个结点的右单分支，需要长度为2k-1的一维数组。例如:深度为4，且仅有4个结点的右单分支ABCD1 A 0 B 0 0 0 C D 0 1 2 3 4 5 6 146.2 二叉树二叉树的顺序存储#define MAX_TREE_SIZE 100 /二叉树的最大结点数#define TElemType char /二叉树的数据元素类型：chartyp
17、edef TElemType SqBiTreeMAX_TREE_SIZE;/二叉树顺序存储的数据类型定义，char一维数组 /0号单元存储根结点SqBiTree bt;/定义一个二叉树顺序存储的数据类型变量bt6.2 二叉树二叉树的顺序存储6.2 二叉树二叉树的链式存储1.二叉链表2三叉链表3双亲链表4线索链表考虑：l二叉树的数据元素之间的关系l任一个结点，最多有两个孩子（直接后继元素）l二叉链表：l将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。dataLChild RChild特点：找孩子容易，但不利于找双亲LChilddataRChild结点结构
18、ABC6.2 二叉树二叉树的链式存储二叉链表ABCDEFG思考:在n个结点的二叉链表中,有多少个空指针域?n个结点共有2n个指针，除了根结点没有指向他的指针外，其余的结点都有且仅有一个指向它的指针，n-1个结点应共有n-1个指针指向，所以空指针为2n-（n-1）=n+1ABCDE FGLChilddataRChild结点结构root6.2 二叉树二叉树的链式存储二叉链表typedef struct BiTNode /结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rch
19、ild结点结构:二叉链表C 语言的类型描述如下:#define TElemType char/二叉树的数据元素类型：char特点：找孩子容易，但不利于找双亲6.2 二叉树二叉树的链式存储二叉链表6.2 二叉树二叉树的链式存储三叉链表ADEBCF root parent lchild data rchild结点结构:ABCDEF6.2 二叉树二叉树的链式存储三叉链表typedef struct TriTNode /结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 struct TriTNode *parent;/双亲指针 Tr
20、iTNode,*TriTree;parent lchild data rchild结点结构:三叉链表C 语言的类型描述如下:6.2 二叉树二叉树的链式存储双亲链表 typedef struct BPTNode /结点结构 TElemType data;int *parent;/指向双亲的指针 char LRTag;/该结点是双亲的左、右孩子标志域 BPTNode typedef struct BPTree/树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree6.2 二叉树二叉树的链式存储双亲链表012
21、3456双亲链表示意图 data parent结点结构:LRTagLRRRLABCDEF6.3 遍历二叉树和线索二叉树遍历二叉树问题的提出 二叉树的遍历：按一定规律（顺着某一条搜索路径）访问二叉树中的所有结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出或修改结点的信息等。二叉树的遍历 实际上，也就是要把一个非线性结构的二叉树转化为一个线性结构；“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继，只需从前到后，依次进行即可)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历？即按什么样的搜索路径遍
22、历的问题。6.3 遍历二叉树和线索二叉树遍历二叉树问题的提出6.3 遍历二叉树和线索二叉树遍历二叉树先左后右的遍历算法分析：二叉树的递归定义：DRL 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。可见二叉树有三部分组成：根结点D，左子树L和右子树R由此，遍历二叉树的方案有6种：先左后右：DLR,LDR,LRD 先右后左：DRL,RDL,RLD以下重点讨论先左后右的遍历二叉树方案 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：DLR若左子树为空树，则空操作；否则，（1）访问左子树的根结点；（2）先
23、序遍历左子树的左子树；（3）先序遍历左子树的右子树。DRL6.3 遍历二叉树和线索二叉树遍历二叉树先左后右的遍历算法6.3 遍历二叉树和线索二叉树遍历二叉树先左后右的遍历算法 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：LDR 若左子树为空树，则空操作；否则，（1）中序遍历左子树的左子树；（2）访问左子树的根结点；（3）中序遍历左子树的右子树。DRL6.3 遍历二叉树和线索二叉树遍历二叉树先左后右的遍历算法 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：
24、LRDD 若左子树为空树，则空操作；否则，（1）后序遍历左子树的左子树；（2）后序遍历左子树的右子树；（3）访问左子树的根节点。DRL6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述typedef struct BiTNode /结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针*BiTree;lchild data rchild结点结构:二叉链表C 语言的类型描述如下:#define TElemType char/二叉树的数据元素类型：char6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述先序遍历算法的递归描述v
25、oid Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点.可以是输出coutdata Preorder(T-lchild,visit);/先序遍历左子树 Preorder(T-rchild,visit);/先序遍历右子树 若二叉树为空树，则空操作；否则，（1）访问根结点；visit(T-data);（2）先序遍历左子树；（3）先序遍历右子树。6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述void preorder(BiTree*bt)if(bt!=NULL)printf(%dt,bt
26、-data);preorder(bt-lchild);preorder(bt-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C中序遍历算法的递归描述void Inorder(BiTree T,void(*visit)(TElemType&e)/中序
27、遍历二叉树 if(T T)Inorder(T-lchild,visit);/中序遍历左子树 visit(T-data);/访问根结点 Ineorder(T-rchild,visit);/中序遍历右子树 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述l3种遍历算法不同之处仅在于访问根结点、遍历左子树、遍历右子树的先后关系。若不考虑visit()语句，则三种遍历方法完全相同（访问路径是相同的，只是访问结点的时机不同）。三种遍历算法均是递归算法：
28、树的定义本身就是递归的；递归和栈密切联系：递归过程实际就是对栈的操作过程 可以直接通过对栈的操作，来把递归算法写为非递归算法从虚线的出发点到终点的路径上，每个结点经过3次。第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历6.3 遍历二叉树和线索二叉树遍历二叉树算法的递归描述6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)弹弹出出出出栈顶栈顶C C弹弹出出出出栈顶栈顶B B6.3 遍历二叉树和线索
29、二叉树遍历二叉树中序遍历算法的非递归过程pABCDEFGiP-A访问：C B B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B E Ep(8)D D入入入入栈栈E E入入入入栈栈GG入入入入栈栈弹弹出出出出栈顶栈顶E E6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G D Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP
30、-D访问：C B E GGp(10)6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程ABCDEFGiP-A访问：C B E G D F Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap=NULL(15)ABCDEFGi访问：C B E G D F A Ap(14)中序遍历的非递归算法思路：设待遍历的二叉树的根结点指针为T（算法开始时，令p=T），则可能出现两种情况：1、若p不空，则先按中序次序遍历T（p）的左子树，然后打印p-data,再按中序次序遍历p的右子树。为此，在遍历p的左子树前要保留根结点指针p,以便返回后再打印p-data，接着遍历其右子树。
31、2、若p为空，则表明以p为根的二叉树遍历完毕，应该返回（同时也表明对某子树 T 的左子树p遍历完毕，下面应该访问 T的根结点，并对其右子树遍历，如上图）。此时，若栈不空，则栈顶元素一定为T，取出栈顶的指针并赋予p，在访问完p之后，继续遍历其右子树；若栈为空，则整个二叉树遍历完毕。6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程开始初始化栈Sp=NULL初始化指针p=Tp入栈入栈p=p-Lchild栈顶元出栈：栈顶元出栈：p打印打印p-datap=p-Rchild栈空吗？栈空吗？结束NNYYP和和栈均空均空吗？Y中序
32、遍历的非递归算法流程图6.3 遍历二叉树和线索二叉树遍历二叉树中序遍历算法的非递归过程Status InOrderTraverse(BiTree T,status(*visit)(TElemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)/根指针进栈，遍历左子树 Push(S,p);p=p-pLChild;else/根指针出栈,访问根结点,遍历右子树 Pop(S,p);if(!(*Visit)(p-data)return ERROR;p=p-pRChild;/右子树/else /while return OK;/InOrderTravers
33、e6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例1、统计二叉树中结点的个数(先序遍历)2、求二叉树的深度(后序遍历)3、复制二叉树(后序遍历)4、建立二叉树的存储结构说明:二叉树的所有算法都是建立在遍历的基础上的，故二叉树的应用也是以遍历为基础，或者说以遍历为主框架。在应用遍历算法时，不同的问题需要对其中的“访问结点”操作作适当的修改。6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是该结点非空，则计数器增1。void
34、 Preorder(BiTree T,void(*visit)(TElemType&e)if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/先序遍历左子树 Preorder(T-rchild,visit);/先序遍历右子树 1、统计二叉树中结点的个数6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例void Countnode(BiTree T,int&node)/在实际使用时，node作为全局变量，其初始值为0 if(T)node+;Countnode(T-lchild,node);Countnode(T-rchild,node);/
35、if/Countnode统计二叉树中结点的个数6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。void Preorder(BiTree T,void(*visit)(TElemType&e)if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/先序遍历左子树 Preorder(T-rchild,visit);/先序 遍历右子树 vo
36、id CountLeaf(BiTree T,int&count)/在实际使用时，count作为全局变量，其初始值为0 if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例统计二叉树中叶子结点的个数6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例2、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此
37、，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1。首先分析二叉树的深度和它的左、右子树深度之间的关系。6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例求二叉树的深度(后序遍历)int Depth(BiTree T)/返回二叉树的深度 if(T)depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);else depthval=0;return depthval;3、复制二叉树其
38、基本操作为：生成一个结点。根元素根元素T左子左子树右子右子树根元素根元素NEWT左子左子树右子右子树左子左子树右子右子树(后序遍历)DRL6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例6.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;生成一个二叉树的结点(其数据域为
39、item,左指针域为lptr,右指针域为rptr)6.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;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;/CopyTree6.3 遍
40、历二叉树和线索二叉树遍历二叉树遍历算法的应用举例ABCDEFGHK D C B H K G F E A例如：下列二叉树的复制过程如下：newT6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例4、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例以字符串的形式定义一棵二叉树例如:ABCD以空白字符“”表示空树只含一个根结点的二叉树A以字符串“A ”表示根 左子树 右子树 （先序序列）A B ,C ,D ,以下列字符串表示int CreateBiTree(BiTree&T)scanf(&ch);/cinch;if(c
41、h=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree以字符串的形式定义一棵二叉树6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例A BCDATBCD6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例上页算法执行过程举例如下：6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例abcde-+
42、/特点：操作数为叶子结点 运算符为分支结点已知表达式(a+b)c d/e，建立二叉树6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例a+b(a+b)c d/ea+bc 分析表达式和二叉树的关系:ab+abc+abc+(a+b)cabcde-+/表达式的先序遍历（前缀表示）：-+a b c/d eabcde-+/6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例表达式的中序遍历（中缀表示）：a+b c d/e表达式的后序遍历（后缀表示）：a b+c d e/-仅知二叉树的先序序列”abcdefg”不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列”cbdaegf”，则会如何？
43、由二叉树的先序和中序序列建树二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根确定原则：由先序序列确定二叉树的根结点，由中序序列确定二叉树的左右子树序列。6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列中序序列由二叉树的先序和中序序序列确定二叉树6.3 遍历二叉树和线索二叉树遍历二叉树遍历算法的应用举例6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树说明：通过遍历二叉树，可把二叉树的非线性结构转化为线性结构，求得结点的一个线性序列。问题
44、：在以二叉链表表示二叉树时，各种线性序列中结点间的前驱和后继关系 只能在遍历时才能得到。ABCDEFGHK例如:先序序列:A B C D E F G H K中序序列:B D C A H G K F E后序序列:D C B H K G F E A6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树指向该线性序列中的“前驱”和 “后继”的指针，称作“线索”（以区别二叉链表中的指针，二叉链表中空指针做线索）通过遍历二叉树，可求得结点的一个线性序列。在任一序列中，除了第一个和最后一个结点外，其余结点有且仅有一个直接前驱和直接后继。但是在以二叉链表表示二叉树时，这些不同遍历序列的直接前驱和直接后继信息
45、只能在遍历过程中才能得到。为此我们可以在二叉链表的结点结构中增设两个指向前驱和后继的指针域，但考虑到二叉链表中的2n个指针域中，有n+1个空指针域，为充分利用空间，可以考虑用这些空指针域来保存前驱和后继指针信息。A B C D E F G H K D C B E 包含“线索”的存储结构，称作“线索链表”6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域LTag的值为“指针 Link”；否则，lchi
46、ld域的指针指向其“前驱”，且左标志域LTag的值为“线索 Thread”。lchildLTagdataRTagrchild若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域RTag的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志RTag的值为“线索Thread”。0 lchild域指示结点的左孩子，表示lchild为左孩子指针 Ltag=1 lchild域指示结点的前驱，表示lchild为线索 0 rchild域指示结点的右孩子，表示rchild为右孩子指针 Rtag=1 rchild域指示结点的后驱，表示rchild为线索 以这种结构构成的二叉
47、链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11先序线索二叉树举例ABCDE A B D C ET中序序列：BCAED中序线索二叉树0000111111中序线索二叉树举例6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树ABCDE A B D C ET后序序列：CBEDA后序线索二叉树0000111111后序线索二叉树举例ABCDE
48、0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1头结点：LTag=0,lchild 指向根结点RTag=1,rchild指向遍历序列中 最后一个结点遍历序列中第一个结点的lchild和最后一个结点的rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉树00001111116.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树中序线索二叉树加头结点6.3 遍历二叉树和线索二叉树线索二叉树何谓线索二叉树typedef struct BiThrNod TElemType data;struct BiThrN
49、ode *lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索6.3 遍历二叉树和线索二叉树线索二叉树线索链表的遍历算法 for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。某种遍历序列中的第一个结点 求该结点的后继 中序遍历的第一个结点？求中序线索化链表中某结点的后继
50、？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为 后继线索所指结点；否则为对其右子树进行 中序遍历时访问的第一个结点。ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 16.3 遍历二叉树和线索二叉树线索二叉树线索链表的遍历算法6.3 遍历二叉树和线索二叉树线索二叉树线索链表的遍历算法void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)/T指向头结点,头结点的lchild左链指向根结点，中序遍历二叉线索树的非递归算法,对每个数据元素调用