实验五二叉树的常见操作
【背景知识】二叉树的存储、建立、遍历及其应用。
【目的要求】
1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
【实验内容】
1．输入字符序列，建立二叉链表。
2．中序遍历二叉树:递归算法。
算法如下：
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int status;
typedef struct BiNode
{
char Data;
struct BiNode* lChild;
struct BiNode* rChild;
}BiNode,*pBiNode;
status CreateTree(BiNode** pTree);
status InOrderTraval(BiNode* pTree);
status Visit(char Data);
status CreateTree(BiNode** pTree)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
{
(*pTree)=NULL;
}
else
{
if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode))))
{
exit(OVERFLOW);
}
(*pTree)->Data=ch;
CreateTree(&((*pTree)->lChild));
CreateTree(&((*pTree)->rChild));
}
return OK;
}
status InOrderTraval(BiNode* pTree)
{
if(pTree)
{
if(InOrderTraval(pTree->lChild))
{
if(Visit(pTree->Data))
{
if(InOrderTraval(pTree->rChild)) {
return OK;
}
}
return ERROR;
}
return ERROR;
}
else
{
return OK;
}
}
二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"<
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include
int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }
实验三二叉树的操作及应用 实验课程名：数据结构与算法 专业班级：15计科1班学号：201540410109 姓名：刘江 实验时间：2016.10.24-10.31 实验地点：K4-102 指导教师：冯珊 成绩: 一、实验目的及要求 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 任务一：完成下列程序，该程序以二叉链表作存储结构，构建如图1所示的二叉树， 并依次进行二叉树的前序、中序、后序及层次遍历。 图1 解答： （1）源代码：#include
else { if(!(T=(Node*)malloc(sizeof(Node)))){printf("Overflow.\n") ;exit(0);} T->data =ch; CreatBiTree(T->lchild ); CreatBiTree(T->rchild ); } return T; } void PrintData(DataType x) { printf("%c",x); } void PreOrder(BiTree T, void (*Visit)( DataType item)) /*前序遍历二叉树T，访问操作为Visit()函数*/ { if(T!= NULL) { Visit(T->data); PreOrder(T->lchild, Visit); PreOrder(T->rchild, Visit); } } void InOrder(BiTree T, void (*Visit)( DataType item)) /*中序t */ { if(T!= NULL) { InOrder(T->lchild, Visit); Visit(T->data); InOrder(T->rchild, Visit); } } void PostOrder(BiTree T, void (*Visit)( DataType item)) /*后序 */ { if(T!= NULL) { PostOrder(T->lchild, Visit); PostOrder(T->rchild, Visit); Visit(T->data); }
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);
正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师
一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：
实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。
三、算法设计 1、主要思想：二叉树是n(n>=0)个元素的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。在本实验中根据要求操作先序遍历二叉树：思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素（输出）,此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）...一直这样下去，直到栈为空。中序遍历二叉树：思想：利用栈。从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，有则进栈，没有则继续弹栈。重复下去....栈空，是判定条件。后序遍历二叉树算法：思想：利用栈来实现。从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素（只是取，并去弹栈），判断1:取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件（无右子节点，或者右子节点被访问过），则输出该结点，同时弹栈，并且记录下该访问的节点2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。 2、本程序包含七个模块 1）主函数
#include
if (treeNode->data == data) { return treeNode; } else//分别向左右子树查找 { if (ptr = TreeFindNode(treeNode->left, data))//左子树递归查找 { return ptr; } else if (ptr = TreeFindNode(treeNode->right, data))//右子树递归查找 { return ptr; } else { return NULL; } } } } /**********************添加结点*************************/ void AddTreeNode(CBTType *treeNode) { CBTType *pnode, *parent; DATA data; char menusel; if (pnode = new CBTType) //分配内存 { cout << "输入添加的二叉树结点数据：" << endl; cin >> pnode->data; pnode->left = NULL; //设置左子树为空 pnode->right = NULL; //设置左子树为空 cout << "输入该结点的父结点数据:" << endl; cin >> data; parent = TreeFindNode(treeNode, data); //查找父结点，获得结点指针 if (!parent) //没找到 { cout << "没有找到父结点!" << endl; delete pnode; return; } cout << "**********************" << endl;
实验五二叉树及其应用 1.目的要求： （1）通过实验掌握二叉树的两种基本的存储结构，及二叉树的建立、遍历，并加以应用。 （2）Huffman树建立、编码。 2.实验内容： （1）按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息 的统计（如各种结点数目、二叉树的高度等）； （2）建立一棵二叉排序树，并对其进行先序、中序、后序遍历。 （3）应用队列结构实现二叉树的层次遍历。 （4）设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数，并为其设计Huffman编码。 注：（1）～（2）必做，（3）～（4）选做。 三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页） （1）按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息 的统计（如各种结点数目、二叉树的高度等）； 程序代码： 头文件： #ifndef _H_ #define _H_ #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType e; struct BiTNode *LChild,*RChild; }BiTNode,*BiTree; Status Create(BiTree &T);
Status PrintElemType(TElemType e); Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e)); Status InOrderTraver(BiTree T,Status (* visit)(TElemType e)); Status PostOrderTraver(BiTree T,Status (* visit)(TElemType e)); Status Count(BiTree T); Status Countleaf(BiTree T); Status Counttwo(int n); Status Countone(int n,int n0,int n2); Status Depth(BiTree T); #endif 主函数： #include
******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include
二叉树操作的实现 #include
{ Visit(T->data); PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树} } void InOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) { InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树 Visit(T->data); // 再访问根结点 InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树} } void PostOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) // T不空 { PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); // 最后访问根结点 } } int LeafNum( BiTree T){ if(!T) return 0; else if(!T->lchild&&!T->rchild) return 1; else // printf("nihao"); return LeafNum(T->lchild)+LeafNum(T->rchild); }
实验五二叉树建立及应用 一、实验目的 1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。 2．能够利用二叉树解决具体问题。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉软件：DOS或Windows操作系统+Turbo C； 三、实验要求 ⒈要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的 操作。 ⒉输入数据：树中每个结点的数据类型设定为字符型。 3．设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历，求该二叉树所有叶子结点总数。 四、实验内容 附：参考程序为类C语言程序，非标准C语言程序，需要进行相应的修改。 二叉链表结构如下：P134 typedef struct lnode {char data; struct lnode *lchild,*rchild; }lnode,*tree;
1．建树子函数P137 status creat(tree &t) {//按先序次序输入二叉树中结点的值，’.’字符表示空树 scanf(&ch); if(ch=='.') t=null; else {t=(tree)malloc(sizeof(lnode)); t->data=ch; creat(t->lchild); creat(t->rchild);} return ok; } 2．先序遍历子函数P136 preorder(tree t) { if(t!=null) {printf(t->data); preorder(t->lchild); preorder(t->rchild); } } 3．后序遍历子函数P136 postorder(tree t) {if(t!=null) {postorder(t->lchild); postorder(t->rchild); printf(t->data); } } 五、思考题 1. 已知二叉树先序和中序序列，唯一地构造一棵二叉树并且验证其正确性。 2. 建立一个二叉树，并且按层次遍历操作。 六、报告要求 1．报告要求用专门的实验报告纸书写，字迹清晰，格式规范。 2．报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求。
学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990
学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 }
运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图：
实验五二叉树的存储表示和基本操作 实验内容 1. 二叉树的二叉链表的存储结构 —————二叉树的二叉链表存储表示———————— typedef struct node { ElemType data; /*数据元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ } BTNode; 2. 二叉树的基本操作 （1）创建操作：创建一棵二叉树。 （2）查找操作：查找二叉树中值为x的结点。 （3）查找左孩子操作：查找二叉树中值为x的结点的左孩子。 （4）查找右孩子操作：查找二叉树中值为x的结点的右孩子。 （5）求深度操作：求二叉树的深度。 （6）求宽度操作：求二叉树的宽度。 （7）求结点个数操作：求二叉树的结点个数。 （8）求叶子结点个数操作：求二叉树的叶子结点个数。 （9）输出操作：以括号表示法输出二叉树。 3. 链式队列操作实现的步骤 （1）实现将链式队列的存储结构和基本操作程序代码。 （2）实现main主函数。 4.程序代码完整清单 #include
算法与数据结构》课程实验报告
一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉
实验5：二叉树的基本操作(6学时) 一、实验目的 1.理解二叉树的基本概念和特点 2.掌握二叉树的链式存储结构 3.掌握二叉树的基本操作 4.掌握二叉树遍历操作 5.掌握哈夫曼树的构造算法和基本操作 二、实验内容 1. 实现二叉树的如下操作，二叉树如下图所示。(采用二叉链存储结构实现) (1)输出二叉树b； (2)输出C节点的左、右孩子节点值； (3)输出二叉树的深度； (4)输出二叉树b的节点个数； (5)输出二叉树b的叶子节点个数。 A B C D G E F b 具体效果如下：
三、实验要求 1.独立完成实验程序的编写与调试； 2.实验完成后填写实验报告，学习委员按学号从小到大的顺序提交。 四、思考题 1.思考二叉树先序遍历、中序遍历、后序遍历的递归和非递归算法的实现方法。 方法说明： (1)CreateBTNode(*b,*str)：根据二叉树括号表示法字符串str生成对应的二叉链存储结 构，后者的根节点为*b。 (2)FindNode(BTNode *b,ElemType x)：在二叉树b中寻找data域值为x的节点，并返回指 向该节点的指针。 (3)LchildNode(BTNode *p)：求二叉树中节点*p的左孩子节点。 (4)RchildNode(BTNode *p)：求二叉树中节点*p的右孩子节点。 (5)BTNodeDepth(BTNode *b)：求二叉树b的高度，若二叉树为空，则其高度为0；否则， 其高度等于左子树与右子树的高度中的最大高度加1。 (6)DispBTNode(BTNode *b)：以括号表示法输出一棵二叉树。 (7)Nodes(BTNode *b)：求二叉树b的节点个数 (8)LeafNodes(BTNode *b)：求二叉树b的叶子节点个数 (9)DestroyBTNode(BTNode *&b)：销毁二叉树b
实验六二叉树的基本操作 一、实验目的 1.掌握二叉树的基本概念； 2.掌握二叉树的二叉链表的存储结构； 3.掌握利用括号法表示二叉树的的构建方法，以及先、中、后序遍历和层序遍历的实现。 二、实验相关知识 1.复习C语言文件读写的相关知识 2.复习课本中第6章关于数的相关知识点； 三、实验内容与要求 1.建立一棵用二叉链表方式存储的二叉树，并利用凹凸法进行二叉树的打印；并对其进行遍历（先序、中序、后序和层序），并打印输出遍历结果。 【设计要求】输入为括号法表示的二叉树字符串序列，补充完整以下函数，实现二叉链表的建立，二叉树的遍历、以及二叉树的竖向打印。 void CreateBiTree(BiTree *bt) /*扩展的先序遍历结果构造二叉链表*/ void PreOrder(BiTree root)/*先序遍历二叉树*/ void PostOrder(BiTree root) /* 后序遍历二叉树*/ void InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */ int LayerOrder(BiTree bt) /* 层序遍历二叉树 */ void PrintTree(BiTree bt,int nLayer) /* 按竖向树状打印的二叉树 */ 【测试用例】设有以下的二叉树： 则添加空孩子进行扩展之后： 1、输入：A(B(C,D(E,F(G)))) 2、输出： 先序遍历：ABCDEFG 中序遍历：CBEDGFA 后序遍历：CEGFDBA 层序遍历：ABCDEFG 打印二叉树： A F
G D E B C 四、程序代码及运行结果 【程序代码】 #include
数据结构 实 验 报 告
1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程
2.3关键算法分析 算法一：Create(BiNode
算法三：PreOrder(BiNode