二叉树及其先序遍历
-------------------------------实验 二叉树及其先
序遍历
一、 实验目的：
1．明确了解二叉树的链表存储结构。
2．熟练掌握二叉树的先序遍历算法。
一、 实验内容：
1．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算
机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。
2．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有
一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。
3．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉
树的子树有左右之分，其次序不能颠倒。
4．二叉树的结点存储结果示意图如下：
二叉树的存储（以五个结点为例）：
三、实验步骤
1．理解实验原理，读懂实验参考程序。
2．
（1）在纸上画出一棵二叉树。
E
D (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. 考虑用非递归算法完成二叉树遍历。