《数据结构与算法设计PPT (24).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (24).pdf（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 树6.4 二叉树的遍历二叉树的遍历T 令L，r和R代表访问左子树，访问根结点、右子树。T 遍历有六种可能的组合LRr，LrR，rLR，RLr，RrL，rRLT 约定先左后右遍历，仅剩下3中种遍历顺序LRr，LrR，rLRT 后根序遍历、中根序遍历、先根序遍历深度优先遍历Data Structure先根序遍历 若二叉树非空（1）访问根结点（2）先根序遍历左子树（3）先根序遍历右子树AlgorithmPreOrder(v)if(v非空)visit(v);PreOrder(leftChild(v);PreOrder(rightChild(v);532618974先根序遍历过程template
2、 void BinaryTree:PreOrder()PreOrder(root);template void BinaryTree:PreOrder(BinTreeNode *current)if(current!=NULL)cout currentdata;PreOrder(currentleftChild);PreOrder(currentrightChild);先根序遍历算法的实现中根序遍历 若二叉树非空（1）中根序遍历左子树（2）访问根结点（3）中根序遍历右子树AlgorithminOrder(v)if(v非空)inOrder(leftChild(v);visit(v);inOrde
3、r(rightChild(v);312567984中根序遍历过程template void BinaryTree:InOrder()InOrder(root);template void BinaryTree:InOrder(BinTreeNode *current)if(current!=NULL)InOrder(currentleftChild);cout currentdata;InOrder(currentrightChild);中根序遍历算法实现后根序遍历 若二叉树非空（1）后根序遍历左子树（2）后根序遍历右子树（3）访问根结点AlgorithmPostOrder(v)if(v非空)
4、PostOrder(leftChild(v);PostOrder(rightChild(v);visit(v);215396784template voidBinaryTree:PostOrder()PostOrder(root);template void BinaryTree:PostOrder(BinTreeNode *current)if(current!=NULL)PostOrder(currentleftChild);PostOrder(currentrightChild);cout currentdata;后根序遍历算法的实现试一下1 12 23 34 45 56 6先跟序列:?
5、中根序列?后根序列?7 710101 12 23 34 45 56 69 98 8计算二叉树结点个数 若二叉树为空返回0 若二叉树非空问题分解求解（1）l=递归递归求左子树个数（2）r=递归调用求右子树个数解的合并返回 l+r+1template int BinaryTree:Size(constBinTreeNode*t)const if(t=NULL)return 0;else return 1+Size(tleftChild)+Size(trightChild);计算二叉树高度 若二叉树为空返回-1 若二叉树非空（1）lh=递归递归求左子树个数（2）rh=递归调用求右子树个数返回 max
6、（lh，rh）+1template int BinaryTree:Depth(const BinTreeNode *t)const if(t=NULL)return-1;else return 1+Max(Depth(tleftChild),Depth(trightChild);一个二叉树的先根序列：ABECDFGHIJ二叉树的中根序列：EBCDAFHIGJ 求二叉树的结构？ABECDFGHIJ ABECDFGHIJ ABECDFGHIJEBCDAFHIGJEBCD FHIGJE CDHIGJAEBCDFHIGJABECDHIGJFABEHIGJFCD根据两种序列确定二叉树的结构输入二叉树的先
7、根序遍历顺序能否将实例输入计算机？AFEDCB*使用*说明空树A B D*F*C E*先根序遍历顺序：A B D F C E 如何创建二叉树？template void BinaryTree:CreateBinaryTree()CreateBinaryTree(root);通过先根序遍历顺序创建二叉树template void BinaryTree:CreateBinaryTree(BiTreeNode*&T)scanf(&ch);/get a charif(ch=*)T=NULL;/if it denotes an empty treeelse if(!(T=new BiTreeNode()
8、exit(1);/allocated failedT-data=ch;CreateBiTree(T-leftChild);/creates its left subtreeCreateBiTree(T-rightChild);/creates its right subtreereturn OK;通过先根序遍历顺序创建二叉树递归VS非递归 函数调用时用运行时栈保存返回地址调用者将参数放在栈中，并将控制权传递给被调用者。局部变量在运行时栈上分配存储空间由于有运行时栈保障递归可以顺利执行但是控制转移有时间开销运行时栈有空间开销 a a +*/d d -T T e e b b c c Caller:
9、Caller:遍历T T为根的二叉树InorderTraverseInorderTraverse(BinTreeBinTree T)T)if(T)if(T)InorderTraverseInorderTraverse(T(T-lchildlchild););printfprintf(“%(“%c”,Tc”,T-data);data);InorderTraverseInorderTraverse(T(T-rchildrchild););TLTLCallee:Callee:遍历遍历TLTL为根的二叉树为根的二叉树InorderTraverseInorderTraverse(BinTreeBinTr
10、ee T)T)if(T)if(T)InorderTraverseInorderTraverse(T(T-lchildlchild););printfprintf(“%(“%c”,Tc”,T-data);data);InorderTraverseInorderTraverse(T(T-rchildrchild););TLTLT T返回地址返回地址TLTL返回地址返回地址栈栈非递归遍历 通过使用显式堆栈来实现非递归遍历版本 显示堆栈代替运行时栈，用于存储需要返回的结点指针 二叉树的遍历（DLR遍历过程6）acdfghnwoumxfocumaxndhwfocuggmaxndha的指针的指针a的指针的
11、指针c的指针的指针a的指针的指针c的指针的指针f的指针的指针a的指针的指针c的指针的指针f的指针的指针w的指针的指针a的指针的指针c的指针的指针f的指针的指针wa的指针的指针c的指针的指针a的指针的指针c的指针的指针o的指针的指针a的指针的指针c的指针的指针a的指针的指针a的指针的指针g的指针的指针非递归遍历算法的实现template void BinaryTree:InOrderTraverse()stack S;BiTreeNode*p;S.makeEmpty();p=root;/初始化dowhile(p)S.push(p);p=pleftChild;if(!S.empty()/栈非空p=
12、S.top();S.pop();/退栈cout pdata;/访问根结点p=prightChild;/向右链走 while(p|!S.empty();template void BinaryTree:InOrderTraverse()stack S;BiTreeNode*p;S.makeEmpty();p=root;/初始化dowhile(p)S.push(p);p=pleftChild;if(!S.empty()/栈非空p=S.top();S.pop();/退栈cout pdata;/访问根结点p=prightChild;/向右链走 while(p|!S.empty();非递归遍历算法的实现
13、template void BinaryTree:InOrderTraverse()stack S;BiTreeNode*p;S.makeEmpty();p=root;/初始化dowhile(p)S.push(p);p=pleftChild;if(!S.empty()/栈非空p=S.top();S.pop();/退栈cout pdata;/访问根结点p=prightChild;/向右链走 while(p|!S.empty();非递归遍历算法的实现T 层次由小到大T 内层从左到右T 采用队列辅助遍历层序遍历template void BinaryTree:LevelOrder()QueueBiTreeNode*qu;if(root=NULL)return;qu.EnQueue(root);while(!q.IsEmpty()current=qu.DeQueue();/退队coutdata;if(currentleftChild!=NULL)/左子女qu.EnQueue(currentleftChild);/进队列if(currentrightChild!=NULL)/右子女qu.EnQueue(currentrightchild);/进队列层序遍历算法的实现