实验6╲t 二叉树的遍历.doc
实验6 二叉树的遍历一、实习目的1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序、中序、后序递归和非递归遍历以及二叉树的按层遍历方法。二、实例 二叉树的建立和各种遍历算法在教材中，已经有很详细的介绍。本例题将介绍另外一种建立二叉树的算法。同时介绍对“遍历算法”灵活应用：修改原有二叉树中结点的数值；将二叉树中每个结点的左右子树进行交换。介绍求二叉树深度的算法。178695423本例介绍二叉树的建立是一个递归方法，与二叉树先序遍历思路有点相似。数据的组织是先序遍历的顺序，但是当某结点的某孩子为空时以数据0来充当，也要输入。结合右图的二叉树，其数据的输入顺序应该是：1 2 4 0 0 0 3 5 0 7 0 0 6 8 0 0 9 0 0。若当前数据不为0，则申请一个结点存入当前数据。如果输入0表明是空（NULL），不分配结点。递归调用建立函数，建立当前结点的左右子树。 源程序 #include <iostream.h>#include <conio.h>typedef int ElemType;struct NodeType /定义结点 结构体 ElemType data; NodeType *lch，*rch;class BiTree /定义 二叉树类 class public: BiTree()root=NULL; /构造函数 BiTree()destroy(root) ; /析构函数 void inorder() /中序遍历 inorder(root); void preordertswap() /利用先序遍历方法交换左右子树 preorderswap(root); int theight() /求二叉树高度 return height(root); void creat0(); private: NodeType *root; /数据成员，树根 NodeType *creat(); /建立二叉树递归方法 void inorder(NodeType *p); /中序遍历 void preorderswap(NodeType *p); /利用先序遍历方法交换左右子树 int height(NodeType *p); /求二叉树高度递归算法 void destroy(NodeType* &p); /删除二叉树所有结点 ;void BiTree:creat0() /建立树函数， cout<<"请按照树的先序遍历顺序组织数据"<<endl; cout<<"若结点信息是int，把每个结点的空孩子以0输入;"<<endl; cout<<"一个结点的二叉树11，输入：11 0 0;"<<endl; root=creat(); /调用私有creat(); NodeType * BiTree:creat() /递归建立二叉树算法 NodeType *p; ElemType x; cout<<"n 输入数据：" cin>>x; if( x=0) p=NULL; else p=new NodeType; p->data=x;p->lch=creat(); /递归调用自身p->rch=creat(); return p; void BiTree:inorder(NodeType *p) /中序遍历 if(p != NULL) inorder(p->lch); cout<<p->data<<" " inorder(p->rch);void BiTree:preorderswap(NodeType *p) /利用先序遍历方法交换左右子树 if(p != NULL) NodeType *r; r=p->lch; p->lch=p->rch; p->rch=r;/上面几条语句可以认为对结点的访问（交换左右孩子）/替换了原来的： cout<<p->data<<" " 语句 preorderswap(p->lch); preorderswap(p->rch);void BiTree:destroy(NodeType* &p) /删除二叉树所有结点if(p != NULL) destroy(p->lch);destroy(p->rch);delete p;p = NULL;int BiTree:height(NodeType *p) /求二叉树高度递归 if(p = NULL) return 0; else int hl=height(p->lch); int hr=height(p->rch); return 1 + (hl>hr?hl:hr); /1加上hl和hr的较大值 /-int main() int k; BiTree root0; /声明创建二叉树对象，调用构造函数 do cout<<"nn" cout<<"nn 1. 建立二叉树" cout<<"nn 2. 交换左右子树 " cout<<"nn 3. 求二叉树深度 " cout<<"nn 4. 结束程序运行" cout<<"n=" cout<<"n 请输入您的选择 (0,1,2,3,4):" cin>>k; switch(k) case 1: cout<<"n s输入（0 0）结束：" root0.creat0(); cout<<"n 中先根遍历结果：" root0.inorder(); break; case 2: cout<<"n 交换左右子树结果：" root0.preordertswap(); cout<<"n 中先根遍历结果：" root0.inorder(); break; case 3: int deep;/=root0.theight(); deep=root0.theight(); cout<<"n 树的深度是："<<deep; break; case 4: exit(0); / switchcout<<"n -" while(k>=0 && k<4); _getch(); return 0;/-三、实习题1. 建立一棵二叉树，要求用先序非递归方法遍历二叉树。2建立一棵二叉树，要求用“按层遍历”的方法遍历二叉树。3使用“数据结构算法练习系统”软件环境： （1）Ch06 Ex36写出先序遍历二叉树的非递归算法。 （2）Ch06 Ex38写出后序遍历二叉树的非递归算法。 （3）Ch06 Ex43编写递归算法，将二叉树中的所有结点的左右子树交换。参考：（1）Ch06 Ex36写出先序遍历二叉树的非递归算法void pre_Order( BiTree bt, char ss, int& n ) stack s; BiTLink pp , q; q = NULL; InitStack(s); Push(s, q); pp = bt; n = 0; while ( pp ) ssn+ = pp->data; if ( pp->rchild ) Push(s, pp->rchild); if ( pp->lchild ) pp = pp->lchild; else pp = Pop_BiTLink(s); /while DestroyStack(s);/pre_Order （2）Ch06 Ex38写出后序遍历二叉树的非递归算法。void post_Order( BiTree bt, char ss, int& n ) StackType s; BiTLink p; SNodeType w ; bool right; InitStack(s); n = 0 ; w.ptr = bt; w.tag = 'L' do while ( w.ptr ) Push_SNode(s,w); w.ptr = w.ptr->lchild; right = true; while (!StackEmpty(s) && right ) Pop_SNode(s,w); if ( w.tag = 'R' ) ssn+ = w.ptr->data; else w.tag = 'R' Push_SNode(s,w); right = false; w.ptr = w.ptr->rchild; w.tag = 'L' /else /while while ( !StackEmpty(s) );/post_Order（3）Ch06 Ex43编写递归算法，将二叉树中的所有结点的左右子树交换。void swap( BiTree BT ) BiTLink tempL; if (BT) tempL = BT->lchild;BT->lchild = BT->rchild; BT->rchild = tempL; swap( BT->lchild); swap( BT->rchild);
