下载文档原格式
二叉树的建立与遍历实验报告（c语言编写,附源代码）二叉树的建立与遍历实验报告级班年月日姓名学号_1．实验题目建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
2．需求分析本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。
①输入的形式和输入值的范围：输入二叉树的先序，当其结点为空时，需要输入#。
（输入的先序仅含字母和#）②输出的形式：输出二叉树的先序、中序、后序。
③程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。
④测试数据：输入数据：输入ABC##DE#G##F###输出结果：二叉树的先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA3．概要设计1)为了实现上述程序功能，需要定义二叉链表的抽象数据类型：typedef struct BinaryTreeNode{TElemType data;//二叉树结点中的数据域struct BinaryTreeNode *lchild , *rchild; //二叉树结点的左孩子和右孩子指针}BinaryTreeNode ,*BiTree;基本操作：A.void CreateBinaryTree (BiTree &T)初始条件：无操作结果：建立了二叉树。
B. void PreOrder(BiTree T)初始条件：存在一棵二叉树操作结果：先序遍历二叉树，并且输出先序遍历的结果。
C. void MidOrder(BiTree T)初始条件：存在一棵二叉树操作结果：中序遍历二叉树，并且输出中序遍历的结果。
D. void PostOrder(BiTree T)初始条件：存在一棵二叉树操作结果：后序遍历二叉树，并且输出后序遍历的结果。
程序包含5个函数：○1主函数main()○2先序建立二叉树 void CreateBinaryTree (BiTree &T)○3先序遍历二叉树，并且输出先序遍历的结果void PreOrder(BiTree T);○4中序遍历二叉树，并且输出中序遍历的结果void MidOrder(BiTree T);○5序遍历二叉树，并且输出后序遍历的结果void PostOrder(BiTree T); 各函数间关系如下：主函数main()CreateBinaryTree PreOrder MidOrder PostOrder4．详细设计1)二叉链表的定义typedef struct BinaryTreeNode{定义一个树结点的数据域;定义一个该结点的左孩子指针和右孩子指针;}2)void CreateBinaryTree (BiTree &T)//先序建立二叉树{输入一个字符量;if(输入字符== '#') T指针置值为NULL;else{动态申请一个指向二叉树结构体的指针把输入字符赋值给新指针的数据域data;调用CreateBinaryTree(新指针的lchild成员);调用CreateBinaryTree(新指针的rchild成员);}}3)void PreOrder(BiTree T) //先序遍历二叉树{if(T指针不为NULL){输出T的data域;先序遍历左子树;先序遍历右子树;}}4)void MidOrder(BiTree T) //中序遍历二叉树{if(T指针不为NULL){中序遍历左子树;输出T的data域;中序遍历右子树;}}5)void PostOrder(BiTree T) //中序遍历二叉树{if(T指针不为NULL){后序遍历左子树;后序遍历右子树;输出T的data域;}}5．调试分析在编写程序过程中，我将scanf（”%c”,&ch）中的%c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。
二叉树的遍历实验报告二叉树的遍历实验报告引言：二叉树是一种常见的数据结构，它由节点和连接节点的边组成。
在实际应用中，我们经常需要对二叉树进行遍历，以便对其中的节点进行访问和操作。
本次实验旨在探索二叉树的遍历算法，并通过实验验证其正确性和效率。
一、二叉树的定义和基本操作二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
根据节点的访问顺序，二叉树的遍历可以分为前序遍历、中序遍历和后序遍历三种方式。
前序遍历是指先访问根节点，然后按照左子树、右子树的顺序递归地进行遍历；中序遍历是指先按照左子树、根节点、右子树的顺序递归地进行遍历；后序遍历是指先按照左子树、右子树、根节点的顺序递归地进行遍历。
二、实验设计和方法为了验证二叉树的遍历算法的正确性和效率，我们设计了以下实验方案：1. 构建二叉树：我们首先构建一个具有一定规模的二叉树，以模拟实际应用中的情况。
为了方便起见，我们选择随机生成一棵二叉树，并确保其结构合理。
2. 实现遍历算法：我们根据前文所述的遍历方式，实现了相应的遍历算法。
在实现过程中，我们考虑到了递归和迭代两种方式，并分别进行了实验比较。
3. 遍历实验：我们使用不同规模的二叉树进行遍历实验，并记录遍历的结果和所花费的时间。
通过对比不同规模下不同遍历方式的结果和时间，我们可以评估遍历算法的效率和准确性。
三、实验结果和分析在实验中，我们构建了一棵具有1000个节点的二叉树，并分别使用前序、中序和后序遍历算法进行遍历。
通过实验结果的比较，我们得出以下结论：1. 遍历结果的正确性：无论是前序、中序还是后序遍历，我们都能够正确地访问到二叉树中的每个节点。
这表明我们所实现的遍历算法是正确的。
2. 遍历算法的效率：在1000个节点的二叉树中，我们发现中序遍历算法的执行时间最短，后序遍历算法的执行时间最长，前序遍历算法的执行时间居中。
这是因为中序遍历算法在访问节点时可以尽可能地减少递归次数，而后序遍历算法需要递归到最深层才能返回。
二叉树的遍历算法实验报告二叉树的遍历算法实验报告引言：二叉树是计算机科学中常用的数据结构之一，它是由节点组成的层次结构，每个节点最多有两个子节点。
在实际应用中，对二叉树进行遍历是一项重要的操作，可以帮助我们理解树的结构和节点之间的关系。
本文将介绍二叉树的三种遍历算法：前序遍历、中序遍历和后序遍历，并通过实验验证其正确性和效率。
一、前序遍历前序遍历是指先访问根节点，然后按照先左后右的顺序遍历左右子树。
具体的实现可以通过递归或者使用栈来实现。
我们以递归方式实现前序遍历算法，并进行实验验证。
实验步骤：1. 创建一个二叉树，并手动构造一些节点和它们之间的关系。
2. 实现前序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先访问当前节点，然后递归调用函数遍历左子树，最后递归调用函数遍历右子树。
4. 调用前序遍历函数，输出遍历结果。
实验结果：经过实验，我们得到了正确的前序遍历结果。
这证明了前序遍历算法的正确性。
二、中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。
同样，我们可以使用递归或者栈来实现中序遍历算法。
在本实验中，我们选择使用递归方式来实现。
实验步骤：1. 继续使用前面创建的二叉树。
2. 实现中序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先递归调用函数遍历左子树，然后访问当前节点，最后递归调用函数遍历右子树。
4. 调用中序遍历函数，输出遍历结果。
实验结果：通过实验，我们得到了正确的中序遍历结果。
这证明了中序遍历算法的正确性。
三、后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。
同样，我们可以使用递归或者栈来实现后序遍历算法。
在本实验中，我们选择使用递归方式来实现。
实验步骤：1. 继续使用前面创建的二叉树。
2. 实现后序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先递归调用函数遍历左子树，然后递归调用函数遍历右子树，最后访问当前节点。
4. 调用后序遍历函数，输出遍历结果。
北京林业大学实验任务书北京林业大学15学年—16学年第 1 学期数据结构C实验任务书专业名称：实验学时： 4课程名称：数据结构C 任课教师：孟伟实验题目：二叉树的基本操作实验环境： Visual C++ 6.0实验目的：1．掌握二叉树的定义；2．掌握二叉树的基本操作，如建立、前序遍历、中序遍历和后序遍历、结点个数的统计等。
实验内容：用递归的方法实现以下算法：1．以二叉链表表示二叉树，建立一棵二叉树；2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果；4．输出二叉树的后序遍历结果；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；7．计算二叉树的深度。
8．交换二叉树每个结点的左孩子和右孩子；选做内容设计二叉树的双序遍历(DblOrderTraverse)算法（双需遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
实验提示：1．统计二叉树的叶结点个数。
int LeafNodeCount(BiTree T ){如果是空树，则叶子个数为0;如果是叶子结点，则叶子结点个数为1（如何表示叶子结点？？？）否则叶结点个数为左子树的叶结点个数+右子树的叶结点个数}2．计算二叉树的深度。
int Depth(BiTree T){如果是空树，则深度为0;否则(1)计算左子树的深度记为m；(2)计算右左子树的深度记为n；二叉树的深度为m 与n的较大者加1}实验要求：(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。
(2) 程序要添加适当的注释，程序的书写要采用缩进格式。
(3) 根据实验报告模板详细书写实验报告,源程序保存为“sy2.cpp”，实验报告命名为“实验报告2.doc”。
将这两个文件压缩为一个文件，按以下方式命名：学号姓名.rar，上传到ftp的相应班级所在文件夹。
二叉树实验报告09信管石旭琳 20091004418一、实验目的：1、理解二叉树的遍历算法及应用2、理解哈夫曼树及其应用。
3、掌握哈夫曼编码思想。
二、实验内容：1、建立二叉树二叉链表2、实现二叉树递归遍历算法（中序、前序、后序）3、求二叉树高度4、求二叉树结点个数5、求二叉树叶子个数6、将序号为偶数的值赋给左子树三、主要程序：#include<stdio.h>#include<stdlib.h>typedef int ElemType;struct BiTNode{ElemType data;struct BiTNode *lch,*rch;}BiTNode,*BiTree;struct BiTNode *creat_bt1();struct BiTNode *creat_bt2();void preorder (struct BiTNode *t);void inorder (struct BiTNode *t);void postorder (struct BiTNode *t);void numbt (struct BiTNode *t);int n,n0,n1,n2;void main(){int k;printf("\n\n\n");printf("\n\n 1.建立二叉树方法1(借助一维数组建立)"); printf("\n\n 2.建立二叉树方法2(先序递归遍历建立)"); printf("\n\n 3.先序递归遍历二叉树");printf("\n\n 4.中序递归遍历二叉树");printf("\n\n 5.后序递归遍历二叉树");printf("\n\n 6.计算二叉树结点个数");printf("\n\n 7.结束程序运行");printf("\n==================================="); do{printf("\n请输入你要执行的操作(1,2,3,4,5,6,7)");scanf("%d",&k);printf("\n");switch(k){case 1:{printf("你选择的是操作1，现用方法1进行建立二叉树\n");BiTree=creat_bt1(); /* 调用性质5建立二叉树算法*/break;}case 2:{printf("你选择的是操作2，现用方法2进行建立二叉树\n");BiTree=creat_bt2(); /* 调用递归建立二叉树算法*/break;}case 3:{printf("你选择的是操作3，现进行先序递归遍历二叉树\n结果为:");preorder(BiTree);break;}case 4:{printf("你选择的是操作4，现进行中序递归遍历二叉树\n结果为:");inorder(BiTree);break;}case 5:{printf("你选择的是操作5，现进行后序递归遍历二叉树\n结果为:");postorder(BiTree);break;}case 6:{ n=0,n0=0,n1=0,n2=0; /*全局变量置0 */printf("你选择的是操作6，现进行计算二叉树结点个数\n结果为:");numbt(BiTree);printf("\n 二叉树结点总数是：%d",n);printf("\n 二叉树叶子结点数是：%d",n0);printf("\n 度为1的结点数是：%d",n1);printf("\n 度为2的结点数是：%d",n2);break;}case 7:{printf("你选择的是操作8，将结束本程序运行，谢谢你的使用，再见！\n");break;}}}while(k>=1&&k<7);}struct BiTNode *creat_bt1(){struct BiTNode *v[50],*p,*t;int i,j;ElemType e; /*输入结点的序号i、结点的数据e */printf("\n i,data=");scanf("%d,%d",&i,&e);while(i!=0&&e!=0){p=(struct BiTNode *)malloc(sizeof(struct BiTNode));p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if (i==1) /*序号为1的结点是根*/t=p;else{j=(i+1)/2;if(i%2==0) /*序号为偶数，做左孩子*/v[j]->lch=p;elsev[j]->rch=p;}printf("\n i,data=");scanf("%d,%d",&i,&e);}return t;}struct BiTNode *creat_bt2(){struct BiTNode *t;int e;printf("\n data=");scanf("%d",&e);if(e==0) t=NULL; /*对于0值，不分配新结点*/else{t=(struct BiTNode *)malloc(sizeof(struct BiTNode));t->data=e;t->lch=creat_bt2(); /*左孩子获得新指针值*/t->rch=creat_bt2();}return (t);}void preorder (struct BiTNode *t){if(t){printf("%d ",t->data);preorder(t->lch);preorder(t->rch);}}void inorder (struct BiTNode *t){if(t){inorder(t->lch);printf("%d ",t->data);inorder(t->rch);}}void postorder(struct BiTNode *t){if(t){postorder(t->lch);postorder(t->rch);printf("%d ",t->data);}}void numbt(struct BiTNode *t){if(t){numbt(t->lch);{n++;if(t->lch==NULL&&t->rch==NULL)n0++;if((t->lch==NULL&&t->rch!=NULL)||(t->lch!=NULL&&t->rch==NUL L))n1++;if(t->lch!=NULL&&t->rch!=NULL)n2++;}numbt(t->rch);}}四、测试结果：五、小结：实操后还是会搞不清楚数据域及指针域的定义类型的不同。
二叉树的建立与遍历一、实验目的进一步理解二叉树的逻辑结构和存储结构，掌握二叉树的建立与遍历算法。
二、实验内容1、用二叉链表创建二叉树①输入根结点值；②若左子树不空，则输入左子树，否则输入一个结束符；③若右子树不空，则输入右子树，否则输入一个结束符。
例如：FCA▲▲DB▲▲▲E▲GH▲▲P▲▲其中▲表示结束符2、遍历该二叉树(1) 先序遍历(DLR)若二叉树为空，则结束返回。
否则：①访问根结点；②先序遍历左子树；③先序遍历右子树。
(2) 中序遍历(LDR)若二叉树为空，则结束返回。
否则：①中序遍历左子树；②访问根结点；③中序遍历左子树。
(3) 后序遍历(LRD)若二叉树为空，则结束返回。
否则：①后序遍历左子树；②后序遍历左子树；③访问根结点。
实验思想：根据要求，输入二叉树各结点对应的编号和数值，建立一棵空树，存储相应数值并使左子树和右子树均为空树，根据计算，若编号为偶数则为左子树，若为奇数则为右子树。
最后遍历二叉树。
三、实验算法流程图与程序清单（一）二叉树的建立与先序遍历：1、算法流程图：2、实验清单：{char data;struct node1 *lchild,*rchild;}BTCHINALR;BTCHINALR * createbt( ){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != '$'){q = (BTCHINALR*)malloc(sizeof(BTCHINALR));q->data = x; q->lchild = NULL; q->rchild = NULL;s[i] = q;if(i != 1){j = i / 2;if(i % 2 == 0) s[j]->lchild = q;else s[j]->rchild = q;}printf("i,x = ");scanf("%d,%c",&i,&x);}return s[1];}void inorder(BTCHINALR *bt){if(bt != NULL){ inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild); }}main( ){ BTCHINALR *bt;char ch;int i;bt = createbt(); i = 1;while(i) {printf("\n先序遍历二叉树(递归按y键，): ");fflush(stdin);scanf("%c",&ch);if(ch == 'y') inorder(bt);printf("\n");}3、实验结果：建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开i,x = 1,li,x = 2,ki,x = 3,yi,x = 4,bi,x =5,si,x = 7,ci,x =11,vi,x = 15,ri,x = 0,$先序遍历二叉树(递归按y键，): yl k b s v y c r（二）、二叉树的建立与中序遍历:1、算法流程图：2、实验清单：{char data;struct node1 *lchild,*rchild;}BTCHINALR;BTCHINALR * createbt( ){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != '$'){q = (BTCHINALR*)malloc(sizeof(BTCHINALR));q->data = x; q->lchild = NULL; q->rchild = NULL;s[i] = q;if(i != 1){j = i / 2;if(i % 2 == 0) s[j]->lchild = q;else s[j]->rchild = q;}printf("i,x = ");scanf("%d,%c",&i,&x);}return s[1];}void inorder(BTCHINALR *bt){if(bt != NULL){ inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild); }}main( ){ BTCHINALR *bt;char ch;int i;bt = createbt(); i = 1;while(i) {printf("\n先序遍历二叉树(递归按y键，): ");fflush(stdin);scanf("%c",&ch);if(ch == 'y') inorder(bt);printf("\n");}3、实验结果：建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开i,x = 1,li,x = 2,ki,x = 3,yi,x = 4,bi,x =5,si,x = 7,ci,x =11,vi,x = 15,ri,x = 0,$先序遍历二叉树(递归按y键，): yl k b s v y c r四、实验心得体会通过这次实验，锻炼了自己编程的能力，加深了自己对有关知识的理解。
二叉树的遍历实验报告实验报告：二叉树的遍历（先序遍历、中序遍历、后序遍历）一、引言二叉树是一种非常常见的数据结构，在计算机领域有着广泛的应用。
对二叉树进行遍历操作是其中最基本的操作之一、本实验旨在通过对二叉树的先序遍历、中序遍历和后序遍历的实践，加深对二叉树遍历算法的理解和掌握。
二、目的1.掌握二叉树先序遍历的算法原理和实现方法；2.掌握二叉树中序遍历的算法原理和实现方法；3.掌握二叉树后序遍历的算法原理和实现方法；4.使用递归和非递归两种方式实现以上三种遍历算法；5.进行正确性验证和性能评估。
三、方法1.算法原理：1.1先序遍历：先访问根节点，然后递归遍历左子树，再递归遍历右子树；1.2中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树；1.3后序遍历：先递归遍历左子树，再递归遍历右子树，最后访问根节点。
2.实现方法：2.1递归实现：采用函数递归调用的方式，实现对二叉树的遍历；2.2非递归实现：采用栈的数据结构，模拟递归的过程，实现对二叉树的遍历。
四、实验步骤1.数据结构设计：1.1定义二叉树的节点结构，包括节点值和两个指针（分别指向左子节点和右子节点）；1.2定义一个栈结构，用于非递归实现时的辅助存储。
2.先序遍历：2.1递归实现：按照先序遍历的原理，通过递归调用遍历左子树和右子树，再输出根节点；2.2非递归实现：通过栈结构模拟递归的过程，先将根节点入栈，然后循环将栈顶节点弹出并输出，再将其右子节点入栈，最后将左子节点入栈，直到栈为空。
3.中序遍历：3.1递归实现：按照中序遍历的原理，通过递归调用先遍历左子树，再输出根节点，最后遍历右子树；3.2非递归实现：先将根节点入栈，然后循环将左子节点入栈，直到左子节点为空，然后弹出栈顶节点并输出，再将其右子节点入栈，重复以上过程直到栈为空。
4.后序遍历：4.1递归实现：按照后序遍历的原理，通过递归调用先遍历左子树，再遍历右子树，最后输出根节点；4.2非递归实现：通过栈结构模拟递归的过程，先将根节点入栈，然后重复以下步骤直到栈为空。
二叉树的遍历实验报告一、需求分析在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。
对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。
二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。
本次实验要实现先序、中序、后序三种遍历。
基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。
二、系统总框图三、各模块设计分析（1）建立二叉树结构建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。
本实验用的是先序遍历的规则进行建树。
二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。
因此要先定义一个结构体。
此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。
最后，还需要一个链表的头指针指向根结点。
要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。
当它遇到该标志时，就指向为空。
建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。
（2）输入二叉树元素输入二叉树时，是按上面所确定的遍历规则输入的。
最后，用一个返回值来表示所需要的结果。
（3）先序遍历二叉树当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
（4）中序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
（5）后序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
二叉树二叉链表表示及实现实验报告实验三二叉树的二叉链表表示及实现实验项目中文名称：二叉树的二叉链表表示及实现实验项目英文名称：Definition and Implementation of Binary Tree 实验学时：2学时一、实验目的1、深入了解二叉树的特性，掌握二叉树的二叉链表表示及实现方法。
2、掌握二叉树的递归遍历算法。
二、实验内容1、编写函数，创建一棵二叉树；2、编写函数，用递归算法分别求二叉树的各种遍历序列；3、编写函数，用非递归算法求二叉树的中序遍历序列。
4、编写函数，用非递归算法求二叉树的先序和后序遍历序列。
（选做）三、设计概要1、核心数据结构二叉树的链式存储结构表示typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;} BiTNode;结构示意图：2,二叉树的链式存储算法实现Status CreateBiTree(BiTree * Tp){//创建一棵二叉树；char ch;scanf(“%c”,…ch);getchar();if(ch ==' ')Tp = NULL;else {Tp=(BiTree)malloc(sizeof(BiTNode));Tp->data=ch;printf(“输入%c的左子树：”,ch);creatBitree(Tp->lchild);printf(“输入%c的右子树：”,ch);creatBitree(Tp->rchild); }}程序框架结构与流程图遍历：即将树的所有结点访问且仅访问一次。
按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树中序遍历：左子树->根节点->右子树后序遍历：左子树->右子树->根节点（1）序遍历二叉树：若二叉树为空，则空操作；否则，先访问根节点->先序遍历左子树->先序遍历右子树。
数据结构实验报告报告题目: 二叉树的基本操作学生班级:学生姓名: 学号:一. 实验目的1、基本要求: 深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。
2. 较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
二.实验学时：课内实验学时: 3学时课外实验学时: 6学时三. 实验题目1. 以二叉链表为存储结构, 实现二叉树的创建、遍历（实验类型: 验证型）1）问题描述：在主程序中设计一个简单的菜单, 分别调用相应的函数功能：1…建立树2…前序遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求: 在程序中定义下述函数, 并实现要求的函数功能:CreateBinTree(BinTree &T): 按从键盘输入的前序序列, 创建树Preorder(BinTree &T): 前序遍历树（递归）Inorder(BinTree &T): 中序(递归)遍历树Postorder(BinTree &T): 后序遍历树（递归）PostTreeDepth(BinTree &T): 树的高度leaf(BinTree &T):树的叶子节点InorderN(BinTree &T): 中序(非递归)遍历树3)数据结构二叉链表存储数据类型定义typedef struct node{TElemType data;struct node *lchild,*rchild;}BinTNode;元素类型:int CreateBinTree(BinTree &T);void Preorder(BinTree &T);void Inorder(BinTree &T);void Postorder(BinTree &T);void InorderN(BinTree &T);int PostTreeDepth(BinTree &T);int leaf(BinTree &T);2.编写算法实现二叉树的非递归中序遍历和求二叉树高度。
