《数据结构与算法(C语言版)》上机实验4.pdfVIP

上机实验4二叉树的遍历

【实验目的】

（1）掌握指针变量的含义及使用方法。

（2）熟悉二叉树结点的结构。

（3）掌握二叉树每一种操作具体实现的方法。

（4）学会利用递归的方法实现二叉树的遍历算法。

【实验内容】

实现对二叉树的如下操作：

（1）创建二叉树。

（2）先序遍历二叉树。

（3）中序遍历二叉树。

（4）后序遍历二叉树。

（5）按层遍历二叉树。

要求能够从键盘上输入建树的结点内容，并且将遍历的结果输出在屏幕上。

【实验步骤】

（1）在MicrosoftVisualC++中创建应用程序L4。

（2）在程序中创建二叉树的存储结构BiTNode，以链表作为存储结构。

（3）创建CreateBiTree()函数，实现创建二叉树的操作，能够按先序次序从键盘输入结

点内容，空格表示空树。

（4）创建PreOrderTraverse()函数，用递归的方法实现先序遍历二叉树的操作。

（5）创建InOrderTraverse()函数，用递归的方法实现中序遍历二叉树的操作。

（6）创建PostOrderTraverse()函数，用递归的方法实现后序遍历二叉树的操作。

（7）创建LevelOrderTraverse()函数，实现按层遍历二叉树的操作。

（8）创建主函数，用switch语句实现从键盘上输入字符，选择要执行的操作。

（9）编译连接程序，执行并观察程序的运行效果。

【参考源代码】

typedefstructBiTNode

{

chardata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

voidCreateBiTree(BiTreeT)

{//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树

charch;

if(ch==)T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(-1);

T-data=ch;

CreateBiTree(T-lchild);

CreateBiTree(T-rchild);

}

}//CreateBiTree

voidPreOrderTraverse(BiTreeT)

{//先序遍历

if(T){

PreOrderTraverse(T-lchild);

PreOrderTraverse(T-rchild);

}

}//PreOrderTraverse

voidInOrderTraverse(BiTreeT)

{//中序遍历

if(T){

InOrderTraverse(T-lchild);

InOrderTraverse(T-rchild);

}

}//InOrderTraverse

voidPostOrderTraverse(BiTreeT)

{//后序遍历

if(T){

PostOrderTraverse(T-lchild);

PostOrderTraverse(T-rchild);

}

}//PostOrderTraverse

voidLevelOrderTraverse(BiTreeT)

{//按层遍历

constintMaxLength=100;

BiTreeQ[MaxLength];

Q[0]=T;

intfront=0,rear=1;

while(frontrear)

{

if(Q[front])

{

Q[rear++]=Q[f