数据结构课程的内容1第6章 树和二叉树（ Tree Preorder (bt-rchild) ; A ABCDEFGHJI二叉树的遍历1）中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树 2）访问根结点 3）中序遍历右子树算法描述: void Inorder (BiTree bt) /bt为根结点指针if( bt) /根非空 Inorder (bt-lchild) ;visit (bt-data)visit (bt-data)；Inorder (bt-rchild) ; 362）后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根结点算法描述: void Postorder (BiTree bt) /bt为根结点指针if( bt) /根非空 Postorder (bt-lchild) ; Postorder (bt-rchild) ; visit (bt -data)visit (bt -data)； 对遍历的分析：371. 从前面的三种遍历算法可以知道：如果将print语句抹去， 从递归的角度看，这三种算法是完全相同的，或者说这三种 遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径 上，每个结点经过3次。AFEDCBG第1次经过时访问先序遍历 第2次经过时访问中序遍历 第3次经过时访问后序遍历2. 二叉树遍历的时间效率和空间效率 时间效率:O(n)O(n) /每个结点只访问一次 空间效率:O(n)O(n) /栈占用的最大辅助空间 （精确值：树深为k的递归遍历需要k+1 个辅助单元！）38知识回顾：（1）二叉树的存储：顺序存储方式：完全二叉树满二叉树一般树补充成的完全二叉树或满二叉树链式存储方式：适用于各种树（2）二叉树的遍历：先序遍历、中序遍历、后序遍历、层序遍历39ABJIDCGFEH1、先序遍历的结果为 ：2、中序遍历的结果为 ：3、后序遍历的结果为 ：A B D H E C F I G JD H B E A F I C J GH D E B I F J G C特点：先访问根，再遍历左子树，再遍历右子树特点：先遍历左子树，再访问根，再遍历右子树特点： 先遍历左子树，再遍历右子树最后访问根，注：要实现遍历运算必须先把二叉树存入机内。40思路：利用前序遍历来建树 （结点值陆续从键盘输入，用DLR为宜）Status createBiTree( BiTree if(ch=#)T=NULL; elseif(!(T=( BiTNode * )malloc(sizeof(BinTNode);T-data=ch;createBiTree(T-lchild);createBTpre(T-lchild); return T;怎样建树？见教材P131程序。例：编写递归算法，计算二叉树中叶子结点的数目。 41思路：输出叶子结点比较简单，用任何一种遍历算法，凡 是左右指针均空者，则为叶子，将其统计并打印出来。 DLR(BiTree *root) if ( root!=NULL ) if(!root-lchild printf(“%dn“,root-data);DLR(root-lchild); /递归遍历左子树，直到叶子处；DLR(root-rchild); /递归遍历右子树，直到叶子处；习题讨论：421. 1. 求二叉树深度，或从求二叉树深度，或从x x结点开始的子树深度。结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右 )指针非空，则层次数加1；否则函数返回。左 子 树右 子 树根hlhrHeight=max(hl,hr)+1AFEDCBG43后序遍历求二叉树的高度递归算法：Int PostTreeDepth(BiTree bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth（bt-Lchild); /求左子树的深度hr=PostTreeDepth(bt-Rchild); /求右子树的深度max=hlhr?hl:hr; /*得到左、右子树深度较大者*/return (max+1); /*返回树的深度*/else return 0;442. 2. 按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各 子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：当根结点出队后，令其左、右孩子结点入队，而左孩子 出队时又令它的左右孩子结点入队，由此便可产生按层次 输出的效果。ADFCGEHBVoid Layout(BiTree root) EnQueue(s,root);While(!QueueEmpty(s) DeQueue(s,p);printf(“%c”,s-data);EnQueue(s,p-lchild);EnQueue(s,p-rchild); 6.3.3 6.3.3 遍历的非递归遍历的非递归( (迭代迭代) )算法算法以中序遍历以中序遍历45算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则 ，必用堆栈。可直接用while语句和push/pop操作。参见教材 P130-131程序。 在中序遍历中，我们是通过顺着左子树的 根直走到最左端，然后访问最左端元素， 遍历右，再返回上一层，访问结点，遍历 右，然后再访问上一层，这样又顺着左子 树的根回到A。在递归调用中，返回上一层的操作是通过 调用函数执行结束自然返回上一层的。如 果不用递归，如何返回上一层。先从A走到F，在从F返回到A，最后走到的 先访问，所以可以用栈。把根和左子树的根全部入栈然后判断是否有右子树，如果有，则遍历 右子树，HIAFEDCBG46知识回顾：1、按层遍历Void Layout(BiTree root) EnQueue(s,root);While(!QueueEmpty(s) DeQueue(s,p);printf(“%c”,root-data);EnQueue(s,p-lchild);EnQueue(s,p-rchild); ADFCGEHB472、非递归中序遍历HIAFEDCBG首先走到最左边（肯定没有左子树） 接着访问根节点 再非递归中序遍历右子树Status NoInOrderTraverse(BiTree T) InitStack( Push( while(!StackEmpty(S) while(GetTop(S, Pop(if(!StackEmpty(S)Pop(printf(“%c“,p-data);Push( return OK; 482、非递归先序遍历HIAFEDCBGStatus NoInOrderTraverse(BiTree T) InitStack(Push(While(!StackEmpty(S) while(GetTop(S,push( pop(if(!StackEmpty(S) pop(push( 492、非递归后序遍历HIAFEDCBGStatus NoPostTraverse(BiTree T) InitStack( Push( BiTree q;while(!StackEmpty(S)while(GetTop(S,Pop(if(!StackEmpty(S)GetTop(S,if(p-rchild) else Pop( q=p;Push(printf(“%c“,p-data); 50知识回顾：二叉树的建立二叉树的应用：（1）求二叉树叶子节点的个数（2）求二叉树的深度非递归遍历二叉树（1）层序遍历二叉树（2）非递归先序遍历二叉树（3）非递归中序遍历二叉树（4）非递归后序遍历二叉树特别讨论：特别讨论：若已知先序若已知先序/ /后序遍历结果和中序遍历后序遍历结果和中序遍历 结果，能否结果，能否“ “恢复恢复” ”出二叉树？出二叉树？证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵 二叉树。 51例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是 左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG） ；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF 子串可确定F为A的右孩子；以此类推。中序遍历：B D C E A F H G后序遍历：D E C B H G F A52（B D C E）（ F H G）ABF（D C E） （ H G）C D EG HABBFF*536.3.2 6.3.2 线索二叉树线索二叉树 问题的提出：通过遍历二叉树可得到结点的一个线性序列， 在线性序列中，很容易求得某个结点的直接前驱和后继。例如中序遍历结果：B D C E A F H G，实际上已将二叉树转 为线性排列，显然具有唯一前驱和唯一后继！但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱 和后继只有在遍历过程中才能得到，那么，如何保存遍历二叉 树后动态得到的线性序列，以便快速找到某个结点的直接前驱 和后继？增加两个标志域，一个指向前驱、一个指向后继。这样使结构 的存储密度大大降低。54ABDCE置空置空0A10B01D11C01E1置空置空552. 分析：n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个空链域，n-1个指针域；因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结 点的信息。 3. 线索二叉树：有效利用二叉链表中空的存储空间，指定原有的孩子指针为 空的域来存放指向前驱和后继的信息，这样的指针被称为“线索” 。加线索的过程称为线索化，由此得到的二叉树称作线索二叉树 。 (1)规 定 ：1）若结点有左子树，则lchild指向其左孩子；否则， lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则， rchild指向其直接后继(即线索) 。56为了避免混淆，增加两个标志域，如下图所示： lchildLTagdataRTagrchild约定:当Tag域为0时,表示正常情况; 当Tag域为1时,表示线索情况.注：在线索化二叉树中，并不是每个结点都能直接找到其后继的， 当标志为0时，则需要通过一定运算才能找到它的后继。线索链表：用这种结点结构所构成的二叉链表线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树（图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程*57按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树；按后序遍历得到的线索二叉树称为后序线索二叉树；例2：画出以下二叉树对应的中序线索二叉树。58ABCGEIDHFroot悬空？悬空 ？解：该二叉树中序遍历结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：为避免悬空 态，应增设 一个头结点59对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G0-root160（2）整体结构增设一个头结点，令其lchild指向二叉树的根结点ltag=0、 rtag=1；并将该结点作为遍历访问的第一个结点的前驱和最后一个结 点的后继；最