二叉树的建立和遍历实验报告.doc

实验四 二叉树的建立和遍历 学院 专业 班 学号 姓名 一 实习目的1. 掌握二叉链表的存储结构；2. 掌握二叉链表的建立；3. 掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法；4. 掌握二叉树遍历算法的应用；二 实习内容1. 按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示）2. 对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。3 统计二叉树中结点个数； 4. 求二叉树的高度；三 实验步骤1. 定义 二叉链表的存储结构#include stdio.h#include stdlib.h typedef char TElemType;typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode,*BiTree;2. 编写函数CreateBiTree，按先序序列建立二叉树的二叉链表;测试的字符序列为abdg#e#c#f#; 程序代码为：void CreateBiTree(BiTree &T) / 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， 构造二叉链表表示的二叉树T。以#表示空树 TElemType ch; scanf(%c,&ch); if(ch=#) / 空 T=NULL; else T=(BiTree )malloc(sizeof(BiTNode); / 生成根结点 if(!T) exit(-1); T-data=ch; CreateBiTree(T-lchild);/ 递归构造左子树 CreateBiTree(T-rchild);/ 构造右子树 2. 编写二叉树的先序遍历、中序遍历、后序遍历的递归算法 int preOrderTraverse(BiTree T) / 初始条件：二叉树T存在，先序递归遍历T； if(T=NULL) return 1; if(T!=NULL) / T不空 printf(%5c,T-data); / 访问根结点 preOrderTraverse(T-lchild);/ 先序遍历左子树 preOrderTraverse(T-rchild);/ 先序遍历右子树 int inOrderTraverse(BiTree T) / 初始条件：二叉树T存在，中序递归遍历T； if(T=NULL) return 1; if(T!=NULL) / T不空 inOrderTraverse(T-lchild);/ 中序遍历左子树 printf(%5c,T-data); / 访问根结点 inOrderTraverse(T-rchild);/ 中序遍历右子树 int postOrderTraverse(BiTree T) / 初始条件：二叉树T存在， / 操作结果：后序递归遍历T； if(T=NULL) return 1; if(T!=NULL) / T不空 postOrderTraverse(T-lchild);/ 后序遍历左子树 postOrderTraverse(T-rchild);/ 后序遍历右子树 printf(%5c,T-data); / 访问根结点 3. 编写函数统计二叉树中结点个数； （遍历算法）int countND(BiTree T) int n=0,k=0,m=0;if(T=NULL) return 0;else if(T-lchild!=NULL ) k=countND(T-lchild); / 后序遍历左子树,得到左子树结点个数if(T-rchild!=NULL ) m=countND(T-rchild); / 再后序遍历右子树 n=m+k+1 ; return n;4. 编写函数求二叉树的高度；int Bitheight(BiTree T) int lh,rh,th;if(T=NULL)return 0; lh= Bitheight(T-lchild); / 递归求T的左子树的高度lhrh= Bitheight(T-rchild); /递归求T的右子树的高度rh if(lhrh) th=lh+1; else th=rh+1; return th;4. 编写 main 函数，调用函数，输出结构 void main() int i,k,h ; BiTree T; printf(请按先序输入二叉树(如:ab#表示a为根结点,b为左子树的二叉树)n); CreateBiTree(T); printf(先序遍历的结果为：n); i=preOrderTraverse(T); printf(n); printf(中序遍历的结果为：n); i=inOrderTraverse(T);printf(n); printf(后序遍历的结果为：n); i=postOrderTraverse(T);printf(n); k=countND(T); printf(结点个数为%dn,k); h= Bitheight(T