二叉树的遍历(先序遍历中序遍历后序遍历全)实验报告.doc
文本预览下载声明
实验目的
编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。
实验内容
编程序并上机调试运行。
编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。
编写程序
/***********二叉树的遍历**************/
#includestdio.h
#includestdlib.h
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.
按先序次序构建二叉树链表T。
函数CreatBiTree为构建二叉树链表的函数，T为指针，定义ch为字符型，如果输入为空格的话，指针就为空。否则，就新开辟一个单元，如果开辟失败，则强制错误退出，如果开辟成功，就让ch指向新单元的数据，然后再指向左孩子，再指向右孩子。
遇到的问题：一开始写的是以下程序：
没有指针形式，调试的时候没有错误，也可以执行，但是执行的时候就发生以下错误：
所以在T的前面加一个指针符号，因为要用指针指向新的结点，所以将后面的T都加上一个*，结果还是错误：
最后实在不知道错在哪，就上网百度了一下，发现是在指向左孩子和右孩子的时候要加一个地址符，因为函数CreatBi
显示全部