二叉树结点染色问题 实验报告

实验报告：二叉树第一篇：实验报告：二叉树实验报告二叉树一实验目的1、进一步掌握指针变量，动态变量的含义；2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。

二实验原理树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。

在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。

树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。

遍历二叉树的实质是将非线性结构转为线性结构。

三使用仪器，材料计算机 2 Wndows xp 3 VC6.0四实验步骤【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。

【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。

【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。

五实验过程原始记录基本数据结构描述； 2 函数间的调用关系；用类C语言描述各个子函数的算法；附录：源程序。

六试验结果分析将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。

第二篇：数据结构-二叉树的遍历实验报告实验报告课程名：数据结构（C语言版）实验名：二叉树的遍历姓名：班级：学号：时间：2014.11.03一实验目的与要求1.掌握二叉树的存储方法2.掌握二叉树的三种遍历方法3.实现二叉树的三种遍历方法中的一种二实验内容• 接受用户输入一株二叉树• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序三实验结果与分析//*********************************************************** //头文件#include #include //*********************************************************** //宏定义#define OK 1 #define ERROR 0 #define OVERFLOW 0//*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//******************************** *************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树//构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;Creat eBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrd erTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderT raverse(T->rChild);} }//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild) ;printf(“%c”,T->data);} }//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}图1:二叉树的遍历运行结果第三篇：数据结构二叉树操作验证实验报告班级：计算机11-2 学号：40 姓名：朱报龙成绩：_________实验七二叉树操作验证一、实验目的⑴ 掌握二叉树的逻辑结构；⑵ 掌握二叉树的二叉链表存储结构；⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。

数据结构二叉树前驱结点的实验报告二叉树的前驱结点是指在中序遍历中，一个节点的前面那个节点，即左子树中最大的节点。

为了实现二叉树前驱结点的查找，我进行了如下实验。

首先，需要定义二叉树的数据结构。

在这个数据结构中，每个节点包含三个参数：值，左子节点和右子节点。

这个数据结构可以使用递归方式来定义。

接下来，需要定义查找前驱节点所需要的函数。

这个函数的参数是二叉树中的一个节点，函数的返回值是这个节点的前驱节点。

如果这个节点是二叉树中的根节点，那么它没有前驱节点，函数返回 null。

如果这个节点没有左子节点，那么前驱节点一定是它的某个祖先节点。

对于这种情况，可以向上递归，直到找到一个祖先节点，该祖先节点的右子节点是该节点或者该节点的某个祖先节点。

如果这个节点有左子节点，那么前驱节点一定是该节点的左子树中最右边的节点。

对于这种情况，可以向左递归，直到找到最右边的节点。

如果没有左子树，那么该节点的前驱节点就是null。

我实现了这个函数，并在一些测试用例上测试它的效果。

首先，我使用了一个简单的二叉树来进行测试。

这个二叉树包含了三个节点，根节点的值是2，左子节点的值是1，右子节点的值是3、我测试了根节点和右子节点的前驱节点，结果都是左子节点。

接下来，我测试了一个更复杂的二叉树，该二叉树包含了七个节点，是一个完整的二叉树。

我测试了二叉树中每一个节点的前驱节点，结果都是正确的。

通过这个实验，我学习了如何在二叉树中查找前驱节点。

这项技能在很多算法和数据结构中都有很多应用。

通过使用递归的方式，我可以在一些复杂的二叉树中轻松地查找前驱节点。

这种技能对于我今后的编程生涯非常重要，能够帮助我更高效地解决各种问题。

（一）需求和规格说明一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。

任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

（二）设计分析过程：这是一道二叉树的染色问题，求染成绿色的最大最小情况，从本质上看，这是一道动态规划问题。

为了方便直观起见，代码开始时用先enum Color{nocolor = 0,green = 1,red = 2,blue = 3};定义了不同的颜色。

举个简单的例子，如下图所示：将整个二叉树划分成三个部分：根节点、左子树、右子树。

由于有约束条件，所以这三个部分存在着互相限制作用如下：1. 二叉树的根节点与左子树的根节点颜色不同；2.二叉树的根节点与右子树的根节点颜色不同；3.左子树根节点与右子树根节点颜色不同。

显然，上述的三个限制表示的是标号为1、2、3三个点之间的互相关系。

除此以外，左子树中的点与右子树中的点没有任何直接的限制关系！也就是说，如果我们事先确定了上述二叉树中标号为1、2、3的三个点的颜色，那么接下来，对左子树染色和对右子树染色将变成两个互不干扰的子问题，左子树最值与右子树最值不影响，可以分开求解。

【互不干扰，可以分开求解】如此一来，通过将三点染色，我们就可以把二叉树分成左右两个子树，整个问题被分解成两个较小规模的子问题。

算法设计：如图二所示，将二叉树划分成三部分，给标号为1、2、3三个点先染色后，将依次处理左子树，右子树。

在求解时，有以下2个问题：（1）染色的任意性标号为1、2、3的三个点的颜色并不一定固定依次是红、绿、蓝。

我们需要对所有染色情况进行枚举，并对每个染色情况进行左、右子树的分别处理。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：1.掌握二叉树的基本操作；2.理解二叉树的性质；3.熟悉二叉树的广度优先遍历和深度优先遍历算法。

二、实验原理：1.二叉树是一种树形结构，由n(n>=0)个节点组成；2.每个节点最多有两个子节点，称为左子节点和右子节点；3.二叉树的遍历分为四种方式：前序遍历、中序遍历、后序遍历和层次遍历。

三、实验环境：1.编程语言：C++；2.编译器：Dev-C++。

四、实验内容：1.定义二叉树节点结构体：struct BinaryTreeNode{int data; // 节点数据BinaryTreeNode *leftChild; // 左子节点指针BinaryTreeNode *rightChild; // 右子节点指针};2.初始化二叉树：queue<BinaryTreeNode *> q; // 使用队列存储节点q.push(root);int i = 1; // 创建子节点while (!q.empty() && i < length){BinaryTreeNode *node = q.front();q.pop();if (data[i] != -1) // 创建左子节点 {BinaryTreeNode *leftChild = new BinaryTreeNode;leftChild->data = data[i];leftChild->leftChild = nullptr;leftChild->rightChild = nullptr;node->leftChild = leftChild;q.push(leftChild);}i++;if (data[i] != -1) // 创建右子节点 {BinaryTreeNode *rightChild = new BinaryTreeNode;rightChild->data = data[i];rightChild->leftChild = nullptr;rightChild->rightChild = nullptr;node->rightChild = rightChild;q.push(rightChild);}i++;}return root;}3.前序遍历二叉树：五、实验结果：输入：int data[] = {1, 2, 3, 4, -1, -1, 5, 6, -1, -1, 7, 8};输出：前序遍历结果：1 2 4 5 3 6 7 8中序遍历结果：4 2 5 1 6 3 7 8后序遍历结果：4 5 2 6 8 7 3 1层次遍历结果：1 2 3 4 5 6 7 8通过本次实验，我深入理解了二叉树的性质和遍历方式，并掌握了二叉树的基本操作。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算学院：化学与材料科学学院专业班级：09级材料科学与工程系PB0920603姓名：李维谷学号：PB09206285邮箱：liwg@指导教师：贾伯琪实验时间：2010年10月17日一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E 后，以广义表形式打印A （B （C,D （,F ）））输 入 二：ABD □□EH □□□CF □G □□□ （以□表示空格）,查找10,删除B 预测结果：先序遍历 ABDEHCFG中序遍历 DBHEAGFC 后序遍历 DHEBGFCA层次遍历 ABCDEFHG广义表打印 A （B(D,E(H)),C(F(,G))）叶子数 3 深度 4 宽度 3 非空子孙数 7 度为2的数目 2 度为1的数目3 查找10，失败。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

⼆叉树基本操作--实验报告实验三⼆叉树的基本操作学院:物理与电⼦学院班级:电信1105班姓名:刘岩学号:29⼀、实验⽬的1、熟悉⼆叉树的基本操作，掌握⼆叉树的实现以及实际应⽤。

3、加深对于⼆叉树的理解，逐步培养解决实际问题的编程能⼒。

⼆、实验环境1台WINDOWS环境的PC机，装有Visual C++ 。

三、实验内容1、问题描述现需要编写⼀套⼆叉树的操作函数，以便⽤户能够⽅便的利⽤这些函数来实现⾃⼰的应⽤。

其中操作函数包括：1>创建⼆叉树CreateBTNode(*b,*str)：根据⼆叉树括号表⽰法的字符串*str⽣成对应的链式存储结构。

2>输出⼆叉树DispBTNode(*b)：以括号表⽰法输出⼀棵⼆叉树。

3>查找结点FindNode(*b,x)：在⼆叉树b中寻找data域值为x的结点,并返回指向该结点的指针。

4>求⾼度BTNodeDepth(*b)：求⼆叉树b的⾼度。

若⼆叉树为空,则其⾼度为0；否则,其⾼度等于左⼦树与右⼦树中的最⼤⾼度加l。

5>求⼆叉树的结点个数NodesCount(BTNode *b)6>先序遍历的递归算法：void PreOrder(BTNode *b)7>中序遍历的递归算法：void InOrder(BTNode *b)8>后序遍历递归算法：void PostOrder(BTNode *b)9>层次遍历算法void LevelOrder(BTNode *b)2、基本要求实现以上9个函数。

主函数中实现以下功能：创建下图中的树b输出⼆叉树b找到’H’节点，输出其左右孩⼦值输出b的⾼度输出b的节点个数输出b的四种遍历顺序3、程序编写上图转化为⼆叉树括号表⽰法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))程序:#include <>#include <>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩⼦*/struct node *rchild; /*指向右孩⼦*/} BTNode;void CreateBTNode(BTNode *&b,char *str);//创建BTNode *FindNode(BTNode *b,ElemType x);//查找节点int BTNodeHeight(BTNode *b);//求⾼度void DispBTNode(BTNode *b);//输出int NodesCount(BTNode *b);//⼆叉树的结点个数void PreOrder(BTNode *b);//先序遍历递归void InOrder(BTNode *b);//中序遍历递归void PostOrder(BTNode *b);//后序遍历递归void LevelOrder(BTNode *b);//层次遍历//创建void CreateBTNode(BTNode *&b,char *str){BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=str[j];while(ch!='\0'){switch(ch){case '(':top++;St[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}//输出void DispBTNode(BTNode *b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL||b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);printf(")");}}}//查找节点BTNode *FindNode(BTNode *b,ElemType x){ BTNode *p;if(b==NULL)return b;else if(b->data==x)return b;else{p=FindNode(b->lchild,x);if(p!=NULL)return p;elsereturn FindNode(b->rchild,x);}}//求⾼度int BTNodeHeight(BTNode *b){int lchildh,rchildh;if(b==NULL)return (0);else{lchildh=BTNodeHeight(b->lchild);rchildh=BTNodeHeight(b->rchild);return(lchildh>rchildh)(lchildh+1):(rchildh+1);}}//⼆叉树的结点个数int NodesCount(BTNode *b){if(b==NULL)return 0;elsereturn NodesCount(b->lchild)+NodesCount(b->rchild)+1; }//先序遍历递归void PreOrder(BTNode *b){ if(b!=NULL){printf("%c",b->data); PreOrder(b->lchild); PreOrder(b->rchild);}}//中序遍历递归void InOrder(BTNode *b){if(b!=NULL){InOrder(b->lchild);printf("%c",b->data); InOrder(b->rchild);}}//后序遍历递归void PostOrder(BTNode *b){ if(b!=NULL){PostOrder(b->lchild); PostOrder(b->rchild);printf("%c",b->data);}}//层次遍历void LevelOrder(BTNode *b){ BTNode *p;BTNode *qu[MaxSize];int front,rear;front=rear=-1;rear++;qu[rear]=b;while(front!=rear){front=(front+1)%MaxSize;p=qu[front];printf("%c",p->data);if(p->lchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=p->lchild;}if(p->rchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=p->rchild;}}}void main(){BTNode *b,*p,*lp,*rp;char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//根据树形图改写成的//⼆叉树括号表⽰法的字符串*str //char str[100];scanf("%s",&str);//⾃⾏输⼊括号表⽰的⼆叉树CreateBTNode(b,str); //创建树bprintf("\n");printf("输出⼆叉树:");//输出⼆叉树bDispBTNode(b);printf("\n");printf("'H'结点:");//找到'H'节点，输出其左右孩⼦值p=FindNode(b,'H');printf("\n");if (p!=NULL){printf("左孩⼦节点的值");printf("%c",p->lchild->data);printf("\n");printf("右孩⼦节点的值");printf("%c",p->rchild->data);printf("\n");//此处输出p的左右孩⼦节点的值}printf("\n");printf("⼆叉树b的深度:%d\n",BTNodeHeight(b));//输出b的⾼度printf("⼆叉树b的结点个数:%d\n",NodesCount(b));//输出b的节点个数printf("\n");printf(" 先序遍历序列:\n");//输出b的四种遍历顺序printf(" 算法:");PreOrder(b);printf("\n");printf(" 中序遍历序列:\n");printf(" 算法:");InOrder(b);printf("\n");printf(" 后序遍历序列:\n");printf(" 算法:");PostOrder(b);printf("\n");printf(" 层次遍历序列:\n");printf(" 算法:");LevelOrder(b); printf("\n");}四、实验⼼得与⼩结通过本次实验，我熟悉⼆叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

河南农业大学数据结构实验报告专业/班级实验时间地点姓名实验二一、实验目的学习上操作树的各种基本操作，重点掌握以下操作创建、遍历、显示二叉树，通过二叉树的基本操作，掌握树结构的处理方法。

并以此为基本思想延伸树的应用。

二、问题描述1.建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。

2.按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。

3.按凹入表形式打印树形结构。

三、数据结构设计1.对于二叉树来说，每个节点最多有两个孩子，采用链式方式存储，每个结点的值域有数据域（data），两个指针域左海子（lchild）右孩子（rchild），该结点的深度（degree）。

但是如果打印二叉树的话则每个节点的深度规定根节点的深度为0，其孩子结点的深度为1并且兄弟节点的深度是相同的，则二叉树结点的结构为data lchild rchild degree2.对与树使用孩子---兄弟的数据结构即每个结点有两个域为指向孩子节点（firstchild）和下个兄弟域（nextsibling）firstchild nextsibling三．功能设计1.二叉树的算法思想（1）对二叉树的遍历用递归思想，改变访问根节点的顺序来实施遍历。

（2）如果打印二叉树则需要构造完全二叉树，若空结点，用相同的变量的代替。

遍历的时候是先遍历右子树的中序遍历。

建立的时候先建立一个根结点，若不是空的话，则为其孩子节点，重复操作直到建立完整的二叉树。

（3）打印树在遍历是的时候用先根遍历。

建立需要使用队列的数据结构相结合存储树。

编码实现四、运行与调试一．先序遍历二．中序遍历三．递归后续遍历二叉树四．打印二叉树五．打印树五、实验完成后的思考1.遍历二叉树的过程注意基本c语言语句的书写，此外建立二叉树的时候首先申请一个空间。

最重的是要弄清楚在输入二叉树时结束符，和空字符的位置。