实验5 二叉树与最优二叉树
一、实验要求
1、了解树和二叉树的特性，以及它们在实际问题中的应用。
2、掌握树和二叉树的实现方法以及它们的基本操作，学会运用树和二叉树来解决问题。
二、实验题目
1、用菜单驱动的手法，编写一个完整的程序，生成一棵二叉树，求二叉树的高度，求二叉树的叶子结点数，输出二叉树的所有结点。
2、编写一个完整的程序实现，利用哈夫曼算法建立哈夫曼树,并输出这棵树中所有结点数据。
三、算法描述
二叉树：一般常用的是动态链式存储，这时一般不用担心空间溢出问题，也不必关心存储管理的细节(由系统完成)，这使我们能用更多的精力去考虑其他问题。在此用动态链表存储二叉树。
二叉链表是二叉树最常用的存储结构，其中每个结点除了存储结点本身的数据外，还设置两个指针域Ichild 和 rchild ，分别指向该结点的左孩子和右孩子。这是二叉树链式存储的二指针形式。就像单链表由头指针惟一确定一样，一个二义链表也由指向根结点的根指针惟一确定。为了某些运算的方便，也可给二义链表增加头结点（但一般并没有这样做）。
二叉树的生成是指如何在内存中建立二叉树的存储结构。建立顺序存储结构的问题较简单，这里仅讨论如何建立二叉链表。要建立二叉链表，就需要按照某种方式输人二叉树的结点及其逻辑信息。注意到对二叉树遍历时，不仅得到了结点信息，而且由序列中结点的先后关系还可获得一定的逻辑信息，如果这些信息足够，就可根据遍历序列生成相应的二叉树
二叉树的生成方法就是基于遍历序列的，相当于遍历问题的逆问题，即由遍历序列反求二叉树，这需要分析和利用二叉树遍历序列的特点。
哈夫曼算法（最优二叉树）：在许多应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。结点到树根之间的路径长度与该结点权的乘积称为该结点的带权路径长度。树的（外部）带权路径长度（Weighted Path Length ），定义为树中所有叶于结点的带权路径长度之和，通常记为： WPL ＝
i n
i i l w ∑=1
其中，n表示子结点的数目，w和分别表示叶结点i的权值和它到根之间的路径长度。在权为w1，w2，…，w n的n个叶结点的所有二叉树中，带权路径长度WPL最小的二叉树.
（1）首先，根据给定的n个权值w1，w2，…，w n构造含有n棵二叉树的森林F＝{T1；，T2，…，T n}，其中每棵二叉树T i中只有一个权值为W i的根结点，没有左右子树。
（2）在森林F中选出两棵根结点权值最小的树（当这样的树不止两棵树时，可从中任
选两棵），将这两棵树合并成一棵新的二叉树。这时会增加一个新的根结点，它的权取为原来两棵树的根的权值之和，而原来的两棵树就作为它的左右子树（谁左，谁右无关紧要）。
（3）对新的森林F重复（2），直到森林F中只剩下一棵树为止。这棵树便是哈大曼树。
由算法知，哈夫曼树不一定惟一（但WPL是相同的，并且都为最小）。原因在于每次合并时，原两棵树谁左谁右、以及候选的两棵树有多个时选哪两个等。
在哈夫曼算法中，初始森林共有n棵二叉树，每棵树中仅有一个结点，它们既是根，又是叶子。算法的第二步是将当前森林中的两棵根结点权值最小的二叉树合并成一棵新二叉树。每合并一次，森林中就减少一棵树。显然，要进行n—l次合并，才能使森林中二叉树的数目由n棵减少到只剩一棵，即最终的哈夫曼树。
另外，每合并一次都要产生一个新结点，合并n- l次共产生n- l个新结点。由此可知，最终求得的哈大曼树中共有n＋（n—l）＝2n—1个结点，其中的叶结点就是初始森林中的n个孤立结点。
在哈夫曼树中，每个分支结点都是合并过程中产生的，它们的度为2，所以树中没有度为1的分支结点。
四、程序清单
#include
#include
#include
#define M 200
#define null 0
#define n 8 //叶子结点数，假设为20 #define m 15 //结点总数
#define max 1000
typedef char Etype; /*定义数据类型*/ typedef struct BiTNode/*定义结点类型*/ { Etype data;
struct BiTNode *lch,*rch;/*左右子树*/ }BiTNode,*BiTree;
BiTree que[M];
int front=0,rear=0;
int count=0;
BiTNode *t,*p;
typedef int datatype;
typedef struct
{ float weight;
int parent,lchild,rchild;
}hftree; //结点类型
hftree tree[m+1],tree2[m+1]; //哈夫曼树类型，数组从0号单元开始使用//哈夫曼树向量
/*建立二叉树（层次法）*/
BiTNode *creat_bt1()
{BiTNode *t,*p,*v[20];int i,j; Etype e;
printf("输入二叉树各结点的编号和对应的值(用空格隔开)：");
scanf("%d %c",&i,&e);
while(i!=-1)
{ p=(BiTNode
*)malloc(sizeof(BiTNode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else{ j=i/2;
if(i%2==0)v[j]->lch=p;
else v[j]->rch=p;
}
printf("输入二叉树各结点的编号和对应的值(输入i为-1时结束)：");
scanf("%d %c",&i,&e);
}
return(t);
}
//先根法建立二叉树
BiTNode *creat_bt2()
{ BiTNode *t;
char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch=='@')
return null;
else
{ t=(BiTNode
*)malloc(sizeof(BiTNode));
t->data=ch;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return t;
}
void huffman(hftree tree[])
{ int i,j,p1,p2,kz,ky,exchange; //p1,p2记当前选的权值最小的两棵树根结点在向量T 中的下标
float sm1,sm2;
for(i=1;i<=n;i++)
{ //初始化, 根结点（叶子）的双亲和左、右孩子指针置为-1
tree[i].parent=0;
tree[i].lchild = tree[i].rchild=0;
tree[i].weight=0.0;
}
printf("Hello huffman!\n");
printf("\t请输入%d个叶子结点的权值：\n",n);
for(i=1;i<=n;i++) //输入n个叶子的权值
{ scanf ("%f",&tree[i].weight);}
for(i=1;i<=n;i++)
printf("%2.2f ",tree[i].weight);
printf("\n\n");
for(i=n+1;i<=m;i++) //第i次合并, 产生第i棵新树(结点).共进行n－l次合并。{ p1=p2=0; //此句可不要
sm1=sm2=max; //max为float型的最大值,它大于所有结点权值
for (j=1;j<=i-1;j++) //从第0~i-1棵树中找两个权值最小的根结点，
//作为第i个生成的新树
{ if (tree[j].parent != 0) continue;//不考虑已合并的点,双亲域不为-1时就不是根
if (tree[j].weight { sm2=sm1; //sm1中记当前找到的最小者权值,sm2记次小者权值 sm1= tree[j].weight; p2=p1; //p1中记当前找到的权值最小者结点的下标, // p2记当前权值次小者结点的下标 p1= j; } else if(tree[j].weight { sm2=tree[j].weight; // sm2记次小权值 p2 = j; } // p2记次小权值结点在数组中的下标 } tree[p1].parent=tree[p2].parent = i; //对当前被找到的的两棵根权值最小树进行合并 //使这两个结点p1,p2的双亲在数组中的下标为i, tree[i].parent=0; //新根的双亲为-1,它没有双亲 tree[i].lchild = p1; //修改新根结点的左孩子在向量中的下标为p1 tree[i].rchild=p2; //修改新根结点的右孩子在向量中的下标为p2 tree[i].weight=sm1+sm2;//修改新根结点权值为其左右孩子的权值之和 } } //打印哈夫曼树 void printhuffman(hftree tree[]) { int i,k; printf("\t哈夫曼树为(输出中：冒号前是所存结点值的下标冒号后是结点的值)：\n\n"); printf("结点序号双亲结点左子树右子树权值\n"); for(i=m;i>0;i--) { printf("%4d",i); printf("%10d: ",tree[i].parent); k=tree[i].parent; printf("%5.2f",tree[k].weight); printf("%10d: ",tree[i].lchild); k=tree[i].lchild; printf("%5.2f",tree[k].weight); printf("%10d: ",tree[i].rchild); k=tree[i].rchild; printf("%5.2f",tree[k].weight); printf("%10.2f\n",tree[i].weight); } printf("Print end！\n\n"); } void preorder(BiTNode *p )/*先序遍历二叉树*/ { if(p) { printf("%c ",p->data); preorder(p->lch); preorder(p->rch); } } void inorder(BiTNode *p) /*中序遍历*/ { if(p) { inorder(p->lch); printf("%c ",p->data); inorder(p->rch); } } void postorder(BiTNode *p) /*后序遍历*/ { if(p) { postorder(p->lch); postorder(p->rch); printf("%c ",p->data); } } void enqueue(BiTree T) { if(front!=(rear+1)%M) { rear=(rear+1)%M; que[rear]=T; } } BiTree delqueue() { if(front==rear)return NULL; front=(front+1)%M; return (que[front]); } void levorder(BiTree T)/*层次遍历二叉树*/ { BiTree p; if(T) { enqueue(T); while(front!=rear) { p=delqueue(); printf("%c ",p->data); if(p->lch!=NULL)enqueue(p->lch); if(p->rch!=NULL)enqueue(p->rch); } } } int treedepth(BiTree bt)/*二叉树高度*/ { int hl,hr,max1; if(bt!=NULL) { hl=treedepth(bt->lch); hr=treedepth(bt->rch); max1=(hl>hr)? hl:hr; return(max1+1); } else return(0); } void prtbtree(BiTree bt,int level)/*打印*/ { int j; if(bt) { prtbtree(bt->rch,level+1); printf("%d\n",bt->data); prtbtree(bt->lch,level+1); } } void exchange(BiTree bt)/*交换二叉树左右子树*/ { BiTree p; if(bt) { p=bt-> lch;bt->lch=bt->rch;bt->rch=p; exchange(bt->lch);exchange(bt->rch); } } int leafcount(BiTree bt) /*叶子结点数*/ { if(bt!=NULL) { leafcount(bt->lch); leafcount(bt->rch); if((bt->lch==NULL)&&(bt->rch==NUL L)) count++; } return(count); } void paintleaf(BiTree bt)/*叶子结点值*/ { if(bt!=NULL) { if(bt->lch==NULL&&bt->rch==NULL) printf("%d ",bt->data); paintleaf(bt->lch); paintleaf(bt->rch); } } void print_menu() { printf("-------------主菜单---------------"); printf("\n 1.建立二叉树(层次发)"); printf("\n 2.建立二叉树（先根法）"); printf("\n 3.先序递归遍历二叉树"); printf("\n 4.中序递归遍历二叉树"); printf("\n 5.后序递归遍历二叉树"); printf("\n 6.层次遍历二叉树"); printf("\n 7.计算二叉树的高度和叶子结点个数"); printf("\n 8.建立哈夫曼树"); printf("\n 9.打印哈夫曼树"); printf("\n 0.打印二叉树"); printf("\n E.结束程序运行"); printf("\n--------------------------------"); printf("\n 请选择：\n"); } char chioce_menu() { char ch; for(;;) { scanf("%c",&ch); if(ch<'0'||ch>'E') printf("输入错误，重新选择：\n"); else break; } return ch; } main() { char x; do { print_menu(); switch(chioce_menu()) { case '1':t=creat_bt1();break; /*建立二叉树算法*/ case '2': { printf("\t先根遍历建立二叉树：\n"); printf("\t请输入二叉树结点的值！\n"); printf("可以输那个值均为字母或'@'(n<100)字符间以回车换行，想结束时输多个'@':\n"); t=creat_bt2(); }break; case '3':if(t) { printf("先序遍历二叉树:"); preorder(t); printf("\n"); } else printf("该二叉树为空!\n"); break; case '4':if(t) { printf("中序遍历二叉树:"); inorder(t); printf("\n"); } else printf("该二叉树为空!\n"); break; case '5':if(t) { printf("后序遍历二叉树:"); postorder(t); printf("\n"); } else printf("该二叉树为空!\n"); break; case '6':if(t) { printf("层次遍历二叉树:"); levorder(t); printf("\n"); } else printf("该二叉树为空!\n"); break; case '7':if(t) { printf("二叉树的高度为:%d\n",treedepth(t)); printf("二叉树的叶子结点数为:%d\n",leafcount(t)); printf("二叉树的叶子结点为:");paintleaf(t); printf("\n"); } else { printf("该二叉树为空!\n"); printf("该二叉树为空!\n"); } break; case '8':huffman(tree);break; //建立哈夫曼树 case '9':printhuffman(tree);break; case '0':if(t) { prtbtree(t,0); printf("\n"); } else printf("该二叉树为空!\n"); break; case 'E':exit(0); } }while((x!='1')||(x!='2')||(x!='3') ||(x!='4')||(x!='5')||(x!='6') ||(x!='7')||(x!='8')||(x!='8') ||(x!='9')||(x!='0')||(x!='E')); printf("输入错误，请重新运行程序\n"); } 五、运行结果 略 六、调试小结 1、本程序应用了先根序列建立二叉树、按完全二叉树的层次顺序，依次输入结点信息来建立二叉链表、先序递归遍历二叉树、中序递归遍历二叉树、.后序递归遍历二叉树、层次遍历二叉树及建立哈夫曼树、打印哈夫曼树等一系列的算法。 2、算法复杂度分析：本程序所有的算法时间复杂度都为O（n）。 3、递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。一般出现需要对话框，说什么发送错误报告的时候有两种可能，一是数组越界，二是指针没有赋值。 4、自己在追求程序的完善性和美观性，觉得很好，但是由于能力水平有限，有些东西还是不能很好的实现 09082229 刘增鹏 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 1.需求分析 1．建立平衡二叉树并进行创建、查找、插入、删除等功能。 2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。 3．测试数据：自选数据 2.概要设计 1.抽象数据类型定义： typedef struct BSTNode { int data; int bf; //节点的平衡因子 struct BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; void CreatBST(BSTree &T); //创建平衡二叉树 void R_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理 void L_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理 void LeftBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree &T,int e,bool &taller); //插入结点e bool SearchBST(BSTree &T,int key); //查找元素key是否在树T中 void LeftBalance_div(BSTree &p,int &shorter); //删除结点时左平衡旋转处理 void RightBalance_div(BSTree &p,int &shorter); //删除结点时右平衡旋转处理 void Delete(BSTree q,BSTree &r,int &shorter); //删除结点 int DeleteA VL(BSTree &p,int x,int &shorter); //平衡二叉树的删除操作 void PrintBST(BSTree T,int m); //按树状打印输出二叉树的元素 2.主程序的流程 3.各模块之间的层次调用 实验题目：实验九——二叉树实验 算法设计（3） 问题分析： 1、题目要求：编写算法交换二叉树中所有结点的左右子树 2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据： A、输入：1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历：4 2 5 1 3 交换后中序遍历：3 1 5 2 4 交换前：交换后： B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历：11 7 17 18 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ①主函数main（） ②先序遍历二叉树建立函数creat_bt（） ③中序遍历二叉树函数inorder（） ④左右子树交换函数 exchange（） 各函数间关系如下： 详细设计： 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据； 判断是否为0{ 若是，为空； 不是，递归；} 返回二叉树； } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否，交换左右子树； 递归；} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } main （） creat_bt （） inorder （） exchange （） 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); } 平衡二叉树操作的演示 1.需求分析 本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能： （1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更 新平衡二叉树的显示。 （2）平衡二叉树的显示采用凹入表现形式。 （3）合并两棵平衡二叉树。 （4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。 如下图： 2．概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的关系，进行相应的旋转，使之成为新的平衡子树。 具体步骤： （1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点； （2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； （3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。 流程图 3.详细设计 二叉树类型定义： typedefint Status; typedefintElemType; typedefstructBSTNode{ 二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) 实习报告 一、需求分析 1、问题描述 利用平衡二叉树实现一个动态查找表。 （1）实现动态查找表的三种基本功能：查找、插入和删除。 （2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡二叉树的显示。 （3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。 （4）平衡二叉树的显示采用图形界面画出图形。 2、系统功能 打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。 3、程序中执行的命令包括： （1）(L)oad from data file //在平衡的二叉树中插入关键字； （2）(A)ppend new record //在平衡的二叉树中查找关键字； （3）(U)pate special record //显示调整过的平衡二叉树； （4）(D)elete special record //删除平衡二叉树中的关键字； （5）(Q)uit //结束。 4、测试数据： 平衡二叉树为： 图 1 插入关键字10之前的平衡二叉树 插入关键字：10； 调整后： 图 2 插入关键字10之后的平衡二叉树 删除关键字：14； 调整后： 图 3 删除关键字14后的平衡二叉树查找关键字：11； 输出：The data is here! 图 3 查找关键字11后的平衡二叉树 二、概要设计 本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。 1、动态查找表的抽象数据类型定义为： ADT DynamicSearchTable {数据对象D ：D是具有相同特性的数据元素的集合。各个数据元素均含 有类型相同，可唯一标识数据元素的关键字。 数据关系R ：数据元素同属于一个集合。 基本操作P ： InitDSTable(&ST); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件：动态查找表DT存在。 操作结果：销毁动态查找表DT。 SearchDSTable(DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给丁值。 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为 该元素的值或在表中的位置，否则为“空”。 InsertDSTable(&DT,e); 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e，key的数据元素，则插入 e到DT； DeleteDSTable(&DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 }ADT DynamicSearchTable 2、二叉树抽象数据类型的定义为： ADT BinaryTree 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include 实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include 数据结构 实 验 报 告 实验名称：平衡二叉树 1.实验目的和内容 根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。 二叉树的基本功能： 1、平衡二叉树的建立 2、平衡二叉树的查找 3、平衡二叉树的插入 4、平衡二叉树的删除 5、平衡二叉树的销毁 6、其他：自定义操作 编写测试main()函数测试平衡二叉树的正确性。 2. 程序分析 2.1 存储结构 struct node { int key; //值 int height; //这个结点的父节点在这枝最长路径上的结点个数 node *left; //左孩子指针 node *right; //右孩子指针 node(int k){ key = k; left = right = 0; height = 1; } //构造函数}; 2.2 程序流程 2.3 关键算法分析（由于函数过多，在此只挑选部分重要函数） 算法1：void AVL_Tree::left_rotate(node *&x) [1] 算法功能：对 R-R型进行调整 [2] 算法基本思想：将结点右孩子进行逆时针旋转 [3] 算法空间、时间复杂度分析：都为0（1） [4] 代码逻辑 node *y = x->right; y为x的右孩子 x->right = y->left; 将y的左孩子赋给x的右孩子 y->left = x; x变为y的左孩子 fixheight(x); 修正x，y的height值 fixheight(y); x = y; 使x的父节点指向y 算法2：void A VL_Tree::right_rotate(node *&x) [1] 算法功能：对L-L型进行调整 [2] 算法基本思想：将左孩子进行顺时针旋转 [3] 算法空间、时间复杂度分析：都为0（1） [4] 代码逻辑 node *y = x->left; //y为x的左孩子 x->left = y->right; y的右孩子赋给x的左孩子 二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include 重庆交通大学综合性设计性实验报告 姓名姚远学号 631106060113 班级：计信息一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 407机房 指导教师：鲁云平 实验完成时间： 2013 年 5 月 10 日 一、实验目的 1. 建立二叉树 2. 计算结点所在的层次 3.统计结点数量和叶结点数量 4.计算二叉树的高度 5.计算结点的度 6.找结点的双亲和子女 7.二叉树的遍历 8.二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 VISUAL C++软件 四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的应用 ㈡设计的主要思路 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，出度为2的结点数为n2，则n0 =n2 + 1。 ㈢主要功能 实现二叉树的各项操作。 五、主要代码 #include 数学与计算机科学学院数据结构程序设计报告 平衡二叉树 学生姓名: 学号: 班级: 指导老师: 报告日期: 1.题目与要求 1). 问题的提出 编写已个平衡二叉树，主要是对插入一个元素导致树不平衡的情况进行平衡化处理以及相关的处理。 2）设计的知识点 队列的插入，删除，二叉树的建立于销毁，平衡树的平衡化，以及C语言中基础应用于结构等。 3）功能要求 (1).通过不断插入的方式创建一棵平衡二叉树，包括输入结点的关键字和相关信息。 (2)按要求输出创建的平衡二叉树结点，包括顺序（中序）输出和按层次输出。 (3)插入新增的结点，若结点不存在则插入平衡二叉树，并进行相关调整。 (4)销毁二叉树。 (5)退出 菜单界面如下： 2.功能设计 算法设计 选择创建平衡二叉树后，利用循环不断插入结点，并进行调整，当输入节点为0时停止进入菜单界面。 在平横二叉树排序树BSTree上插入一个新的数据元素ｅ的递归算法可如下描述： （１）若BSTree为空树，则插入一个数据元素为e的新结点作为BSTree的根结点，树的深度增1； （２）若e的关键字和BSTree的根节点的关键字相等，则不进行插入； （３）若e的关键字小于BSTree的根结点的关键字，而且在其左子树中不存在和e形同的关键字的结点，则将e插入在其左子树 上，并且当插入之后的左子树的深度加1时，分别就下列不同 情况处理之： a.BSTree的跟结点的平衡因子为-1（右子树的深度大于左子树 的深度）：则将跟结点的平衡因子更改为0，BBST的深度不 变； b.BBST的根结点的平衡因子为0（左，右子树的深度相等）： 则将根结点的平衡因子更改为1，BBST的深度增1； c.BBST的根结点的平衡因子为1（左子树的深度大于右子树 的深度）：若BBST的左子树根结点的平衡因子为1，则需进 行向左旋平衡处理，并且在右旋之后，将根节点和其右子树 根节点的平衡因子更改为0，树的深度不变； 若BBST的左子树根结点的平衡因子为-1，则需进行向左，向 右的双向旋转平衡处理，并且在旋转处理之后，修改根结点 和其左右子树的平衡因子，数的深度不变； （４）若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同的关键字的的节点，则将e插入在 BBST的右子树上，并且当插入之后的右子树深度增加（+1） 时，分别就不同情况处理之。 3.详细设计 1）结点类型定义： typedef struct ElemType{ KeyType Key; //键值类型 char info[20]; }ElemType; Typedef struct BSTNode{ ElemType data； int bf ; //结点的平衡因子 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; }; ************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">); 二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 Visual C++ 三、需求分析 1、建立一棵用二叉链表方式存储的二叉树。 2、从键盘接受扩展先序序列，以二叉链表作为存储结构。 3、建立二叉树，并将遍历结果打印输出。采用递归和非递归两种 方法实现。 四、设计概要 //——————二叉树的二叉链表存储表示—————— typedef struct BiTBode{ TElemType data; Struct BiTNode *lchild, *rchild //左右孩子指针 }BiTNode, *BiTree; //—————基本操作的函数原型说明———————— Status CreateBiTree(BiTree &T); //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉树链表表示的二叉树T。 Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //先序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //后序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 —————先序遍历二叉树基本操作的递归算法———— Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){ //采用二叉链表存储结构，visit是对数据元素操作的应用函数， 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 1、isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。 2、isEmpty函数：根结点为空则为空树。 3、Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。 4、LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。 5、DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。 6、PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。 7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。 8、CreateTree函数：采用先序遍历序列构造二叉树，设‘0’为空结点，输入非‘0’数，生成新结点，递归创建左子树和右子树。 9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在 二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图 三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 广工数据结构实验报告记录平衡二叉树 ————————————————————————————————作者：————————————————————————————————日期： 实验报告 课程名称数据结构实验学院计算机学院专业班级计科9班 学号 学生姓名 指导教师苏庆 2015年 7 月6 日 1.题目:平衡二叉树 ADT BBSTree{ 数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ 问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include 数据结构程序报告(平衡二叉树的操作)
二叉树实验报告
数据结构二叉树实验报告
大数据结构 平衡二叉树的操作演示
二叉树的建立和遍历的实验报告doc
实验报告平衡二叉树
实验四 二叉树的遍历和应用04
实验八：二叉树的遍历与应用
北邮数据结构平衡二叉树报告概论
二叉树的遍历算法实验报告
二叉树实验报告及代码
数据结构程序设计报告(平衡二叉树)(内容清晰)
数据结构实验二叉树的遍历
二叉树实验报告
二叉树实验报告
二叉树的遍历实验报告
数据结构实验三——二叉树基本操作及运算实验报告
数据结构实验报告—二叉树
广工数据结构实验报告记录平衡二叉树
数据结构二叉树遍历实验报告
相关主题
文本预览