二叉树的遍历(先序遍历、中序遍历、后序遍历全)实验报告
- 格式:doc
- 大小:130.55 KB
- 文档页数:8
实验目的
编写一个程序,实现二叉树的先序遍历,中序遍历,后序遍历。
实验内容
编程序并上机调试运行。
编写一个程序,实现二叉树的先序遍历,中序遍历,后序遍历。编写程序
/***********二叉树的遍历**************/
#include
#include
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*************************************************/
//按先序次序构建的二叉树链表
void CreatBiTree(BiTree *T)
{
char ch;
if((ch=getchar())==' ')
*T=NULL;
else
{
*T=(BiTNode*)malloc(sizeof(BiTNode));
if(!(*T))
exit(1);
(*T)->data=ch;
CreatBiTree(&(*T)->lchild);
CreatBiTree(&(*T)->rchild);
}
}
/*************************************************/ //先序遍历--递归算法
void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
/*************************************************/ //中序遍历--递归算法
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
/*************************************************/ //后序遍历--递归算法
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
/*************************************************/ //main函数
void main()
{
BiTree T;
printf("请按先序次序输入二叉树中结点的值,空格字符表示空树:\n" );
CreatBiTree(&T);
printf("\n");
printf("先序遍历为:\n");
PreOrderTraverse(T);
printf("\n\n");
printf("中序遍历为:\n");
InOrderTraverse(T);
printf("\n\n");
printf("后序遍历为:\n");
PostOrderTraverse(T);
printf("\n\n");
getchar();
}
运行程序:
结果分析:
按先序输入的二叉树为ABC^^DE^G^^F^^^(^为空格)
该二叉树画成树形为:
其先序遍历为:ABCDEGF
其中序遍历为:CBEGDFA
其后序遍历为:CGEFDBA
可以看出运行结果是正确的。
程序解析:
1.首先是将程序的开头写好,因为后面要用到malloc,所以要有stdlib.h的声明。然后建立指针表struct BiTNode,定义其数据类型为char型,指针指向lchild,rchild,下一个指针为BiTNode.
2.按先序次序构建二叉树链表T。
函数CreatBiTree为构建二叉树链表的函数,T为指针,定义ch为字符型,如果输入为空格的话,指针就为空。否则,就新开辟一个单元,如果开辟失败,则强制错误退出,如果开辟成功,就让ch指向新单元的数据,然后再指向左孩子,再指向右孩子。
遇到的问题:一开始写的是以下程序:
没有指针形式,调试的时候没有错误,也可以执行,但是执行的时候就发生以下错误:
所以在T的前面加一个指针符号,因为要用指针指向新的结点,所以将后面的T都加上一个*,结果还是错误:
最后实在不知道错在哪,就上网百度了一下,发现是在指向左孩子和右孩子的时候要加一个地址符,因为函数CreatBiTree是指针函数。
这样结果就对了。
3.建立先序遍历函数。
用递归算法建立先序遍历的函数PreOrderTraverse,如果T不为0,则先输出其根,再输出左孩子,在输出右孩子。这种方法为递归算法,以下的中序,后序均与此类似。
4.建立中序遍历函数。
用递归算法建立中序遍历函数InOrderTraverse,其函数的写法与先序的类似,先输出其左孩子,再输出根节点,再输出其右孩子。书上的中序遍历用的是非递归算法,非递归算法用的是栈,所以还要建栈,入栈,出栈等函数,相较于递归算法麻烦很多。
5.建立后序遍历函数。
用递归算法建立后序遍历函数PostOrderTraverse,先输出其左孩子,再输出其右孩子,再输出其根节点。以%C的格式输出。
6.建立main函数。