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