姓名学号
序#include"DataStructure_BinaryTree.h"//数据结构第六章树与二叉树函数的定义及声明using namespace std;
int main(void)
{
system("title 数据结构实验实验四：树和二叉树及其应用（I） "); //设置cmd窗口标题 system("color F1"); //设置控制台窗口的背景色和前景色
system("date /T"); //输出当前的日期
print();
cout << "实验内容一：树的遍历" << endl;
BiTree T;
int num = 0;
cout << " 二叉树的建立：" << endl;
cout << " 输入二叉树数据：";
GreateBiTree(T); //先序建立二叉树
cout << " 二叉树的遍历" << endl << " 【递归遍历】 ";
cout << endl << "> 先序遍历：";
PreOrderTraverse(T, PrintElement); //先序遍历二叉树
cout << endl << "> 中序遍历：";
InOrderTraverse(T, PrintElement); //中序遍历二叉树
cout << endl << "> 后序遍历：";
PostOrderTraverse(T, PrintElement); //后序遍历二叉树
cout << endl << "> 层序遍历：" << endl;
LevelOrderTraverse(T, PrintElement); //层序遍历二叉树
cout << endl<< " 【非递归遍历】";
cout << endl << "> 先序遍历：";
PreOrderTraverseNonRec(T, PrintElement); //先序遍历二叉树
cout << endl << "> 中序遍历：";
InOrderTraverseNonRec(T, PrintElement); //中序遍历二叉树
cout << endl << "> 后序遍历：";
PostOrderTraverseNonRec(T, PrintElement); //后序遍历二叉树
cout << endl << "> 层序遍历：";
LevelOrderTraverseNonRec(T, PrintElement);//层序遍历二叉树
print();
cout << endl << "实验内容二：二叉树的基本操作";
cout << endl << "<1> 二叉树的深度：" << BiTDepth(T) << endl;
LeafTNodeNum(T, num);
cout << "<2> 二叉树中叶子结点的数目：" << num << endl;
cout << "<3> 交换左右子树：" << endl;
ExchangeBiTree(T);
cout << " 交换后的二叉树：" << endl;
LevelOrderTraverse(T, PrintElement); //层序遍历二叉树
BiTree root;
TElemType x;
int depth;
cout << "<4> 查找指定节点的根子树：" << endl << " 请输入需要查找的根节点：x = ";
cin >> x;
PreOrderLocate(T, x, root); //先序查找以元素值为x的结点为子树，并以root指向其根子树cout << " 以元素x为根节点的根子树：" << endl;
LevelOrderTraverse(root, PrintElement); //层序遍历二叉树
ChildBiTreeDepth(T, x, depth);
cout << "<5> 查找指定节点的根子树的深度：" << endl << " 以元素x为根节点的根子树的深度：" << depth << endl;
cout << "<6> 判断根子树是否为完全二叉树：" << endl;
if (CompleteBiTree(root))
cout << " 以元素x为根节点的根子树是完全二叉树" << endl;
else
cout << " 以元素x为根节点的根子树不是完全二叉树" << endl;
DelChildBiTree(T, x);
cout << "<7> 删除二叉树：" << endl;
cout << " 删除以元素x为根节点的根子树后的二叉树：" << endl;
LevelOrderTraverse(T, PrintElement); //层序遍历二叉树
if (CompleteBiTree(T))
cout << " 删除以元素x为根子树后的二叉树是完全二叉树" << endl;
else
cout << " 删除以元素x为根子树后的二叉树不是完全二叉树" << endl;
DestoryBiTree(T); //销毁二叉链表T
DestoryBiTree(root); //销毁二叉树root
return 0;
}
2.头文件”ADT.h”的部分程序如下：
#ifndef ADT_H_
#define ADT_H_
/* ------二叉树数据类型定义------ */
typedef char TElemType; //顺序表中元素的数据类型
/* ------二叉树链式结构类型定义------ */
typedef struct BiTNode
{
TElemType data; //二叉树结点数据
struct BiTNode *lchild, *rchild; //二叉树结点指针
}BiTNode, *BiTree; //二叉树结点类型及结构体指针类型
/************************栈和队列*************************/
/* ------栈数据类型定义------ */
typedef BiTree SElemType; //顺序表中元素的数据类型
/* ------队列数据类型定义------ */
typedef BiTree QElemType; //顺序表中元素的数据类型
#endif/* ADT_H_ */
3.头文件"DataStructure_StackQueue.h"中部分函数定义如下：
#include
#include
#include"ADT.h"
#include"DataStructure_StackQueue.h" //数据结构第三章栈和队列相关函数的定义及声明
/************************************************************
* 功能函数声明区
************************************************************/
Status GreateBiTree(BiTree &T); //按先序输入二叉树中节点的值,'#'字符表示空树,构造二叉链表树T
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //先序递归遍历二叉树T
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //中序递归遍历二叉树T Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //递归后序遍历二叉树T
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //递归层序遍历二叉树T Status PreOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e)); //先序非递归遍历二叉树T
Status InOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e)); //中序非递归遍历二叉树T
Status PostOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e)); //后序非递归遍历二叉树T
Status LevelOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e));//层序非递归遍历二叉树T
int BiTDepth(BiTree &T); //求二叉树的深度
Status TraverseLevel(BiTree root, int level,Status(*Visit)(TElemType e));
//遍历以roo为根节点中的level层的所以节点（从左到右），成功返回1，失败返回0
Status PreOrderLocate(BiTree &T, TElemType e, BiTree &T1);
//先序查找以元素值为e的结点为子树，并以T1指向其根子树
Status ChildBiTreeDepth(BiTree &, TElemType , int &); //求以元素值x的节点的根子树的深度
Status InitBiTree(BiTree &T); //初始化二叉链表T
Status BiTreeEmpty(BiTree T); //判断二叉树是否为空，若为空则返回TRUE, 否则返回FALSE Status DestoryBiTree(BiTree &T); //销毁二叉树T
Status DelBiTree(BiTree &); //删除二叉链表T
Status DelChildBiTree(BiTree &, TElemType e); //删除以元素值为e的结点为根子树
Status CompleteBiTree(BiTree T); //判断二叉树是否为完全二叉树
Status ExchangeBiTree(BiTree &T); //先序交换二叉树的左右子树
Status LeafTNodeNum(BiTree T, int &num); //求二叉树的叶子结点的个数，叶子结点个数num
Status CopyBiTree(BiTree &T1, BiTree &T2); //复制二叉树
Status PrintElement(TElemType e); //二叉树数据元素操作应用函数
/************************************************************
* 功能函数定义区
************************************************************/
/*
* 函数原型：Status PrintElement(TElemType e)
* 函数功能：二叉树数据元素操作应用函数
* 入口参数：TElemType类型的数据
* 出口参数：返回函数结果状态
*/
Status PrintElement(TElemType e)
{
printf("%c ",e);
return OK;
} //PrintElement
/*
* 函数原型：Status GreateBiTree(BiTree &T)
* 函数功能：按先序输入二叉树中结点的值，'#'字符表示空树，构造二叉链表树T
* 入口参数：BiTree类型树T
* 出口参数：返回函数结果状态
*/
Status GreateBiTree(BiTree &T)
{
TElemType data;
scanf_s("%c", &data);
if (data == '#')
T = NULL;
else
{
if (!(T = (BiTree)malloc(sizeof(BiTNode))))
return OVERFLOW;
T->data = data;
GreateBiTree(T->lchild);
GreateBiTree(T->rchild);
}
return OK;
} //GreateBiTree
/*
* 函数原型：Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit一次且仅一次* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
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; //访问根结点失败,不能返回ERROR,返回OK,保证所有节点都能被访问} // PreOrderTraverse
/*
* 函数原型：Status PreOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
Status PreOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
{
BiTree p;
LinkStack S;
InitStack_L(S);
p = T;
while (p || !StackEmpty_L(S))
{
if (p)
{
if (!Visit(p->data)) //如果根指针不空，访问根结点
return ERROR;
Push_L(S, p); //根指针域压栈，继续遍历左子树
p = p->lchild;
}
else//根指针已空，本左子树遍历完毕
{
Pop_L(S, p); //根指针域退栈，继续遍历右子树
p = p->rchild;
}
}
return OK;
} // PreOrderTraverseNonRec
/*
* 函数原型：Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
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;
return ERROR; //访问失败
}
else
return OK; //访问失败
} // InOrderTraverse
/*
* 函数原型：Status InOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
Status InOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
{
BiTree p;
LinkStack S;
InitStack_L(S);
p = T;
while (p || !StackEmpty_L(S))
{
if (p)
{
Push_L(S, p); //根指针进栈，遍历左子树
p = p->lchild;
}
else
{
Pop_L(S, p); //根指针退栈，访问根结点，遍历右子树
if (!Visit(p->data))
return ERROR;
p = p->rchild;
}
}
return OK;
} // InOrderTraverseNonRec
/*
* 函数原型：Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
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;
return ERROR; //访问失败
}
else
return OK;
} // PostOrderTraverse
/*
* 函数原型：Status PostOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
Status PostOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
{
BiTree p, q, last;
LinkStack S;
q = last = NULL;
InitStack_L(S);
p = T;
while (p || !StackEmpty_L(S))
{
while (p) //根指针不空，则进栈，遍历左子树
{
Push_L(S, p);
p = p->lchild;
}
GetTop_L(S, q);
if (!q->rchild || q->rchild == last) //根节点能被访问的条件是右子树为空或已被访问过
{
if (!Visit(q->data))
return ERROR;
Pop_L(S, last);
}
else
p = q->rchild;
}
return OK;
} // PostOrderTraverseNonRec
/*
* 函数原型：Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
* 函数功能：层序遍历二叉树T的递归算法，对每个数据元素调用函数Visit一次且仅一次
* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
if (!T)
return ERROR;
for (int level = 0;; level++)
{
if (!TraverseLevel(T, level, Visit))
break;
printf("\n");
}
return OK;
} //LevelOrderTraverse
/*
* 函数原型：Status LevelOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e)) * 函数功能：层序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit一次且仅一次* 入口参数：二叉链表T，Visit是对数据元素操作的应用函数
* 出口参数：返回函数结果状态
*/
Status LevelOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e))
{
BiTree p;
LinkQueue Q;
InitQueue_L(Q);
if (T)
EnQueue_L(Q, T);
while (!QueueEmpty_L(Q))
{
DeQueue_L(Q, p);
Visit(p->data);
if (p->lchild)
EnQueue_L(Q, p->lchild);
if (p->rchild)
EnQueue_L(Q, p->rchild);
}
return OK;
} // LevelOrderTraverseNonRec
/*
* 函数原型：Status TraverseLevel(BiTree root,int level，Status(*Visit)(TElemType e))
* 函数功能：遍历以roo为根节点中的level层的所以节点（从左到右），成功返回1，失败返回0
* 入口参数：root：二叉树的根结点，level：层次数，根结点为第0层
* 出口参数：返回函数结果状态
*/
Status TraverseLevel(BiTree root, int level, Status(*Visit)(TElemType e))
{
if (!root || level < 0)
return ERROR;
if (level == 0)
return Visit(root->data);
else
return TraverseLevel(root->lchild, level - 1, Visit) + TraverseLevel(root -> rchild, level - 1, Visit);
} //PrintBiTreeLevel
/*
* 函数原型：int BiTDepth(BiTree T)
* 函数功能：求二叉树的深度
* 入口参数：二叉链表T
* 出口参数：二叉链表的深度
*/
int BiTDepth(BiTree &T)
{
int ldepth, rdepth;
if (!T)
return 0;
else
{
ldepth = BiTDepth(T->lchild) + 1;
rdepth = BiTDepth(T->rchild) + 1;
return ldepth > rdepth ? ldepth : rdepth;
}
} //BiTDepth
/*
* 函数原型：Status CompleteBiTree(BiTree T)
* 函数功能：判断二叉树是否为完全二叉树
* 入口参数：二叉链表T
* 出口参数：返回函数结果状态
*/
Status CompleteBiTree(BiTree T)
{
int d;
if (T)
{
d = BiTDepth(T->lchild) - BiTDepth(T->rchild);
if (d<0 || d>1)
return ERROR;
else
{
if (CompleteBiTree(T->lchild) && CompleteBiTree(T->rchild))
return OK;
else
return ERROR;
}
}
return OK;
} //CompleteBiTree
/*
* 函数原型：Status LeafTNodeNum(BiTree T,int &num)
* 函数功能：求二叉树的叶子结点的个数，叶子结点个数num
* 入口参数：二叉链表T
* 出口参数：返回函数结果状态
*/
Status LeafTNodeNum(BiTree T,int &num)
{
if (!T)
return ERROR;
else
{
if (!T->lchild&&!T->rchild)
num++;
LeafTNodeNum(T->lchild, num);
LeafTNodeNum(T->rchild, num);
}
return OK;
} //LeafTNodeNum
1、此次实验完成了对二叉树的遍历操作和二叉树的一些基本操作。二叉树的遍历尤其是非递归遍历，加深了我对二叉树遍历过程的理解，
据结构有了更进一步的认识和掌握。
2、此次实验我最大的收获是递归思想，它将有递推关系的原本复杂的事情变得非常的清晰、明确，使程序实现变得简单。
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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. 本程序中用到的所有抽象数据类型的定义； typedef struct BiNode 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图： 3．列出各个功能模块的主要功能及输入输出参数 void push(char cc) 初始条件：输入表达式中的某个符号 操作结果：将输入的字符存入buf数组中去 BiTree Create_RTree() 初始条件：给出二叉树的定义表达式 操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组 BiTree Create_RootTree() 初始条件：给出二叉树的定义表达式
操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’void PreOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次 void InOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次 void PostOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次 int main() 主函数，调用各方法，操作成功后返回0 （三）调试分析 调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。 有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n). （四）测试结果 X：=(-b+(b^2-4*a*c)^/(2*a) （五）用户手册 打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。（六）附录 源程序： #include<>
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
实验题目：实验九——二叉树实验 算法设计（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 （）
重庆交通大学综合性设计性实验报告 班级：软件开发专业 2010级一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 6教 指导教师：鲁云平 实验完成时间： 2012 年 4 月 29 日
一、实验目的 主要完成以下功能: 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 Visual studio 2010
四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的简单应用 ㈡设计的主要思路 通过递归原理实现大部分遍历二叉树功能 ㈢主要功能 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出 五、主要代码 栈头文件：stack.h class Stack { public: Stack(int sz=100); ~Stack(){delete[]elements;} void Push(const T &x); bool Pop(T &x); bool getTop(T &x); bool IsEmpty()const{return(top==-1)?true:false;} bool IsFull()const{return(top==maxSize-1)?true:false;} private: T *elements; int top;
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （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))))
重庆交通大学综合性设计性实验报告 姓名姚远学号 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
实验3 树和二叉树 实验性质：验证性 实验学时：4学时 一、实验目的 1.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现； 2.能够利用二叉树求解一些常见问题。 二、实验预备知识 1.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作。 2.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。 三、实验内容 1.理解并用二叉链表的操作运行下列程序： #include 二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 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即为所给元素所在 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 福建农林大学计算机与信息学院实验报告 树与二叉树 一、实验目的和要求 1)进一步掌握指针变量、动态变量的含义。 2)掌握二叉树的结构特性及各种存储结构的特点及适用范围。 3)掌握用指针类型描述、访问和处理二叉树的运算。 4)熟悉各种存储结构的特征及如何应用树结构解决具体问题。 二、实验内容和原理 实验内容： 编写程序实现交换二叉树中所有结点的左右子树的算法。 实验原理： 【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将二叉树中所有结点的左右子树交换，显示其结果。 【基本要求】从键盘接受输入点（按层次遍历顺序），以“#”号结束，以二叉链表作为存储结构，将其二叉树中所有结点的左右子树交换，并将结果输出。 【实现】交换二叉树中所有结点的左右子树的具体步骤如下: ①将根结点进指针栈seqstack; ②当指针栈不空时，从栈顶取结点，如果此结点的左右孩子不为 空，则把其左右孩子交换，然后再分别将其左右孩子进栈； ③反复执行步骤②，直至指针栈为空时止。 三、实验环境 Windows XP系统 visual c++6.0 四、算法描述及实验步骤 #include "stdio.h" #include"stdlib.h" #define MAXSIZE 100 typedef char elemtype; typedef struct btnode {elemtype data; struct btnode *lchild, *rchild; }bitnode ,*bitree; typedef struct nodd {bitree addr; int parent; }sequre; bitree ins_node (bitree s,bitree t); void print_tree(bitree t); bitree creat_ordbt(); sequre seq[MAXSIZE]; void swap(bitree tree); int n=0; void main() {bitree tree; tree=creat_ordbt(); swap(tree); printf("输出交换后的二叉树\n"); print_tree(tree); } bitree creat_ordbt() {bitree t,s; elemtype x; t=NULL; printf("请按层次输入结点1的值(以#号结束，0号为空的结点)："); scanf("%c",&x); getchar(); while(x!='#') {n++; 实验四 二叉树的建立和应用 1、实验目的 （1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； （2）重点掌握二叉树的生成、遍历及求深度等算法； （3）掌握运用递归方式描述算法及编写递归C 程序的方法，提高算法分析和程序设计能力。 2、实验内容 按照已知二叉树，从键盘读入节点字符，建立二叉树（ABD#G###CE##FH###） ；分别采用先序、中序、后序遍历该二叉树，分别输出遍历结果。 3、实验步骤 （1）仔细分析实验内容，给出其算法和流程图； （2）用C 语言实现该算法； （3）给出测试数据，并分析其结果； （4）在实验报告册上写出实验过程。 4、测试数据 先序序列： ABDGCEFHjfkdkfakf 中序序列： DGBAECHF 后序序列： GDBEHFCA 5、结构定义 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 6、实验报告要求 实验报告要求书写整齐，步骤完整，实验报告格式如下： 1、［实验目的］ 2、［实验设备］ 3、［实验步骤］ 4、［实验内容］ 5、［实验结果(结论)］ G H B C D E F A 程序如下： #include "stdio.h" #include "string.h" typedef char TElemType ; typedef struct BiNode { TElemType data; struct BiNode * lchild ,* rchild; }BiNode ,*BiTree; BiTree CreateBiTree(BiTree bt) { char ch; B iTree h=NULL; c h=getchar(); i f(ch=='#') bt=NULL; e lse { if((bt=(BiNode *)malloc(sizeof(BiNode)))==NULL) exit(-2); bt->data=ch; bt->lchild=CreateBiTree(h); bt->rchild=CreateBiTree(h); } r eturn(bt); } void PreOrderTraverse(BiTree bt) 问题一：二叉树遍历 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 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 ADT BinaryTree{ //数据对象D:D是具有相同特性的数据元素的集合。 //数据关系R: // 若D=Φ，则R=Φ，称BinaryTree为空二叉树; // 若D?Φ，则R={H}，H是如下二元关系; // (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1， // (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。 数据结构 实 验 报 告 1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程 2.3关键算法分析 算法一：Create(BiNode 算法三：PreOrder(BiNode 实验报告 课程名称____数据结构上机实验__________ 实验项目______二叉树的应用 ____________ 实验仪器________PC机___________________ 系别____________________________ 专业_____________________________ 班级/学号____________________________ 学生姓名_____________________________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验三.二叉树的应用 1.实验目的：掌握二叉树的链式存储结构和常用算法。利用哈夫曼树设计最优压缩编码。 2.实验内容： 1)编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。 2)编写函数，实现生成哈夫曼编码的功能。 3)编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码。 选做内容：修改程序，选择实现以下功能： 4)编码：用哈夫曼编码对一段英文文本进行压缩编码，显示编码后的文本编码序列； 5)统计：计算并显示文本的压缩比例； 6)解码：将采用哈夫曼编码压缩的文本还原为英文文本。 3.算法说明： 1)二叉树和哈夫曼树的相关算法见讲义。 2)编码的方法是：从头开始逐个读取文本字符串中的每个字符，查编码表得到它的编码并输出。重复处理直至文本结束。 3)解码的方法是：将指针指向哈夫曼树的树根，从头 开始逐个读取编码序列中的每位，若该位为1则向右子树走，为0则向左子树走。当走到叶子节点时，取出节点中的字符并输出。重新将指针放到树根，继续以上过程直至编码序列处理完毕。 4)压缩比例的计算：编码后的文本长度为编码序列中 的0和1,的个数，原文本长度为字符数*8。两者之比即为压缩比。 4.实验步骤： 实现哈夫曼树的编码序列操作： int i=0,j=0; huffnode p; p=tree[2*n-2];child=tree[i].rchild=-1; if (i二叉树实验报告
二叉树实验报告
数据结构实验三——二叉树基本操作及运算实验报告
二叉树的遍历实验报告
数据结构实验报告—二叉树
数据结构实验报告-树与二叉树
数据结构课程实验(树和二叉树的建立和应用)
数据结构二叉树遍历实验报告
二叉树的基本操作实验报告
数据结构二叉树的实验报告
二叉树的应用实验报告
相关主题
文本预览