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

1、数据结构上机报告 电子信息工程实验五 树图及其应用一、实验目的 本次实习突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。二、实验环境 装有Visual C6.0的计算机。三、实验内容二叉树采用二叉列表作存储结构，试编程实现二叉树的如下操作：1、 按先序序列构造一棵二叉链表表示的二叉树T2、 对这棵二叉树进行遍历：先序，中序、后序以及层次遍历序列，分别输出节点的遍历序列3、 求二叉树的深度/结点数目/叶结点数目4、 将二叉树每个结点的左右子树交换位置5、 分别使用递归、非递归方法编写4、 源程序框架程序代码：递归#

2、include#include#define MAX 20#define NULL 0typedef char TElemType;typedef int Status;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTree *T)char ch;ch= getchar();if(ch=#)(*T)=NULL;else(*T)=(BiTree)malloc(sizeof(BiTNode);(*T)-data=ch;CreateBi

3、Tree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);return 1;void PreOrder(BiTree T)if(T) printf(%2c,T-data); PreOrder(T-lchild);PreOrder(T-lchild);void LevelOrder(BiTree T)BiTree QueueMAX,b;int front,rear;front=rear=0;if(T)Queuerear+=T;while(front!=rear)b=Queuefront+;printf(%2c,b-data);if(b-lchild!=NULL)

4、Queuerear+=b-lchild;if(b-rchild!=NULL)Queuerear+=b-rchild;/LevelOderint depth(BiTree T)int dep1,dep2;if(T=NULL)return 0;elsedep1=depth(T-lchild);return dep1dep2?dep1+1:dep2+1;/depthmain()BiTree T=NULL;printf(nt创建一个二叉树： n);CreateBiTree(&T);printf(nThe preoder is:n);PreOrder(T);printf(nThe level order

5、 is:n);LevelOrder(T);printf(nThe depth is:%dn,depth(T);程序代码：非递归#include #include #include #include #include using namespace std;typedef char ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTree;void CreateBiTree(BiTree *root)char ch;ch = getchar();if(ch = #)(*root) = NU

6、LL;else(*root) = (BiTree*)malloc(sizeof(BiTree);(*root)-data = ch;CreateBiTree(&(*root)-lchild);CreateBiTree(&(*root)-rchild);/递归先序遍历void PreOrder(BiTree *root)if(root != NULL)printf(%c ,root-data);PreOrder(root-lchild);PreOrder(root-rchild);/非递归先序遍历void NRPreOrder(BiTree *root)BiTree *p = root;stac

7、k 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);/非递归中序遍历void NRInOrder(BiTree *root)BiTree *p = root;stack s;while(p!=NULL | !s.empty()while(p != NULL)s.push(p);p = p-lchild;if(!s.empty()p = s.top();print

8、f(%c ,p-data);s.pop();p = p-rchild;printf(n);void _PostOrder(BiTree *root)BiTree *p = root, *q = NULL;stack s;cout lchild;if (!s.empty()p = s.top();/无右孩子或右孩子已遍历过if (p-rchild = NULL | p-rchild = q)cout data rchild;cout endl;/层次遍历void LevelOrder(BiTree *root)BiTree *p = root;queue q;if(p != NULL)q.pus

9、h(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);/深度int depth(BiTree *root)int hl,hr,high = 0;if(root = NULL)return 0;elsehl = depth(root-lchild);hr = depth(root-rchild);high = hl hr ? hl : hr;return (hi

10、gh+1);int main()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(二叉树的深度: %dn,depth(root);printf(n);return 0;实验结果截图结果输出：请输入要创建的二叉树:ABC#DE#G#F#递归先序遍历:A B C D E G F非递归先序遍历:A B C D E G F非递归中序遍历:C B E G D F A非递归