二叉树的构造与遍历方法_二叉树的构造及遍历
二叉树的构造与遍历方法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树的构造及遍历”。
题目
二叉树的构造与遍历方法
一、实验目的通过实验能熟练掌握二叉树的定义、性质和存储结构;二叉树的遍历和线索以及遍历算法的各种描述形式。
二、实验内容
用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。
三、实验步骤
1）定义二叉树和用先序次序构造二叉树。
typedef struct BiTNode { //注意采用的是二叉链表作为二叉树的存储结构
TElemType data;struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;Status CreateBiTree_PreOrder(BiTree &T){ //先序次序构造二叉树
} 2）根据先序遍历、中序遍历和后序遍历的方法编序相应的函数，如： Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //先序遍历
TElemType ch;scanf(“%c”,&ch);if(ch==' ')T=NULL;else {
} return OK;if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree_PreOrder(T->lchild);CreateBiTree_PreOrder(T->rchild);if(T){
}
if((*Visit)(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;} return OK;Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //中序遍历
} Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //后序遍历
} if(T!=NULL){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if((*Visit)(T->data))return OK;if(T!=NULL){
if(InOrderTraverse(T->lchild,Visit))
if((*Visit)(T->data))
if(InOrderTraverse(T->rchild,Visit))return OK;return ERROR;} else return OK;return ERROR;} else return OK;
3、编写各遍历后的输出函数。
Status Disp(TElemType e){ //输出各结点的数据值
} printf(“%3c”,e);return OK;
4、编写主程序调用以上子程序调试实现实验要求的各种遍历。
void main(){
BiTree T;printf(“输入要构造的二叉树：n”);
CreateBiTree(T);printf(“n”);printf(“用先序遍历的方式遍历此二叉树为:n”);PreOrderTraverse(T, printnode);printf(“n”);printf(“用中序遍历的方式遍历此二叉树为:n”);InOrderTraverse(T, printnode);
printf(“n”);printf(“用后序遍历的方式遍历此二叉树为:n”);PostOrderTraverse(T, printnode);printf(“n”);}
四、实验程序
//利用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。#include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define NULL 0 typedef char TElemType;typedef int Status;typedef struct BiTNode {
TElemType data;
struct BiTNode
*lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;int n=0;Status CreateBiTree(BiTree &T)//用先序次序构造二叉树 {
char ch;scanf(“%c”,&ch);
if(ch==' ')T=NULL;else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;} Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//用先序遍历 {
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}else
return OK;}
Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//中序遍历 { if(T){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}else
return OK;} Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//后序遍历 { if(T){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return OK;
return ERROR;
}else
return OK;} Status printnode(TElemType e){ printf(“ %c”,e);return OK;} void main()
{
BiTree T;printf(“输入要构造的二叉树：n”);
CreateBiTree(T);
} printf(“n”);printf(“用先序遍历的方式遍历此二叉树为:n”);PreOrderTraverse(T, printnode);printf(“n”);printf(“用中序遍历的方式遍历此二叉树为:n”);InOrderTraverse(T, printnode);printf(“n”);printf(“用后序遍历的方式遍历此二叉树为:n”);PostOrderTraverse(T, printnode);printf(“n”);
五、实验的结果：
a b c d f e g
