实验二叉树及其先序遍历
一、实验目的：
1．明确了解二叉树的链表存储结构。

2．熟练掌握二叉树的先序遍历算法。

一、实验内容：
1．树型结构是一种非常重要的非线性结构。

树在客观世界是广泛存在的，在计算
机领域里也得到了广泛的应用。

在编译程序里，也可用树来表示源程序的
语法结构，在数据库系统中，数形结构也是信息的重要组织形式。

2．节点的有限集合（N大于等于0）。

在一棵非空数里：（1）、有且仅
有
一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）
个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。

树
的定义是以递归形式给出的。

3．二叉树是另一种树形结构。

它的特点是每个结点最多有两棵子树，并且，二叉
树的子树有左右之分，其次序不能颠倒。

4．二叉树的结点存储结果示意图如下：
二叉树的存储（以五个结点为例）：
三、实验步骤
1．理解实验原理，读懂实验参考程序。

2．
（1）在纸上画出一棵二叉树。

A
B E
C D G F
(2) 输入各个结点的数据。

(3) 验证结果的正确性。

四、程序流程图
先序遍历
五、参考程序
# define bitreptr struct type1 /*二叉树及其先序边历*/ # define null 0
# define len sizeof(bitreptr)
bitreptr *bt;
int f,g;
bitreptr /*二叉树结点类型说明*/
{
char data;
bitreptr *lchild,*rchild;
};
preorder(bitreptr *bt) /*先序遍历二叉树*/
{
if(g==1) printf("先序遍历序列为：\n");
g=g+1;
if(bt)
{
printf("%6c",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
else if(g==2) printf("空树\n");
}
bitreptr *crt_bt() /*建立二叉树*/ {
bitreptr *bt;
char ch;
if(f==1) printf("输入根结点，#表示结束\n"); else printf("输入结点，#表示结束\n");
scanf("\n%c",&ch);
f=f+1;
if(ch=='#') bt=null;
else
{
bt=(bitreptr *)malloc(len);
bt->data=ch;
printf("%c 左孩子",bt->data);
bt->lchild=crt_bt();
printf("%c 右孩子",bt->data);
bt->rchild=crt_bt();
}
return(bt);
}
main()
{
f=1;
g=1;
bt=crt_bt();
preorder(bt);
}
六、思考问题
1. 画出给出的各类型的数据示意图，理解为不同目的而建立的不同数据结构意义。

2. 改写程序完成中、后序遍历。

3. 考虑用非递归算法完成二叉树遍历。