二叉树遍历的递归与非递归算法编程

数据结构上机报告电子信息工程实验五树图及其应用一、实验目的本次实习突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。二、实验环境装有VisualC＋＋6.0的计算机。三、实验内容二叉树采用二叉列表作存储结构，试编程实现二叉树的如下操作：1、按先序序列构造一棵二叉链表表示的二叉树T2、对这棵二叉树进行遍历：先序，中序、后序以及层次遍历序列，分别输出节点的遍历序列3、求二叉树的深度/结点数目/叶结点数目4、将二叉树每个结点的左右子树交换位置5、分别使用递归、非递归方法编写四、源程序框架程序代码：递归#includestdio.h#includestdlib.h#defineMAX20#defineNULL0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree*T){charch;ch=getchar();if(ch=='#')(*T)=NULL;else{(*T)=(BiTree)malloc(sizeof(BiTNode));(*T)-data=ch;CreateBiTree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);}return1;}voidPreOrder(BiTreeT){if(T){printf(%2c,T-data);PreOrder(T-lchild);PreOrder(T-lchild);}}voidLevelOrder(BiTreeT){BiTreeQueue[MAX],b;intfront,rear;front=rear=0;if(T){Queue[rear++]=T;while(front!=rear){b=Queue[front++];printf(%2c,b-data);if(b-lchild!=NULL)Queue[rear++]=b-lchild;if(b-rchild!=NULL)Queue[rear++]=b-rchild;}}}//LevelOderintdepth(BiTreeT){intdep1,dep2;if(T==NULL)return0;else{dep1=depth(T-lchild);returndep1dep2?dep1+1:dep2+1;}}//depthmain(){BiTreeT=NULL;printf(\n\t创建一个二叉树：\n);CreateBiTree(&T);printf(\nThepreoderis:\n);PreOrder(T);printf(\nThelevelorderis:\n);LevelOrder(T);printf(\nThedepthis:%d\n,depth(T));}程序代码：非递归#includestdio.h#includemalloc.h#includestack#includequeue#includeiostreamusingnamespacestd;typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTree;voidCreateBiTree(BiTree**root){charch;ch=getchar();if(ch=='#'){(*root)=NULL;}else{(*root)=(BiTree*)malloc(sizeof(BiTree));(*root)-data=ch;CreateBiTree(&(*root)-lchild);CreateBiTree(&(*root)-rchild);}}//递归先序遍历voidPreOrder(BiTree*root){if(root!=NULL){printf(%c,root-data);PreOrder(root-lchild);PreOrder(root-rchild);}}//非递归先序遍历voidNRPreOrder(BiTree*root){BiTree*p=root;stackBiTree*s;while(p!=NULL||!s.empty()){while(p!=NULL){printf(%c,p-data);s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();s.pop();p=p-rchild;}}printf(\n);}//非递归中序遍历voidNRInOrder(BiTree*root){BiTree*p=root;stackBiTree*s;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();printf(%c,p-data);s.pop();p=p-rchild;}}printf(\n);}void_PostOrder(BiTree*root){BiTree*p=root,*q=NULL;stackBiTree*s;cout非递归后序遍历：;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();//无右孩子或右孩子已遍历过if(p-rchild==NULL||p-rchild==q){coutp-data;//保存到q，为下一次已处理结点前驱q=p;p=NULL;s.pop();}else{p=p-rchild;}}}coutendl;}//层次遍历voidLevelOrder(BiTree*root){BiTree*p=root;queueBiTree*q;if(p!=NULL){q.push(p);while(!q.empty()){p=q.front();printf(%c,p-data);q.pop();if(p-lchild!=NULL){q.push(p-lchild);}if(p-rchild!=NULL){q.push(p-rchild);}}}printf(\n);}//深度intdepth(BiTree*root){inthl,hr,high=0;if(root==NULL){return0;}else{hl=depth(root-lchild);hr=depth(root-rchild);high=hlhr?hl:hr;return(high+1);}}intmain(){BiTree*root=NULL;printf(\t请输入要创建的二叉树:\n);CreateBiTree(&root);printf(递归先序遍历:);PreOrder(root);printf(\n);printf(非递归先序遍历:);NRPreOrder(root);printf(非递归中序遍历:);NRInOrder(root);_PostOrder(root);printf(层次遍历:);LevelOrder(root);printf(二叉树的深度:%d\n,depth(root));printf(\n);return0;}实验结果截图结果输出：请输入要创建的二叉树:ABC##DE#G##F###递归先序遍历:ABCDEGF非递归先序遍历:ABCDEGF非递归中序遍历:CBEGDFA非递归后序遍历：CGEFDBA层次遍历:ABCDEFG二叉树的深度:5--------------------------------Processexitedwithreturnvalue0Pressanykeytocontinue...五、心得体会由于c及c++基础差，学数据结构也成了我的薄弱的地方，不说太多，只希望自己再好好努力吧！