算法与数据结构实验报告实验五

算法与数据结构实验报告

实验五

实验名称： 二叉树的应用 姓名： 卢丽娟 学号： 211006289 专业： 软件工程 班级： 二班 指导教师： 陈亦萍 日期: 2012年5月19日

一、 实验目的

该实验是验证二叉树的二叉链表表示，实现CreateBiTree算法创建二叉树。

二、 实验内容与实验步骤

利用CreateBiTree算法创建二叉树，实现二叉树的先序、中序、后序递归遍历算法中的一种，编写主程序调用CreateBiTree创建二叉树，并调用先（中、后）序遍历算法，测试不同的输入数据创建二叉树，预期输出并验证输出的结果。

步骤：

1. 创建二叉树

BiTree CreateBiTree(BiTree &T)//二叉树的创建

{//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树T

char ch;scanf(\前加1空格，留给回车 if(ch=='#') T=NULL; //空格字符表示空树 else

{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-1); T->data=ch;//生成根节点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树}return T;}//CreateBiTree 2. 父亲结点的输出 int visit(char e)

{ printf(\3.中序遍历

void InorderTraverse(BiTree T) { BiTree node=T; if (node!=NULL)

{ InorderTraverse(node->lchild); //若非空，则先遍历左孩子 visit(node->data);InorderTraverse(node->rchild);}} //遍历结点 4.中序遍历非递归 void Inorder(BiTree T)

{ BiTree node=T;char stack[100];

int top = 0;stack[top] =node->data;

while(node!=NULL) //判断结点是否为空 {

while(stack[top]!='#') //不为空先遍历左孩子，再遍历右孩子 { top++; {

if(node->lchild) stack[top] = node->lchild->data; else stack[top] = '#';}top--;

top--; visit(stack[top]); top++;

if(node->rchild) stack[top] = node->rchild->data;

if(stack[top]!='#')

else stack[top] = '#';}}} 5.后序遍历

void PostOrderTraverse(BiTree T)

{ if (T!=NULL) //判断是否为空的情况 { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); 6. 求树的高度 { if(T)

{ BiTreeDepth(T->lchild,d+1); BiTreeDepth(T->rchild,d+1);} else{ if(d>depth) depth = d;}} 7. 查找并输出指定结点的所有儿子节点 void Child(BiTree T) { if(T) {

if(T->data!=cur_e)

{ Child(T->lchild); Child(T->rchild);} else

{ printf(\左孩子为\

visit(T->data);}}

void BiTreeDepth(BiTree T,int d) //求二叉树的深度

if(T->lchild) printf(\else printf(\空\\n\printf(\右孩子为\

if(T->rchild) printf(\else printf(\空\\n\

8. main函数可以用上面的几个函数直接调用，就有输出结果了。

三、 实验环境

操作系统是Windows XP，开发平台：Microsoft Visual C++ 6.0

四、 实验过程与分析

发现在调试运行的时候，出现的错误都是很低级的，比如说调试成功运行后，却运行错误，运行到一半就无法继续下去，查看程序也没错，后来发现是在主函数中少了getchar(),而且scanf括号中也少了“&”，还有就是大小写问题了。

五、 实验结论

测试的数据和输出结果如下： 1.# 树为空 2. a##

后序遍历二叉树: a 深度为1 输入父亲结点: a

左孩子为空 右孩子为空

中序遍历二叉树(非递归) a

3. a#b#c##

后序遍历二叉树: cba

深度为3

输入父亲结点: a

左孩子为空 右孩子为b

中序遍历二叉树(非递归) abc

六、附录

#include #include

const int OK = 1,ERROR = 0; #define ok 1 #define error 0 #define overflow -1 int depth=0;

char cur_e;

typedef struct BiTNode

{ char data; BiTNode* lchild; BiTNode* rchild;}BiTNode,*BiTree; BiTree CreateBiTree(BiTree &T)//二叉树的创建

{//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树T

char ch;scanf(\前加1空格，留给回车

if(ch=='#') T=NULL; else

{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-1); T->data=ch;//生成根节点 CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 }

return T;}//CreateBiTree int visit(char e)

{ printf(\ return 1;} //中序遍历

void InorderTraverse(BiTree T){

BiTree node=T;

if (node!=NULL){InorderTraverse(node->lchild);//若非空，则先遍历左孩子

visit(node->data);InorderTraverse(node->rchild);}}//遍历结点 //中序遍历非递归

void Inorder(BiTree T)

{ BiTree node=T; char stack[100]; int top = 0; while(node!=NULL)//判断结点是否为空

stack[top] =node->data;

{

while(stack[top]!='#')//不为空先遍历左孩子，再遍历右孩子 { top++; if(node->lchild) stack[top] = node->lchild->data; else stack[top] = '#';} top--; if(stack[top]!='#') { top--; visit(stack[top]); top++;

if(node->rchild)

stack[top] = node->rchild->data;

else stack[top] = '#';}}}

//后序遍历

void PostOrderTraverse(BiTree T)

{ if (T!=NULL)//判断是否为空的情况

{ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild);visit(T->data);}} void BiTreeDepth(BiTree T,int d)//求二叉树的深度

{ if(T)

{ BiTreeDepth(T->lchild,d+1); BiTreeDepth(T->rchild,d+1);}

else

{ if(d>depth)

depth = d;}}

void Child(BiTree T) { if(T)

{ if(T->data!=cur_e){ Child(T->lchild);Child(T->rchild);} else{printf(\左孩子为\

if(T->lchild) printf(\else printf(\空\\n\右孩子为\if(T->rchild) printf(\else printf(\空\\n\

int main()

{ BiTree T; CreateBiTree(T); BiTreeDepth(T,0);

if(!depth) printf(\树为空\\n\

else{printf(\后序遍历二叉树:\\n\ printf(\深度为%d\\n\ printf(\输入父亲结点:\\n\

printf(\中序遍历二叉树(非递归)\\n\InorderTraverse(T);printf(\

return 0;}

本文来源：https://www.bwwdw.com/article/1dt5.html