第四章树与树的表示(二)

1、 二叉树的遍历遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。 二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是：DLR先(根)序

2、遍历。LDR中(根)序遍历。LRD后(根)序遍历。对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用堆栈来实现的。（1）先序遍历遍历过程为： 访问根结点；A（B D F E ）（C G H I） 先序遍历其左子树； 先序遍历其右子树。先序遍历=A B D F E C G H Ivoid PreOrderTraversal( BinTree BT )if( BT ) printf(“%d”, BT-Data);2B1A6 CPreO

3、rderTraversal( BT-Left );PreOrderTraversal( BT-Right );3D5E4F79G8 HI56（2）中序遍历遍历过程为：（D B E F） A （G H C I） 中序遍历其左子树； 访问根结点；中序遍历=D B E F A G H C I 中序遍历其右子树。Avoid InOrderTraversal( BinTree BT )if( BT ) InOrderTraversal( BT-Left );printf(“%d”, BT-Data);InOrderTraversal( BT-Right );1D3B2EF4C8G7 H9IA 92I（3

4、）后序遍历遍历过程为： 后序遍历其左子树； 后序遍历其右子树；（D E F B ）（ H G I C） A 访问根结点。后序遍历=D E F B H G I C Avoid PostOrderTraversal( BinTree BT )if( BT ) PostOrderTraversal( BT-Left );PostOrderTraversal( BT-Right);printf(“%d”, BT-Data);1DB 4F3EC 867G5 H先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。图中在从入口到出口的曲线上用三种符号分别标记出了先序、中序和后序

5、访问各结点的时刻入口.BA出口CDEFGHI二叉树的非递归遍历中序遍历非递归遍历算法非递归算法实现的基本思路：使用堆栈B入口A出口CDEFGHI中序遍历非递归遍历算法 遇到一个结点，就把它压栈，并去遍历它的左子树； 当左子树遍历结束后，从栈顶弹出这个结点并访问它； 然后按其右指针再去中序遍历该结点的右子树。void InOrderTraversal( BinTree BT ) BinTree T=BT;Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈创建并初始化堆栈S*/while( T | !IsEmpty(S) )while(T)/*一直向左并将沿途结

6、点压入堆栈一直向左并将沿途结点压入堆栈*/Push(S,T);T = T-Left;if(!IsEmpty(S)T = Pop(S); /*结点弹出堆栈结点弹出堆栈*/printf(“%5d”, T-Data); /*（访问）打印结点（访问）打印结点*/T = T-Right; /*转向右子树转向右子树*/层序遍历存储结构：队列层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。为保证是按层次遍历，必须设置一个队列，初始化时为空。设T是指向根结点的指针变量，层次遍历非递归算法是：若二叉树为空，则返回；否则，令p=T，p入队； 队首元素出队到p；访问p所指向的结

7、点； 将p所指向的结点的左、右子结点依次入队。直到队空为止。层序基本过程：先根结点入队，然后：从队列中取出一个元素；访问该元素所指结点；若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。void LevelOrderTraversal ( BinTree BT )Queue Q; BinTree T;if ( !BT ) return; /* 若是空树则直接返回 */Q = CreatQueue( MaxSize ); /*创建并初始化队列创建并初始化队列Q*/AddQ( Q, BT );while ( !IsEmptyQ( Q ) ) T = DeleteQ( Q );p

8、rintf(“%dn”, T-Data); /*访问取出队列的结点访问取出队列的结点*/if ( T-Left ) AddQ( Q, T-Left );if ( T-Right ) AddQ( Q, T-Right );层序遍历A B CD FG I E H1A层序遍历 = A B CD FG I E H2B3C4D 5E8F6 G97HI“遍历”是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、求二叉树的深度等。二叉树遍历算法的应用【例】遍历二叉树的应用：输出二叉树中的叶子结点。 在二叉树的遍历算法中增加检测结

9、点的“左右子树是否都为空”。void PreOrderPrintLeaves( BinTree BT )if( BT ) if ( !BT-Left & !BT-Right )printf(“%d”, BT-Data );PreOrderPrintLeaves ( BT-Left );PreOrderPrintLeaves ( BT-Right );【例】求二叉树的高度。HL左子树右子树HRHeight=max(HL, HR)+1int PostOrderGetHeight( BinTree BT )int HL, HR, MaxH;if( BT ) HL = PostOrderGet

10、Height(BT-Left); /*求左子树的深度求左子树的深度*/HR = PostOrderGetHeight(BT-Right); /*求右子树的深度求右子树的深度*/MaxH = （HL HR）? HL : HR; /*取左右子树较大的深度取左右子树较大的深度*/return ( MaxH + 1 ); /*返回树的深度返回树的深度*/else return 0; /* 空树深度为0 */【例】 二元运算表达式树及其遍历+*a*+gbcd*ef中缀表达式会受到运算符优先级的影响 三种遍历可以得到三种不同的访问结果： 先序遍历得到前缀表达式：+ + a * b c * + * d e

11、f g 中序遍历得到中缀表达式：a + b * c + d * e + f * g 后序遍历得到后缀表达式：a b c * + d e * f + g * +【例】 由两种遍历序列确定二叉树答案是：必须要有中序遍历才行！已知三种遍历中的任意两种遍历序列，能否唯一确定一棵二叉树呢？没有中序的困扰： 先序遍历序列：A B 后序遍历序列：B ABAAB 先序和中序遍历序列来确定一棵二叉树分析 根据先序遍历序列第一个结点确定根结点； 根据根结点在中序遍历序列中分割出左右两个子序列 对左子树和右子树分别递归使用相同的方法继续分解。先序序列中序序列根结点左子树右子树左子树根结点右子树aai例 先序序列：中

12、序序列：bcbedb c d ec b e d ahg f jff g h i jh g i j f左子树（或右子树）序列不配套意味着什么？cedhgij 类似地，后序和中序遍历序列也可以确定一棵二叉树。4.4 什么是二叉搜索树一、定义二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树，是一种对排序和查找都很有用的特殊二叉树。二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：（1）非空左子树的所有键值小于其根结点的键值。（2）非空右子树的所有键值大于其根结点的键值。（3）左、右子树都是二叉搜索树。二、二叉搜索树的动态查找二叉搜索树操作的特别函数：P

13、osition Find( ElementType X, BinTree BST )：从二叉搜索树BST中查找元素X，返回其所在结点的地址；Position FindMin( BinTree BST )：从二叉搜索树BST中查找并返回最小元素所在结点的地址；Position FindMax( BinTree BST ) ：从二叉搜索树BST中查找并返回最大元素所在结点的地址。BinTree Insert( ElementType X, BinTree BST )BinTree Delete( ElementType X, BinTree BST )1.二叉搜索树的查找操作：Find查找从根结点

14、开始，如果树为空，返回NULL若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：l若X小于根结点键值，只需在左子树中继续搜索；l如果X大于根结点的键值，在右子树中进行继续搜索；若两者比较结果是相等，搜索完成，返回指向此结点的指针。都是“尾递归”Position Find( ElementType X, BinTree BST )if( !BST ) return NULL; /*查找失败查找失败*/if( X BST-Data )return Find( X, BST-Right ); /*在右子树中继续查找在右子树中继续查找*/Else if( X Data )return Find

15、( X, BST-Left ); /*在左子树中继续查找在左子树中继续查找*/else /* X = BST-Data */return BST; /*查找成功，返回结点的找到结点的地址查找成功，返回结点的找到结点的地址*/ 由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数Position IterFind( ElementType X, BinTree BST )while( BST ) if( X BST-Data )BST = BST-Right; /*向右子树中移动，继续查找向右子树中移动，继续查找*/else if( X Data )BST = BST-Left; /*向左

16、子树中移动，继续查找向左子树中移动，继续查找*/else /* X = BST-Data */return BST; /*查找成功，返回结点的找到结点的地址查找成功，返回结点的找到结点的地址*/return NULL; /*查找失败查找失败*/查找的效率决定于树的高度2.查找最大和最小元素最大元素一定是在树的最右分枝的端结点上最小元素一定是在树的最左分枝的端结点上181020最左端点71522最右端点9Position FindMin( BinTree BST )if( !BST ) return NULL; /*空的二叉搜索树，返回空的二叉搜索树，返回NULL*/else if( !BST-

17、Left )elsereturn BST; /*找到最左叶结点并返回找到最左叶结点并返回*/return FindMin( BST-Left ); /*沿左分支继续查找沿左分支继续查找*/查找最小元素的递归函数Position FindMax( BinTree BST )if(BST )while( BST-Right ) BST = BST-Right;/*沿右分支继续查找，直到最右叶结点沿右分支继续查找，直到最右叶结点*/return BST;查找最大元素的迭代函数三、二叉搜索树的插入分析关键是要找到元素应该插入的位置，可以采用与Find类似的方法353030154115334150333

18、550BinTree Insert( ElementType X, BinTree BST )if( !BST )/*若原树为空，生成并返回一个结点的二叉搜索树若原树为空，生成并返回一个结点的二叉搜索树*/BST = malloc(sizeof(struct TreeNode);BST-Data = X;BST-Left = BST-Right = NULL;else /*开始找要插入元素的位置开始找要插入元素的位置*/if( X Data )BST-Left = Insert( X, BST-Left);/*递归插入左子树递归插入左子树*/else if( X BST-Data )BST-R

19、ight = Insert( X, BST-Right);/*递归插入右子树递归插入右子树*/* else X已经存在，什么都不做已经存在，什么都不做 */return BST;二叉搜索树的插入算法【例】以一年十二个月的英文缩写为键值，按从一月到十二月顺序输入，即输入序列为（Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep,Oct, Nov, Dec）JanFebMarAprAugJunJulyDecNovMaySeptOct四、二叉搜索树的删除考虑三种情况：要删除的是叶结点：直接删除，并再修改其父结点指针-置为NULL例：删除 353015要删除结点33413550 要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点例：删除 33303015411541要删除结点33503550（只有一个孩子）35要删除的结点有左、右两棵子树：用另一结点替代被删除结点：右子树的最小元素 或者 左子树的最大元素例：删除 413030153341501533415035341、取右子树中的最小元素替代35342、取左子树中的最大元