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

数 据 结 构 上 机 报 告 电子信息工程 实验五 树图及其应用 一、实验目的 本次实习突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。 二、实验环境 装有Visual C＋＋6.0的计算机。 三、实验内容 二叉树采用二叉列表作存储结构，试编程实现二叉树的如下操作： 按先序序列构造一棵二叉链表表示的二叉树T 对这棵二叉树进行遍历：先序，中序、后序以及层次遍历序列，分别输出节点的遍历序列 求二叉树的深度/结点数目/叶结点数目 将二叉树每个结点的左右子树交换位置 分别使用递归、非递归方法编写 源程序框架 程序代码：递归 #includestdio.h #includestdlib.h #define MAX 20 #define NULL 0 typedef char TElemType; typedef int Status; typedef struct BiTNode{ TElemType 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; CreateBiTree((*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 Queue[MAX],b; int front,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;} } }//LevelOder int depth(BiTree T){ int dep1,dep2; if(T==NULL)return 0; else{dep1=depth(T-lchild); return dep1dep2?dep1+1:dep2+1;} }//depth main(){ BiTree T=NULL; printf(\n\t创建一个二叉树： \n); CreateBiTree(T); printf(\nThe preoder is:\n); PreOrder(T); printf(\nThe level order is:\n); LevelOrder(T); printf(\nThe depth is:%d\n,depth(T)); } 程序代码：非递归 #include stdio.h #include malloc.h #include stack #include queue #include iostream using namespace std; typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTree; void CreateBiTree(BiTree **root) { char ch; ch = getchar(); if(ch == #) { (*root) = NULL; } else { (*root) = (BiTree*)malloc(sizeof(BiTree)); (*root)-data = ch; CreateBiTree((*root)-lchild); CreateBiTree((*root)-rchild); } } //递归先序遍历 void Pre