数据结构实验二叉树.docx

1、数据结构实验二叉树嵌入式系统开发实验报告课程名称 数据结构 成 绩 实验项目 二叉树 指导教师 学生姓名 学号 班级专业 实验地点 实验日期 年 月 日一、实习目的1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。2.用树解决实际问题，如哈夫曼编码等。3.加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。二、运行环境Windows Microsoft Visual C+ 运行界面三、实例 1. 二叉树的建立和遍历。为了实现对二叉树的有关操作，首先要在计算机中建立所需的

2、二叉树。建立二叉树有各种不同的方法。有一种方法利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：序号 数据元素。结合下图的二叉树数的输入据顺序应该是：1 1，2 2，3 3，4 4，6 5，7 6，11 7，12 8，13 9。另一种算法是教材P58P59介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织时先序的顺序，但是另有特点，当某结点的某孩子为空时以数据0来充当，也要输入。结合下图的二叉树数的输入据顺序应该是：1 2 4 0 0 0 3 5 0 7 0 0 6 8 0 0 9 0 0。若当前数据不为0，则申请一个结点存入当前数据。递归调

3、用建立函数，建立当前结点的左右子树。 下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。/* 二叉树的建立与遍历 */# include # include typedef int Etype; typedef struct BiTNode /* 树结点结构体 */ Etype data; struct BiTNode *lch,*rch; BiTNode;/* 函数原形声明 */BiTNode *creat_bt1();BiTNode *creat_bt2();void inorder(BiTNode *p);void numb(BiTNode *p);Bi

4、TNode *t; int n,n0,n1,n2;/* 主函数 */void main() char ch; int k; do printf(nnn); printf(nn 1. 建立二叉树方法1 ); printf(nn 2. 建立二叉树方法2); printf(nn 3. 中序递归遍历二叉树); printf(nn 4. 计算树中结点个数); printf(nn 5. 结束程序运行); printf(n=); printf(n 请输入您的选择 (1,2,3,4,5,6); scanf(%d,&k); switch(k) case 1: t=creat_bt1( ); break; /*

5、调用性质5建立二叉树算法 */ case 2: t=creat_bt2( ); break; /* 调用递归建立二叉树算法 */ case 3: inorder(t); /* 调用中序遍历 */ printf(nn 打回车键，继续。); ch=getchar(); break; case 4: n=0;n0=0 ; n1=0; n2=0; /* 全局变量置0 */ numb(t); printf(n 二叉树结点总数 n=%d,n); printf(n 二叉树叶子结点数 n0=%d,n0); printf(n 度为1的结点数 n1=%d,n1); printf(n 度为2的结点数 n2=%d,n

6、2); printf(nn 打回车键，继续。); ch=getchar(); break; case 5: exit(0); /* switch */ printf(n -); while(k=1 & kdata=e; p-lch=NULL; p-rch=NULL; vi=p; if (i=1) t=p; /* 序号为1的结点是根 */ else j=i/2; if(i%2=0) vj-lch=p; /* 序号为偶数，做左孩子*/ else vj-rch=p; /* 序号为奇数，做右孩子*/ printf(n i,data= ); scanf(%d,%d,&i,&e); return(t);

7、/* creat_bt1 */ /* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2( ) BiTNode *t;int e; printf(n data=); scanf(%d,&e); if(e=0) t=NULL; /* 对于0值，不分配新结点 */ else t=(BiTNode *)malloc(sizeof(BiTNode); t-data=e; t-lch=creat_bt2(); /* 左孩子获得新指针值 */ t-rch=creat_bt2(); /* 右孩子获得新指针值 */ return(t); /* creat_bt2 */* 中序递归遍历

8、二叉树 */void inorder(BiTNode *p) if (p) inorder(p-lch); printf(%3d,p-data); inorder(p-rch); /* inorder */* 利用中序递归遍历二叉树的方法，计算树中结点个数 */* 读者可以试着运用先序或后序递归遍历二叉树方法重新编写这一段函数 */ void numb(BiTNode *p) if (p) numb(p-lch); printf(%3d,p-data); n+; if(p-lch=NULL & p-rch=NULL) n0+; if(p-lch=NULL & p-rch!=NULL)|(p-l

9、ch!=NULL & p-rch=NULL) n1+; if(p-lch!=NULL & p-rch!=NULL) n2+; /* 把访问的功能扩大了 */ numb(p-rch); /* inorder */程序运行界面如下： 四、实习题1.建立一棵二叉树，要求用先序非递归方法遍历二叉树。程序设计如下：#include #include#include #define maxsize 10 #define stackmaxsize 100/*二叉链表的结构体建立*/ typedef struct node char data; struct node *lchild,*rchild; bit

10、ree;/*顺序堆栈结构体的建立*/ typedef struct bitree stackstackmaxsize; int top; Seqstack;/*初始化顺序堆栈*/ void initstack(Seqstack *s) s-top=0; /* 进栈函数 */int push(Seqstack *s,bitree *ch) if(s-top=stackmaxsize-1) printf(n Stack is Overflow ! n); else s-top+; s-stacks-top=*ch; return 1; /* push */ /*出栈操作*/ bitree *pop

11、(Seqstack *s) bitree p1,*p=&p1; *p=s-stacks-top; s-top-; return p; /*判断栈是否为空*/ int empty(Seqstack *s) if(s-top=-1) return 1; else return 0; bitree *qmaxsize; /*创建二叉树*/ bitree *creatree() char ch; int front,rear; bitree *t,*s; t=NULL; front=1; rear=0; ch=getchar(); while(ch!=#) s=NULL; if(ch!=) s=(bi

12、tree*)malloc(sizeof(bitree); s-data=ch; s-lchild=s-rchild=NULL; rear+; qrear=s; if(rear=1) t=s; else if(s!=NULL&qfront!=NULL) if(rear%2=0) qfront-lchild=s; else qfront-rchild=s; if(rear%2=1) front+; ch=getchar(); return t; /*先序非递归遍历*/ void preorder(bitree *t) bitree *p=t;Seqstack s1,*s=&s1; initstac

13、k(s); while(p!=NULL)|(!empty(s) if(p!=NULL) printf(%2c,p-data);push(s,p); p=p-lchild; else p=pop(s); p=p-rchild; /*主函数*/ void main() bitree *tr; printf(创建二叉树：n 请输入节点信息：); tr=creatree(); printf(非递归先序遍历二叉树的结果为：n); preorder(tr); printf(n); 程序运行界面输出如下：2.建立一棵二叉树，要求用“按层遍历”的方法遍历二叉树”的函数。程序设计如下：#include #inc

14、lude #define max 100 typedef char ElemType; /*二叉链表的结构体创建*/typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BinTree;/*函数声明*/void CreateBinTree(BinTree &T); /*建立二叉树*/void LevleOrder(BinTree T); /*层次遍历二叉树*/void Print_BinTree(BinTree T,int i ); /*按要求输出二叉树*/*主函数*/int main()B

15、inTree T;int i=0; printf(n按先序遍历法，创建二叉树：n); CreateBinTree (T); printf(n层次遍历二叉树 并输出遍历结果：n); LevleOrder(T); printf(n按树形打印输出二叉树：n); Print_BinTree(T, i); return 0;/*建立二叉树*/void CreateBinTree(BinTree &T) char ch; ch=getchar(); if(ch=#) T=NULL;else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) printf(%c 结点建立失败!

16、) ;T-data=ch; CreateBinTree(T-lchild); CreateBinTree(T-rchild); /*层次遍历二叉树*/void LevleOrder(BinTree T) BinTree Queuemax,p; int front,rear; front=rear=0; if (T) Queuerear+=T; while (front!=rear) p=Queuefront+; printf(%c,p-data); if (p-lchild!=NULL) Queuerear+=p-lchild; if (p-rchild!=NULL) Queuerear+=p

17、-rchild; /*按要求输出二叉树*/void Print_BinTree(BinTree T,int i ) / i表示结点所在层次,初次调用时i=0 if(T-rchild) Print_BinTree(T-rchild,i+1); /函数递归来建立层次。 for(int j=1;jdata); /打印T元素,换行 if(T-lchild) Print_BinTree(T-lchild,i+1);程序运行界面输出如下：3.给定一组值，建立一棵二叉树，求二叉数的树深。程序设计如下：#include #include #include #define NULL 0 /*二叉树链表的结构体定

18、义*/typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; /*函数声明*/BiTree Create(BiTree T); /*二叉树的建立*/void Preorder(BiTree T); /*前序遍历函数*/int Sumleaf(BiTree T); /*二叉树的叶子结点个数的计算*/void zhongxu(BiTree T); /*中序遍历函数*/void houxu(BiTree T); /*后序遍历函数*/int Depth(BiTree T); /*求二叉树的树深

19、*/*主函数*/void main() BiTree T; int sum,dep; printf( 按先序递归遍历方法，如下建立二叉树n ); T=Create(T); printf( 1.先序递归遍历二叉树：n ); Preorder(T); printf(n); printf( 2.中序递归遍历二叉树：n ); zhongxu(T); printf(n); printf( 3.后序递归遍历二叉树：n ); houxu(T); printf(n); printf( 4.求二叉树的叶子结点的个数：n ); sum=Sumleaf(T); printf(%dn,sum); printf( 5.

20、求二叉树的树的深度：n ); dep=Depth(T); printf(%d,dep); printf(n); /*二叉树的建立*/BiTree Create(BiTree T) char ch; ch=getchar(); if(ch=) T=NULL; /* 对于值，不分配新结点 */else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) printf(Error!); T-data=ch; T-lchild=Create(T-lchild); /* 左孩子获得新指针值 */ T-rchild=Create(T-rchild); /* 右孩子获得新指针值

21、 */ return T; /*前序遍历函数*/void Preorder(BiTree T) if(T) printf(%c,T-data); /*遍历根结点*/Preorder(T-lchild); /*遍历左子树结点*/ Preorder(T-rchild); /*遍历右子树结点*/ /*二叉树的叶子结点个数的计算*/int Sumleaf(BiTree T) int sum=0,m,n; if(T) if(!T-lchild)&(!T-rchild) sum+; /*叶子结点数目加1*/m=Sumleaf(T-lchild); /*计算叶子结点数目*/sum+=m; n=Sumleaf

22、(T-rchild); /*计算叶子结点数目*/sum+=n; return sum; /*中序遍历函数*/void zhongxu(BiTree T) if(T) zhongxu(T-lchild); /*遍历左子树结点*/ printf(%c,T-data); /*遍历根结点*/zhongxu(T-rchild); /*遍历右子树结点*/ /*后序遍历函数*/void houxu(BiTree T) if(T) houxu(T-lchild); /*遍历左子树结点*/ houxu(T-rchild); /*遍历右子树结点*/ printf(%c,T-data); /*遍历根结点*/ /*求

23、二叉树的树深*/int Depth(BiTree T) int dep=0,depl,depr; if(!T) dep=0; else depl=Depth(T-lchild); depr=Depth(T-rchild); dep=1+(depldepr?depl:depr); return dep; 程序运行界面输出如下：五、实验结论树的遍历是指按一定的规律走遍树的各个顶点，且使每一个顶点仅被访问一次，即找一个完整有规律的走法，以得到树中所有结点的一个线性排列。二叉树的遍历可分为 以下四种：先序遍历（DLR）、中序遍历(LDR)、后序遍历(LRD)和层次遍历。先序遍历是指先访问根节点，然后分

24、别先序遍历左子树、右子树；中序遍历是指先中序遍历左子树，然后访问根结点，最后中序遍历右子树；后序遍历是指先后序遍历左、右子树，然后访问根结点；层次遍历是指按二叉树的层序次序（即从根结点层至叶节点层），同一层中按先左子树再右子树的次序遍历二叉树。六、实验总结 通过此次实验，我掌握了二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解到了二叉树的按层遍历、先序非递归遍历及后序递归遍历。并且通过学习二叉树的这种非线性存储结构能够解决实际问题，例如哈夫曼问题。尤其是在编写程序的过程中，我明白了一个行之有效的程序，在于对所学知识的已掌握知识的利用和发挥， 并且我加深了对“数据结构+算法=程序”的理解和认识，这样有助于自己提高编写较复杂程序的能力。