实验二二叉树及其应用
内容：
1、计算二叉树叶子节点的个数。
2、交换二叉树所有节点的左、右孩子节点。
3、根据二叉树的前序遍历和中序遍历的结果，构造二叉树。
BinaryTree.cpp
#include "BinaryTree.h"
template
bool BinaryTree
{//取跟节点的data域，放入x
//如果没有根节点，就返回false
if(root) {x = root->data;
return true;}
else return false;
}
template
void BinaryTree
{//将left，right和element合并成一个新树
//left，right和this必须都是不同的树
//创建新树
root = new BinaryTreeNode
left.root = right.root = 0;
}
template
void BinaryTree
{
if(!root) throw BadInput();
element = root ->data;
left = root ->LeftChild;
right = root ->RightChild;
delete root;
root = 0;
}
template
void BinaryTree
{
if(t){
Inorder(visit,t->LeftChild);
visit(t);
Inorder(visit,t->RightChild);
}
}
template
int BinaryTree
{
int count = 0;
if(!t) return 0;
else if(t->LeftChild==0&&t->RightChild==0) count++;
else
{
count += CountChild(t->LeftChild);
count += CountChild(t->RightChild);
}
return count;
}
template
int BinaryTree
{
BinaryTreeNode
t=root;
int count = 0;
if(!t) return 0;
else if(t->LeftChild==0&&t->RightChild==0) count++;
else
{
count += CountChild(t->LeftChild);
count += CountChild(t->RightChild);
}
return count;
}
template
void BinaryTree
{
if(!t) return;
BinaryTreeNode
q = t->LeftChild;
t->LeftChild = t->RightChild;
t->RightChild = q;
Change(t->LeftChild);
Change(t->RightChild);
}
template
void BinaryTree
{
Change(root);
}
template
void shuchu(BinaryTreeNode
{
t->Output();
}
BinaryTree.h
#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include
using namespace std;
template
class BinaryTree;
template
class BinaryTreeNode;
template
class BinaryTreeNode{
friend class BinaryTree
public:
BinaryTreeNode() {LeftChild =RightChild = 0;}
BinaryTreeNode(const T& e)
{
data = e;
LeftChild = RightChild = 0;
}
BinaryTreeNode(const T& e,BinaryTreeNode *l,BinaryTreeNode *r)
{
data = e;
LeftChild = l;
RightChild = r;
}
void Output(){cout << data << " ";}
private:
T data;
BinaryTreeNode
BinaryTreeNode
};
template
class BinaryTree {
public:
BinaryTree(){root = 0;}
virtual ~BinaryTree(){};
bool IsEmpty() const {return ((root) ? true : false);}
bool Root(T& x)const;
void MakeTree(const T& element,BinaryTree
void BreakTree(T& element,BinaryTree
void Inorder(void (*visit)(BinaryTreeNode
{
Inorder(visit,root);
}
int CountChild(BinaryTreeNode
int CountChild();
void Change(BinaryTreeNode
void Change();
private:
BinaryTreeNode
void Inorder(void (*visit)(BinaryTreeNode
class BadInput{
public:
BadInput(){}
};
#endif /* BINARYTREE_H_ */
experiment.cpp
#include
using namespace std;
#include"BinaryTree.cpp"
template
class BinaryTree;
template
class BinaryTreeNode;
int main() {
BinaryTree
int count = 0;
y.MakeTree(4,a,a);
z.MakeTree(5,a,a);
b.MakeTree(6,a,a);
c.MakeTree(7,a,a);
x.MakeTree(2,y,z);
z.MakeTree(3,b,c);
y.MakeTree(1,x,z);
cout<<"中序遍历为：";
y.Inorder(shuchu);
cout << endl;
cout << "孩子节点数为";
count = y.CountChild();
cout<< count << "个" < y.Change(); cout<<"交换后的中序遍历为："; y.Inorder(shuchu); cout << endl; return 0; } 二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。 3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。 #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．熟悉二叉树结点的结构和对二叉树的基本操作。 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<<"二叉树初始化成功!"< #include 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); } 数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12) 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p; 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：二叉树是n(n>=0)个元素的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。在本实验中根据要求操作先序遍历二叉树：思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素（输出）,此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）...一直这样下去，直到栈为空。中序遍历二叉树：思想：利用栈。从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，有则进栈，没有则继续弹栈。重复下去....栈空，是判定条件。后序遍历二叉树算法：思想：利用栈来实现。从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素（只是取，并去弹栈），判断1:取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件（无右子节点，或者右子节点被访问过），则输出该结点，同时弹栈，并且记录下该访问的节点2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。 2、本程序包含七个模块 1）主函数 实验五二叉树及其应用 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 实验题目：实验九——二叉树实验 算法设计（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 （） 二叉树操作的实现 #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．报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求。 长春建筑学院《数据结构》课程设计（论文） 基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation 年级: 学号: 姓名: 专业: 指导老师: 二零一三年十二月 摘要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。 二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。 本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。 关键词：二叉树；左子树；右子树 实验六最优二叉树的应用 【实验目的】 掌握求最优二叉树的方法。 【实验内容】 最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率 {2,3,5,7,11,13,17,19,23,29,31,37,41}，求各通信符号对应的前缀码。 【实验原理和方法】 （1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。 （2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。 #include struct tree *temp; for(i=N-n;i二叉树遍历方法技巧
数据结构实验六二叉树操作代码实现
实验三 二叉树的基本操作实现及其应用
二叉树遍历所有代码
数据结构二叉树实验报告
实验三 二叉树的操作及应用
二叉树遍历C语言(递归,非递归)六种算法
数据结构实验二叉树
二叉树遍历课程设计】汇编
实验三 二叉树的基本运算
二叉树及其应用(实验五)
二叉树实验报告
实验三 二叉树操作的实现 代码及运行结果图
实验5 二叉树建立及应用
基于二叉树遍历系统设计与实现
实验六 最优二叉树的应用
相关主题
文本预览