实验6╲t 二叉树的遍历.doc

《实验6╲t 二叉树的遍历.doc》由会员分享，可在线阅读，更多相关《实验6╲t 二叉树的遍历.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验6 二叉树的遍历一、实习目的1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序、中序、后序递归和非递归遍历以及二叉树的按层遍历方法。二、实例 二叉树的建立和各种遍历算法在教材中，已经有很详细的介绍。本例题将介绍另外一种建立二叉树的算法。同时介绍对“遍历算法”灵活应用：修改原有二叉树中结点的数值；将二叉树中每个结点的左右子树进行交换。介绍求二叉树深度的算法。178695423本例介绍二叉树的建立是一个递归方法，与二叉树先序遍历思路有点相似。数据的组织是先序遍历的顺序，但是当某结点的某孩子为空时以数据0来充当，也要输入。结合右图的二叉树，其数据的输入顺序应该是：1 2 4 0 0 0

2、 3 5 0 7 0 0 6 8 0 0 9 0 0。若当前数据不为0，则申请一个结点存入当前数据。如果输入0表明是空（NULL），不分配结点。递归调用建立函数，建立当前结点的左右子树。 源程序 #include #include typedef int ElemType;struct NodeType /定义结点 结构体 ElemType data; NodeType *lch，*rch;class BiTree /定义 二叉树类 class public: BiTree()root=NULL; /构造函数 BiTree()destroy(root) ; /析构函数 void inorder

3、() /中序遍历 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(NodeT

4、ype *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; coutx; if( x=0) p=NULL; else p

5、=new NodeType; p-data=x;p-lch=creat(); /递归调用自身p-rch=creat(); return p; void BiTree:inorder(NodeType *p) /中序遍历 if(p != NULL) inorder(p-lch); coutdatarch);void BiTree:preorderswap(NodeType *p) /利用先序遍历方法交换左右子树 if(p != NULL) NodeType *r; r=p-lch; p-lch=p-rch; p-rch=r;/上面几条语句可以认为对结点的访问（交换左右孩子）/替换了原来的： co

6、utdatalch); 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 + (hlhr?hl:hr); /1加上hl和hr的较大值 /-int main

7、() int k; BiTree root0; /声明创建二叉树对象，调用构造函数 do coutnn; coutnn 1. 建立二叉树; coutnn 2. 交换左右子树 ; coutnn 3. 求二叉树深度 ; coutnn 4. 结束程序运行; coutn=; coutk; switch(k) case 1: coutn s输入（0 0）结束：; root0.creat0(); coutn 中先根遍历结果：; root0.inorder(); break; case 2: coutn 交换左右子树结果：; root0.preordertswap(); coutn 中先根遍历结果：; ro

8、ot0.inorder(); break; case 3: int deep;/=root0.theight(); deep=root0.theight(); coutn 树的深度是：deep; break; case 4: exit(0); / switchcout=0 & kdata; 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写出后序遍历二叉树的非递

9、归算法。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;

10、 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);