二叉树链式存储结构 第六章实验报告

{ printf("非递归层序遍历二叉树:"); LeverTraverse(T); printf("\n");
} else printf("二叉树为空!\n"); break; default:flag=0;printf("程序运行结束，按任意键退出!\n"); }} } void CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); if(ch==' ') T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode));
else printf("二叉树为空!\n");
break;
case '2':if(T)
2 7/ 来自风行下载 2013 正式版官方下载 金山打字通 2013 官方免费下载 /
文档由酷狗音乐盒 2013 官方免费下载分享
{ printf("递归中序遍历二叉树:"); InOrder(T); printf("\n");
握数据结构的知识和应用,我将为此而继续努力. 总 结 指 导 教 师 意 见
7 7/ 来自风行下载 2013 正式版官方下载 金山打字通 2013 官方免费下载 /
文档由酷狗音乐盒 2013 官方免费下载分享
运 行 结 果
6 7/ 来自风行下载 2013 正式版官方下载 金山打字通 2013 官方免费下载 /
文档由酷狗音乐盒 2013 官方免费下载分享
实 验
通过本次实验,初步掌握了二叉树的存储实现,同时基本掌握了二叉树的遍历思 分 析 想，还掌握了二叉树的常见算法的程序实现。。希望通过今后的学习能更加熟练地掌 与

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

一、二叉树的定义与性质1.1 定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

二、二叉树的遍历2.1 前序遍历前序遍历是指首先访问根节点，然后按照先左后右的顺序遍历左右子树。

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

2.2 中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

2.3 后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

实验名称二叉树的基本操作实验日期实验成绩1、实验目的：1. 掌握二叉树链表的结构和二叉树的建立过程2. 掌握用递归方法实现二叉树遍历的操作2、实验内容：1、编写一个程序实现二叉树的各种运算，并完成如下功能：（1）输出二叉树b；（b为下图所示的二叉树）（2）输出H节点的左、右孩子节点值；（3）输出二叉树b的深度；（4）输出二叉树b的节点个数；（5）输出二叉树b的叶子节点个数；（6）释放二叉树b。

2、编写一个程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归算法。

并以第1题图所示的二叉树b给出求解结果。

3、核心算法或代码片段：代码一：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data;//数据元素struct node *lchild;//指向左孩子struct node *rchild;//指向右孩子} BTNode;void CreateBTNode(BTNode *&b, char *str);void DispBTNode(BTNode *b);BTNode *FindNode(BTNode *b, ElemType x);BTNode *LchildNode(BTNode *p);BTNode *RchildNode(BTNode *p);int BTNodeDepth(BTNode *b);int Nodes(BTNode *b);int LeafNodes(BTNode *b);void DestroyBTNode(BTNode *&b);void CreateBTNode(BTNode *&b, char *str)//由str串创建二叉链{BTNode *St[MaxSize], *p = NULL;int top = -1, k, j = 0;char ch;b = NULL;//建立的二叉树初始时为空ch = str[j];while (ch != '\0')//str未扫描完时循环{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) //p指向二叉树的根节点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)//返回data域为x的节点指针{BTNode *p;if (b == NULL)return NULL;else if (b->data == x)return b;else{p = FindNode(b->lchild, x);if (p != NULL)return p;elsereturn FindNode(b->rchild, x);}}BTNode *LchildNode(BTNode *p)//返回*p节点的左孩子节点指针{return p->lchild;}BTNode *RchildNode(BTNode *p)//返回*p节点的右孩子节点指针{return p->rchild;}int BTNodeDepth(BTNode *b)//求二叉树b的深度{int lchilddep, rchilddep;if (b == NULL)return(0); //空树的高度为0 else{lchilddep = BTNodeDepth(b->lchild);//求左子树的高度为lchilddeprchilddep = BTNodeDepth(b->rchild);//求右子树的高度为rchilddepreturn (lchilddep>rchilddep) ? (lchilddep + 1) : (rchilddep + 1);}}int Nodes(BTNode *b)//求二叉树b的节点个数{int num1, num2;if (b == NULL)return 0;else if (b->lchild == NULL && b->rchild == NULL)return 1;else{num1 = Nodes(b->lchild);num2 = Nodes(b->rchild);return (num1 + num2 + 1);}}int LeafNodes(BTNode *b)//求二叉树b的叶子节点个数{int num1, num2;if (b == NULL)return 0;else if (b->lchild == NULL && b->rchild == NULL)return 1;else{num1 = LeafNodes(b->lchild);num2 = LeafNodes(b->rchild);return (num1 + num2);}}void DestroyBTNode(BTNode *&b) //摧毁树{if (b != NULL){DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);}}int main(){BTNode *b, *p, *lp, *rp;;CreateBTNode(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");printf("二叉树的基本运算如下:\n");printf(" (1)输出二叉树:"); DispBTNode(b); printf("\n");printf(" (2)H节点:");p = FindNode(b, 'H');if (p != NULL){lp = LchildNode(p);if (lp != NULL)printf("左孩子为%c ", lp->data);elseprintf("无左孩子");rp = RchildNode(p);if (rp != NULL)printf("右孩子为%c", rp->data);elseprintf("无右孩子");}printf("\n");printf(" (3)二叉树b的深度:%d\n", BTNodeDepth(b));printf(" (4)二叉树b的节点个数:%d\n", Nodes(b));printf(" (5)二叉树b的叶子节点个数:%d\n", LeafNodes(b));printf(" (6)释放二叉树b\n");DestroyBTNode(b);return 0;}代码二：#include<iostream>#define maxsize 50using namespace std;class node{private:char data;node* lchild;node* rchild;public:void createnode(node *&,char *);//先序遍历void fnode(node* b){if(b!=NULL){cout << b->data ;fnode(b->lchild);fnode(b->rchild);}}//中序遍历void mnode(node* b){if(b!=NULL){mnode(b->lchild);cout << b->data ;mnode(b->rchild);}}//后序遍历void lnode(node* b){if(b!=NULL){lnode(b->lchild);lnode(b->rchild);cout << b->data ;}}void fnode1(node *);void mnode1(node *);void lnode1(node *);void all(node *);};void node::createnode(node* &b,char* a) {node *st[maxsize],*p;int top=-1,k,j=0;char ch;b=NULL;ch=a[j];while(ch!='\0'){switch(ch){case '(':top++;st[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=new node;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=a[j];}}int main(){node *b;char a[]="A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))";b->createnode(b,a);cout << "递归先序编历：";b->fnode(b);cout << endl ;cout << "递归中序编历：";b->mnode(b);cout << endl ;cout << "递归后序编历：";b->lnode(b);cout << endl ;cout << endl ;}一：二:总结体会：在第一个实验对树的操作，利用树广义表的表示法输入一个str，对str进行遍历，通过对括号和字母的判断创建二叉树CreateBTNode()，输出二叉树DispBTNode()同样采用广义表表示法，在找寻某一结点的左右孩子结点首先FindNode()对是否存在左右孩子,由于该二叉树存储采用的二叉链表所以通过指针指向输出左右孩子，在输出二叉树DispBTNode(),找左右孩子FindNode()，计算深度BTNodeDepth(),计算结点数Nodes(),都采用了函数的递归，都是利用左右孩子指针进行操作，进行对整个数的遍历。

实验报告课程名称：数据结构
第 1 页共4 页
五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）
这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。

通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。

在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。

如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。

例如进行二叉树的遍历的时候，要先理解各种遍历的特点。

先序遍历是先遍历根节点，再依次先序遍历左右子树。

中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。

而后序遍历则是先依次后续遍历左右子树，再访问根节点。

掌握了这些，在实验中我们就可以融会贯通，举一反三。

其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。

第 3 页共4 页
第 4 页共4 页。

二叉树的存储与遍历实验题目：二叉树的存储与递归遍历。

实验目的：掌握二叉树的定义、存储及遍历的算法及上机的基本操作。

实验内容与步骤：（1）树结构的基本操作，即操作者使用先序遍历的原理创建一个由多个节点组成的二叉树结构，并使用递归算法按先序、中序、后序对二叉树进行遍历。

（2）程序及部分注释如下：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX(a,b) (a>b?a:b)typedef char TElemType;typedef int Status;//二叉树的二叉链表存储结构typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//先序遍历生成二叉树Status CreatBiTree(BiTree &T){TElemType ch,temp;printf("输入一个元素: ");scanf("%c",&ch);temp=getchar(); //结束回车if(ch==' ') T=NULL; //输入空格表示结点为空树else{if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch; //生成根结点CreatBiTree(T->lchild); //构造左子树CreatBiTree(T->rchild); //构造右子树}return OK;}//打印元素Status PrintElem(TElemType e){printf("%c ",e);return OK;}//先序遍历二叉树Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)) {if(T){ //二叉树不为空时if(Visit(T->data)) //访问根结点if(PreOrderTraverse(T->lchild,Visit)) //先序遍历左子树if(PreOrderTraverse(T->rchild,Visit)) return OK; //先序遍历右子树return ERROR;}else return OK;}//中序遍历二叉树Status InOrderTraverse(BiTree T,Status (* Visit)(TElemType e)) {if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit)) return OK;else return ERROR;}return OK;}//后序遍历二叉树Status PostOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){ if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data)) return OK;else return ERROR;}return OK;}void main(){BiTree T;Status (* Visit)(TElemType);Visit=PrintElem;CreatBiTree(T);printf("\n先序遍历:");PreOrderTraverse(T,Visit);printf("\n中序遍历:");InOrderTraverse(T,Visit);printf("\n后序遍历:");PostOrderTraverse(T,Visit);printf("\n程序结束.\n");}分析与体会：（1）本程序采用的是递归的算法实现了二叉树的三种遍历，相对于非递归的算法较为简单。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：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通过本次实验，我深入理解了二叉树的性质和遍历方式，并掌握了二叉树的基本操作。

数据结构二叉树的实验报告数据结构二叉树的实验报告一、引言数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以便高效地访问和操作。

二叉树是数据结构中常见且重要的一种，它具有良好的灵活性和高效性，被广泛应用于各种领域。

本实验旨在通过实际操作和观察，深入了解二叉树的特性和应用。

二、实验目的1. 理解二叉树的基本概念和特性；2. 掌握二叉树的创建、遍历和查找等基本操作；3. 通过实验验证二叉树的性能和效果。

三、实验过程1. 二叉树的创建在实验中，我们首先需要创建一个二叉树。

通过输入一系列数据，我们可以按照特定的规则构建一棵二叉树。

例如，可以按照从小到大或从大到小的顺序将数据插入到二叉树中，以保证树的有序性。

2. 二叉树的遍历二叉树的遍历是指按照一定的次序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历是先访问根节点，然后再依次遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后再遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的查找二叉树的查找是指在二叉树中寻找指定的节点。

常见的查找方式有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着左子树一直向下搜索，直到找到目标节点或者到达叶子节点；广度优先搜索是从根节点开始，逐层遍历二叉树，直到找到目标节点或者遍历完所有节点。

四、实验结果通过实验，我们可以观察到二叉树的特性和性能。

在创建二叉树时，如果按照有序的方式插入数据，可以得到一棵平衡二叉树，其查找效率较高。

而如果按照无序的方式插入数据，可能得到一棵不平衡的二叉树，其查找效率较低。

在遍历二叉树时，不同的遍历方式会得到不同的结果。

前序遍历可以用于复制一棵二叉树，中序遍历可以用于对二叉树进行排序，后序遍历可以用于释放二叉树的内存。

在查找二叉树时，深度优先搜索和广度优先搜索各有优劣。

深度优先搜索在空间复杂度上较低，但可能会陷入死循环；广度优先搜索在时间复杂度上较低，但需要较大的空间开销。

实验四二叉树的操作班级：计算机1002班姓名：唐自鸿学号：201003010207 完成日期：2010.6.14 题目：对于给定的一二叉树，实现各种约定的遍历。

一、实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。

三、实验步骤：(一) 需求分析1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。

因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。

二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。

2．程序的执行命令为：1）构造结点类型，然后创建二叉树。

2）根据提示，从键盘输入各个结点。

3）通过选择一种方式（先序、中序或者后序）遍历。

4）输出结果，结束。

(二)概要设计1.二叉树的二叉链表结点存储类型定义typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BitNode,*BitTree;2.建立如下图所示二叉树：void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点。

3.本程序包含四个模块1) 主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块4.模块调用关系：主程序模块（三）详细设计1.建立二叉树存储类型//==========构造二叉树=======void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点//{char ch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));//申请一段关于该节点类型的存储空间(*bt)->data=ch; //生成根结点CreatBiTree(&((*bt)->LChild)); //构造左子树CreatBiTree(&((*bt)->RChild)); //构造右子树}}2. 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1）先序遍历二叉树的递归算法如下：void PreOrder(BitTree root){if (root!=NULL){Visit(root ->data);PreOrder(root ->LChild); //递归调用核心PreOrder(root ->RChild);}}2）中序遍历二叉树的递归算法如下：void InOrder(BitTree root){if (root!=NULL){InOrder(root ->LChild);Visit(root ->data);InOrder(root ->RChild);}}3）后序遍历二叉树的递归算法如下：void PostOrder(BitTree root){if(root!=NULL){PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);}}4）计算二叉树的深度算法如下：int PostTreeDepth(BitTree bt) //求二叉树的深度{int hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild); //求左子树的深度hr=PostTreeDepth(bt->RChild); //求右子树的深度max=hl>hr?hl:hr; //得到左、右子树深度较大者return(max+1); //返回树的深度}else return(0); //如果是空树，则返回0}四、调试分析及测试结果1. 进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。

{
PreOrderTraverse((*T).Rchild,Visit);
}
}
s.cpp
#include"h.h"
void main()
{
BiTree T;
CreateBiTree(&T);
PreOrderTraverse(&T,Visit);
printf("\n");
InOrderTraverse(&T,Visit);
CreateBiTree((*T).Rchild);//构造右子树
}
}
void PreOrderTraverse(BiTree *T,void (*Visit)(ElemType e))
//先序遍历二叉树T的递归算法，对每个节点调用Visit函数访问；
//采用二叉链表表示的存储结构，Visit是节点访问函数。
{
Visit((*T).data);
if((*T).Lchild!=NULL)
{
PreOrderTraverse((*T).Lchild,Visit);
}
if((*T).Rchild!=NULL)
{
PreOrderTraverse((*T).Rchild,Visit);
}
}
void InOrderTraverse(BiTree *T,void (*Visit)(ElemType e))
三、实验内容与步骤
二叉树的二叉链表存储，实现先序遍历二叉树。
h.h
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构实验六报告第一篇：数据结构实验六报告实验六报告课程名称：数据结构实验名称：二叉树的应用实验日期2011/11/23一、实验目的：掌握赫夫曼二叉树的建立及赫夫曼编码的生成。

二、实验内容与要求：根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。

三、数据结构设计顺序表的存储结构，建立了二叉树的关系Struct HTNode{int weight;unsigned int parent,lchild,rchild;};四、算法设计1、从数据中选择较小的两个数据元素void Select(HTNode *HT, const int n, int &a, int &b){ //选择较小的两个元素} int x,y;x=y=0x7fff;for(int j=0;jif(HT[j].parent==0)if(HT[j].weight2、建立赫夫曼树void CreatHuff(HTNode *HT,int *p,const int n){} int m=2*n-1;int i,a,b;for(i=0;iSelect(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=H T[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}3、生成赫夫曼编码void HuffCoding(HTNode *HT, Huffcode &HC, const int n){ //}HC=newchar*[n+1];char *code=new char[n];code[n-1]='';int i,j,p,k;for(i=0;i} delete[] code;j=n-1;k=i;while(HT[k].parent){p=HT[k].parent;if(HT[p].lchild==k)code[--j]='0';else code[--j]='1';k=p;} HC[i]=(char*)malloc((n-j)*sizeof(char));HC[i]=new char[n-j];strcpy(HC[i],&code[j]);五、测试结果测试数据一：测试数据二：六、心得体会这次实验是在前面的实验基础之上，加上只用了顺序表的存储结构，所以比较简单。

S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
cout<<p->data<<" ";
S.push(p->rchild);
}}
}
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
#include <queue>
#include <stack>
#include <malloc.h>
#defineSIZE 100
using namespace std;
typedef struct BiTNode
{char data;
struct BiTNode *lchild,*rchild;
break;
default:flag=0;printf("程序运行结束,按任意键退出!\n");
}}
}
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{ T=(BiTNode *)malloc(sizeof(BiTNode));
PreOrder_Nonrecursive(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;

实验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.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

实验报告实验题目二叉树需求分析程序的功能从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。

输入的形式ABCффDEфGффFффф（其中ф表示空格字符）输出的形式先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA概要设计给出所用抽象数据类型的逻辑定义CreateTree(&bt); //创建二叉树PreOrder(bt); //先序遍历InOrder(bt); //中序遍历PostOrder(bt); //后序遍历画出主程序的流程框图画出各模块之间的调用关系图。

Main()Preorder() InOrder() PastOrder()详细设计（1）确定存储结构，并给出所用抽象数据类型的数据结构定义void PreOrder(BiTree root){if(root!=NULL){printf("%c",root->data);PreOrder(root->Lchild);PreOrder(root->Rchild);}}void InOrder(BiTree root){if(root!=NULL){ InOrder(root->Lchild );printf("%c",root->data);InOrder(root->Rchild);}}void PostOrder(BiTree root){if(root!=NULL){ PostOrder(root->Lchild);PostOrder(root->Rchild);printf("%c",root->data);}}给出主程序的伪码算法Main(){创建二叉树先序遍历中序遍历后序遍历}调试分析核心算法改进设想使用非递归算法测试结果列出典型输入及对应的输出结果。

《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

2) 输出树的深度，最大元，最小元。

二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。

递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。

直到递归全部结束。

下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。

具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。

再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。

具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。

如此循环直至结点指针和栈均为空，遍历结束。

最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。

二叉树实验报告1 实验目的1、熟悉二叉树的二叉链表存储结构；2、掌握构造二叉树的方法；3、加深对二叉树前序、中序、后序遍历的理解。

2 需求分析2.1 任务1二叉树的二叉链表存储结构及实现，将参考程序中的三段函数代码补齐。

约束条件：沿用源代码中链表结构体。

输入要求：输入一个二叉树链表。

输出要求：若是二叉树链表不为空则对二叉树链表进行先序遍历。

2.2 任务2功能：int HeightBTree(BTNode *bt) 求二叉树的深度。

约束条件：沿用源代码中链表结构体。

输入要求：输入一个二叉树链表。

输出要求：若是二叉树链表为空则返回0，若二叉树链表不为空则统计出该二叉树的深度，然后返回该值。

2.3 任务3功能：void DisplayBTree(BTNode * bt，int i) 输出二叉树第i层的所有节点。

约束条件：沿用源代码中链表结构体。

输入要求：输入一个二叉树链表。

输出要求：若输入的i小于1，或者二叉树链表为空则直接返回，若二叉树链表不为空且i值符合要求，则打印i层所有的节点。

3概要设计3.1任务1void PreOrder(BTNode *bt)该函数首先，你需要定义一个二叉树节点的数据结构，通常包含一个值和两个指向左右子节点的指针。

在先序遍历函数中，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

并在控制台上输出每个节点的值。

void InOrder(BTNode *bt) 该函数首先判断当前节点是否为空，如果为空则返回。

递归遍历左子树。

访问当前节点，输出节点的值。

递归遍历右子树。

通过这样的递归过程，我们可以实现对整个二叉树的中序遍历。

void PostOrder(BTNode *bt)该函数首先判断当前节点是否为空，如果为空则返回。

递归遍历左子树。

递归遍历右子树。

访问当前节点，输出节点的值。

通过这样的递归过程，我们可以实现对整个二叉树的后序遍历。

3.2任务2int HeightBTree(BTNode *bt)该函数首先判断当前节点是否为空，如果为空则返回0。

二叉树实验报告总结(共10篇)二叉树实验报告实验报告课程名称算法与数据结构专业学号姓名实验日期算法与数据结构实验报告一、实验目的1.了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法2.了解二叉树遍历的概念，掌握遍历二叉的算法3.进一步掌握树的结构及非线性特点，递归特点和动态性。

二、实验内容二叉树的实现和运算三、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．分析算法，并简要给出算法设计小结和心得。

四、算法步骤用户以三元组形式输入二叉树的结点元素及其位置关系，建立二叉树，并打印输出该二叉树。

用户输入选择结点，程序调用BiTNode* Find Node(char tag, BiTNode* node)函数，返回子树的根结点，然后调用BiTreeDepth(BiTree T)函数，求出子树的深度，并输出该值。

3.用户可以选择是否继续执行程序，若继续，则输入1，否则输入0，结束程序。

五、主程序代码：int main(void){BiTree T;TElemType e1;char node; // node为用户选择输入的结点//int b,choose; // b为以选定结点为子树的深度，choose为实现多次选择输入的标志//BiTNode* a; // a为选定结点为子树的根结点//choose=1; // 多次选择的标志，当choose为1时运行程序，为0时结束程序// InitBiTree(T);printf(构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n,BiTreeEmpty(T),BiTreeDepth(T));e1 = Root(T);if(e1 != Nil)#ifdef CHARprintf(二叉树的根为: %c\n,e1);#endif#ifdef INTprintf(二叉树的根为: %d\n,e1);#endifelseprintf(树空，无根\n); //三元组构建二叉树striile(x!=end){AddNode(T, x[0], x[1], x[2]);GetUserWord(x);} //输出树PrintTreeLevel( T );//以三元组形式输入任意二叉树（以大写字母表示结点），求以任意一选定结点为子树的深度。