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

1、实验四二叉树的建立和遍历学院专业班学号姓名实习目的掌握二叉链表的存储结构；掌握二叉链表的建立；掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法；掌握二叉树遍历算法的应用；实习内容按先序序列建立二叉树的二叉链表(算法6.4)(空树用#表示)对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。统计二叉树中结点个数；求二叉树的高度；实验步骤定义二叉链表的存储结构#include stdio.h#include stdlib.htypedef chai TElemType;typedef struct BiTNodeTElemType data;stmct BiTNode *lchild,

2、 *ichild; / 左右孩子指针 BiTNode,*BiTree;编写函数CreateBiTree,按先序序列建立二叉树的二叉链表； 测试的字符序列为abdg#e#c#f#;程序代码为：void CreateB订reqEiT代e &T)算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定 义)，构造二叉链表表示的二叉树T。以#表示空树TElemType ch;scanf(”c 役&ch);/ 空T=NULL;elseT=(BiTiee )malloc(sizeof(BiTNode); / 生成根结点if(!T)exit(-l);T-data=ch;CreateB订ree

3、(T-lchild);/递归构造左子树CreateBiTree(T-rcliild);/ 构造右子树2.编写二叉树的先序遍历、中序遍历、后序遍历的递归算法 iiit preOrderTraveise(BiTree T)/初始条件：二叉树T存在，先序递归遍历T：if(T=NULL) return 1;if(T?=NULL) T 不空pimtf(%5c,T-data); 访问根结点preOrderTraveise(T-lchild);/ 先序遍历左子树preOiderTraverse(T-ichild);/ 先序遍历右子树iiit mOrderTraverse(BiTree T)/初始条件：二叉树

4、T存在，中序递归遍历T；if(T=NULL) return 1;if(T?=NULL) /T 不空iiiOrdeiTiaverse(T-lcluld);/ 中序遍历左子树pimtf(%5c,T-data);/ 访问根结点iiiOiderTraverse(T-ichild);/ 中序遍历右子树iiit postOrdeiTraverse(BiTree T)/初始条件：二叉树T存在，/操作结果：后序递归遍历T；if(T=NULL) return 1;if(T?=NULL) T 不空postOrderTraverse(T-lchild);/ 后序遍历左子树 postOrderTraverse(T-r

5、child);/ 后序遍历右子树 pnnrfC%5L,Tdata);/ 访问根结点编写函数统计二叉树中结点个数；(遍历算法)iiit countND(BiTiee T) int n=O,k=O、m=O;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+l ;return n;编写函数求二叉树的高度；iiit Bitheight(BiTiee T) int lhjhth;

6、if(T=NULL)retuni 0;lh= Bitheight(T-lcluld);/递归求T的左子树的高度Uirh= Bitheight(T-rchild);递归求T的右子树的高度ihif(lhrh)th=lli+l;else th=rh+l;return th;4.编写main函数，调用函数，输出结构void niainQiiit i.kji;BiTree T;pnntf(”请按先序输入二叉树(如:ab#表示a为根结点,b为左子树的二叉树)5”)；CreateBiTree(T);pniitf(先序遍历的结呆为：n);i=preOrdeiTiaveise(T); piintf(” n”)；prmtf(中序遍历的结果为：n”)；i=mOiderTraverse(T);pimtfniiH);pnntf(”后序遍历的结果为：n”)；i=postOrderTraverse(T);printf(niiM);k=countND(T);pnntff结点个数为dW、k); h= Bitheight(T);输出树的高度为dg”, h)；4.运行结果(截图)请按先序输人二叉树如二訪廿腳表示功根结点为左子树的二叉树ahdgttttttettttcttFtttt先序遍历的结果为：a b d g e c F中序遍历的结果为：gdbeac后序遍历的结果为：g