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

《二叉树遍历的递归与非递归算法编程.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、归#include#include#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)

3、);(*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=Qu

4、eue[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);returndep1>dep2?dep1+1:dep2+1;}}//depthmain(){BiTreeT=NULL;printf("t创建一个二叉

5、树：");CreateBiTree(&T);printf("Thepreoderis:");PreOrder(T);printf("Thelevelorderis:");LevelOrder(T);printf("Thedepthis:%d",depth(T));}程序代码：非递归#include#include#include#include#includeusingnamespacestd;typedefcharElemType;typedefstruct

6、BiTNode{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*

7、root){if(root!=NULL){printf("%c",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}//非递归先序遍历voidNRPreOrder(BiTree*root){BiTree*p=root;stacks;while(p!=NULL

8、

9、!s.empty()){while(p!=NULL){printf("%c",p->data);s.push(p);p=p->lchild;}if(!s.empty()){p=s.t