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

上机实验4二叉树的遍历

【实验目的】

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

(2)熟悉二叉树结点的结构。

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

(4)学会利用递归的方法实现二叉树的遍历算法.

【实验内容】

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

(I)创建二叉树。

(2)先序遍历二叉树。

(3)中序遍历二叉树。

(4)后序遍历二叉树。

(5)按层遍历二叉树。

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

【实验步骤】

(1)在MicrosoftVisualC++中创建应用程序L4。

(2)在程序中创建二叉树的存储结构BiTNode,以链表作为存储结构。

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

点内容，空格表示空树。

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

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

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

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

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

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

【参考源代码】

#include"stdlib.h"

#include"stdio.h"

typedefstructBiTNode

(

chardata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

voidCreateBiTree(BiTree&T)

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

charch;

scanf("％c”,&ch);

if(ch==~)T=NULL;

else{

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

T->data=ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

)//CreateBiTree

voidPreOrderTraverse(BiTreeT)

{〃先序遍历

if(T){

primf("％cn,T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

)

}//PreOrderTraverse

voidInOrderTraverse(BiTreeT)

{〃中序遍历

if(T){

InOrderTraverse(T->lchild);

printf("％c",T->data);

InOrderTraverse(T->rchild);

)

}//InOrderTraverse

voidPostOrderTraverse(BiTreeT)

{〃后序遍历

if(T){

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

printf(n%cn,T->data);

)

}//PostOrderTraverse

voidLevelOrderTraverse(BiTreeT)

(〃按层遍历

constintMaxLength=100;

BiTreeQ[MaxLength];

Q[0]=T;

intfront=0,rear=1;

while(front<rear)

(

if(Q|front])

(

printf(u%cM,Q[front]->data);

Q[rear++]=Q[front]->lchild;

Q[rear++]=Q[front]->rchild;

front++;

}

else

(

front++;

}

)

}//LevelOrderTraverse

voidmain()

(

BiTreeT=NULL;

charselect;

while(l)

{

printf("请选择要执行的操作：\n");

printf("l.创建二叉树\n");

printf("2.二叉树的递归遍历算法(前、中、后)\n");

printf("3.二叉树的层序遍历算法\n");

printf("0.退出\n")；

fflush(stdin);

scanf("%c",&select);

fflush(stdin);

switch(select)

(

case'O':retum;

caseT:

printf("请按先序次序输入各结点的值，以空格表示空树(输入时可连

续输入):\n");

CreateBiTree(T);

printf(,,\nn);

break;

case2:

printf("先序遍历:")；

PreOrderTraverse(T);

printf("\n中序遍历:")；

InOrderTraverse(T);

printf(”\n后序遍历:");

PostOrderTraverse(T);

printf(n\n\nn);

break;

case3:

printf("层序遍历:")；

LevelOrderTraverse(T);

printf(n\n\nH);

break;

default:

printf("请确认选择项!\n\n");

}//endswitch

}//endwhile

}//endmain

【实验结果】

运行示例：构建如下二叉树，并且将其遍历的结果输出在屏幕上。

步骤1：输入1,按Entera,等待创建二叉树。

步骤2：按先序方式构建二叉树，输入：abd(空两格)e(空两格)c(空两格)，按Enter键确认

输入。

步骤3：输入2,按Enter®,观察显示结果。

步骤4：输入3,按Enter@,观察显示结果。

步骤5：输入0,退出循环程序。

运行结果如附图4所示。

C:\WINDOVS\syste・32\c・d.

的

操作

请

选笛

执一

要

叉

创

叉

二

的

二

层

遍

1.历1

叉

招中、后)

I2.的

二

遍

历

B.出

B.1退

以空格表示空树(输入时可连续输入＞:

精选会要执代的操作:

仪.创建二叉树

口三叉树的递归遍璧(前、中、后)

b)一.二叉.树的层序遍历:

「退出

2

映•序遍历:aba

|中序遍历:db

后存遍历:debea

愣聚鹦的操作

E.二叉树的「…递八归遍'历-(前、中、后)

「二叉翱

’的层序遍历

退出

p*.

层序遍历:abcde

情姆至要执行的操作:

k创灌二攵希

除二叉树的蓬归遍历萋(前、申、后)

"二叉树的层序遍历事

口.退出I

tT

附图4上机实验4运行结果

【实验总结】

在创建二叉树时应注意程序的编写，在参考程序中，使用空格来表示空树，所以在创建

时，如果结点的子树为空时，一定要输入空格，方能成功创建二叉树。当然，也可用其他的

字符(如“#")