二叉树基本操作及实现的程序(完全正确)

#include

#include

using namespace std;

typedef struct BiTNode

{

char data;

struct BiTNode* lchild;

struct BiTNode* rchild;

}Bitnode,*BiTree;

BiTree createbintree()

{

BiTree t;

char x;

// scanf("%c",&x);

cin>>x;

if(x=='#')

t=NULL;

else

{

// t=(BTNode*)malloc(sizeof(BTNode));

t=new Bitnode;

t->data=x;

cout<<"请输入"<

t->lchild=createbintree();

cout<<"请输入"<

t->rchild=createbintree();

}

return(t);

}

void Insert(BiTree &t, char data){

BiTree s;

if (t==NULL)/*递归结束条件*/

{

s=new Bitnode;

s->data=data;

s->lchild=NULL;

s->rchild=NULL;

t=s;

}

else

if (data<(t)->data)

Insert(((t)->lchild), data);/*将s插入左子树*/ else

if (data> (t)->data)

Insert(((t)->rchild), data); /*将s插入右子树*/ }

//先序遍历二叉树，并输出结果

void Preorder(BiTree t)

{

if(t!=NULL)

{

cout<data<<"->";//输出根节点

Preorder(t->lchild);

Preorder(t->rchild);//递归访问左右子树

}

// else

// cout<<"先序遍历结束\n";

}

//中序遍历二叉树，并输出结果

void Inorder(BiTree t)

{

if(t!=NULL)

{

Inorder(t->lchild);

cout<data<<"->";

Inorder(t->rchild);

}

// else

// cout<<"中序遍历结束\n";

}

//后序遍历二叉树

void Postorder(BiTree t)

{

if(t!=NULL)

{

Postorder(t->lchild);

Postorder(t->rchild);

cout<data<<"->";

}

// else

// cout<<"后序遍历结束\n";

}

int main()

{

char x;

char n;

BiTree t;

cout<<"二叉树的基本操作!\n";

cout<<"首先创建一棵二叉树\n";

cout<<"请输入头结点（以'#'为结束）\n"; t=createbintree();

Preorder(t);

cout<

n = getch();

printf("%c", n);

while(n!='5')

{

switch(n)

{

case '1':

cout<

Preorder(t);

break;

case '2':

cout<

Inorder(t);

break;

case '3':

cout<

Postorder(t);

break;

case '4':

cout<

printf("请输入要插入的内容:\n");

x = getch();

printf("%c\n", x);

Insert(t,x);

break;

case '5':

cout<

exit(1);

break;

}

cout<

cout<<"请输入数字选择操作\n";

cout<<"--1、输出先序遍历二叉树结果--\n"; cout<<"--2、输出中序遍历二叉树结果--\n"; cout<<"--3、输出后序遍历二叉树结果--\n"; cout<<"--4、添加叶结点--\n";

cout<<"--5、退出--\n";

n = getch(); printf("%c\n", n); }

return 1;

}

二叉树的基本 操作

//二叉树的基本操作 #include typedef struct node //定义结点 { char data; struct node *lchild, *rchild; } BinTNode; typedef BinTNode *BinTree; //定义二叉树 void CreateBinTree(BinTree &T); //先序创建二叉树 void PreOrder(BinTree T); //先序遍历二叉树 void InOrder(BinTree T); //中序遍历二叉树 void PostOrder(BinTree T); //后序遍历二叉树 int onechild(BinTree T); //求度为1的结点的个数int leafs(BinTree T); //求叶子结点的个数 int twochild(BinTree T); //度为2的结点的个数void translevel(BinTree b); //层序遍历二叉树 void main() { int n; BinTree T; char ch1,ch2; cout<<"欢迎进入二叉树测试程序的基本操作"<

实验三 二叉树的基本操作实现及其应用

二叉树的基本操作实现及其应用 一、实验目的 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<<"二叉树初始化成功!"<>ch; if(ch=='#') BT=NULL; else { if(!(BT=(BitTree)malloc(sizeof(BitNode)))) exit(0);

数据结构——二叉树的操作(遍历及树形输出)

/*实验三：二叉树遍历操作验证*/ #include #include #include #include #include

if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue q;//建队 q.push(T);//根节点入队

二叉树的基本操作实验

实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现

1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

数据结构——二叉树基本操作源代码

数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include using namespace std; //------------------------------------------------------------------------------------------------------------------------ //定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。template struct BTNode { T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 }; //------------------------------------------------------------------------------------------------------------------------ //CBinary的类模板 template class BinaryTree { BTNode* BT; public: BinaryTree(){BT=NULL;} // 构造函数,将根结点置空 ~BinaryTree(){clear(BT);} // 调用Clear()函数将二叉树销毁 void ClearBiTree(){clear(BT);BT=NULL;}; // 销毁一棵二叉树 void CreateBiTree(T end); // 创建一棵二叉树，end为空指针域标志 bool IsEmpty(); // 判断二叉树是否为空 int BiTreeDepth(); // 计算二叉树的深度 bool RootValue(T &e); // 若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回false BTNode*GetRoot(); // 二叉树不为空获取根结点指针，否则返回NULL bool Assign(T e,T value); // 找到二叉树中值为e的结点，并将其值修改为value。

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

数据结构实验三——二叉树基本操作及运算实验报告

《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。

实验10 二叉树的基本操作

浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test10.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： typedef struct BiTNode { TElemType data ; struct BiTNode *lchild , *rchild ; }BiTNode,*BiTree ; 基本操作如下： ①void InitBiTree(BiTree &T ) //初始化二叉树T ②void CreateBiTree(BiTree &T) //按先序遍历序列建立二叉链表T ③bool BiTreeEmpty (BiTree T); //检查二叉树T是否为空，空返回1，否则返回0 ④int BiTreeDepth(BiTree T); //求二叉树T的深度并返回该值 ⑤void PreOrderTraverse (BiTree T); //先序遍历二叉树T ⑥void InOrderTraverse (BiTree T); //中序遍历二叉树T ⑦void PostOrderTraverse (BiTree T); //后序遍历二叉树T ⑧void DestroyBiTree(BiTree &T) //销毁二叉树T

二叉树及其操作的实现

班级：数媒1101 学号：0305110125 课程名称：数据结构实验 实验名称：二叉树及其操作的实现 实验内容和目的： 内容：1. 创建二叉树； 2. 用递归方法实现二叉树的各种遍历。 目的：1.掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 2.掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍 历算法的递归实现和非递归实现。 实验步骤： 1.首先定义二叉树的存储形式； 2.用CreateBiTree( )构造二叉链表表示的二叉树T； 3. 用PreOrder ( bitree *t )、InOrder ( bitree *t)、PostOrder ( bitree * t )这三个函数 对二叉树依次进行先序、中序、后序遍历，并输出遍历序列。 实验代码/文件描述： #include "stdio.h" #include "stdlib.h" #define maxsize 64 #define null 0 typedef char datatype; typedef struct node { datatype data; struct node * lchild, * rchild; } bitree; bitree * bitr; bitree *Q[maxsize];

bitree *CREATREE( ) { char ch ; int front , rear ; bitree *root , *s ; root = null ; front = 1 ; rear = 0 ; ch = getchar( ) ; while ( ch != '#' ) { s = null ; if ( ch != '@' ) { s =(bitree*) malloc(sizeof(bitree)); s->data = ch ; s->lchild = null ;s->rchild =null; } rear ++; Q[rear] = s ; if (rear == 1 ) root = s ; else { if ( s && Q[front] ) if (rear%2==0 ) Q[front]->lchild = s ; else Q[front]->rchild = s ; if ( rear%2==1 ) front ++; } ch = getchar ( ) ; } return root ; } void PreOrder ( bitree *t ) { if ( t != null ) { printf("\t%c\n",t->data); PreOrder ( t->lchild ); PreOrder ( t->rchild ); } } void InOrder ( bitree *t) { if ( t != NULL ) { InOrder ( t->lchild ); printf("\t%c\n", t->data); InOrder ( t->rchild ); } }

二叉树基本操作经典实例

本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include using namespace std; #define FLAG'#' typedef char Record; template struct Binary_Node { Entry data; Binary_Node*left; Binary_Node*right; Binary_Node(); Binary_Node(const Entry& x); }; template Binary_Node::Binary_Node() { left=NULL; right=NULL; } template Binary_Node::Binary_Node(const Entry &x) { data=x; left=NULL; right=NULL; } template class Binary_tree { public: bool empty()const; Binary_tree(); Binary_tree(Binary_tree&org); void create_tree(Binary_Node*&tree);//建立二叉树 void recursive_copy(Binary_Node*&tree,Binary_Node*&cur); void pre_traverse(Binary_Node *tree);//前序 void mid_traverse(Binary_Node *tree);//中序 void post_traverse(Binary_Node *tree);//后序遍历

二叉树的基本操作及实现.cpp

二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include #define MAXNODE 100 typedef char DataType; typedef struct BiTNode{ DataType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void Visit(DataType bt){ //输出二叉树结点值 cout<lchild=NULL;bt->rchild=NULL; return bt; } BiTree Create_BiTree(DataType x,BiTree lbt,BiTree rbt){ //建立二叉树：以结点值为x的结点为头结点，并以lbt和rbt为左右子树BiTree p; p=new BiTNode; if(!p){ cout<<"无法完成二叉树的建立!"<data=x; p->lchild=lbt;p->rchild=rbt; return p; } BiTree InsertL(BiTree bt,DataType x,BiTree parent){ //在某结点之后插入左结点BiTree p; if(parent==NULL){ cout<<"要插入结点的父节点不存在！"<

二叉树的基本 操作

创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include typedef struct node //定义结点 { char data; struct node *lchild, *rchild; } BinTNode; typedef BinTNode *BinTree; //定义二叉树 void CreateBinTree(BinTree &T); //先序创建二叉树 void PreOrder(BinTree T); //先序遍历二叉树 void InOrder(BinTree T); //中序遍历二叉树 void PostOrder(BinTree T); //后序遍历二叉树 int onechild(BinTree T); //求度为1的结点的个数int leafs(BinTree T); //求叶子结点的个数 int twochild(BinTree T); //度为2的结点的个数void translevel(BinTree b); //层序遍历二叉树 void main() { int n; BinTree T; char ch1,ch2; cout<<"欢迎进入二叉树测试程序的基本操作"<

cout<<"--------------请选择------------"<>ch2; switch(ch2) { case '1': cout<<"请输入按先序建立二叉树的结点序列：\n"; CreateBinTree(T); cout<

数据结构实验-二叉树的操作

******************************* 实验题目：二叉树的操作 实验者信息：班级 13007102,姓名 庞文正，学号 1300710226 实验完成的时间 3:00 ****************************** 一、 实验目的 1, 掌握二叉树链表的结构和二叉树的建立过程。 2, 掌握队列的先进先出的运算原则在解决实际问题中的应用。 3, 进一步掌握指针变量、指针数组、动态变量的含义。 4, 掌握递归程序设计的特点和编程方法。 二、 实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。 （所谓层次遍历，是 指从二叉树的根结点开始从上到下逐层遍历二叉树， 在同一层次中从左到右依次访问各个节 点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加 深对算法的理解。 三、 算法设计与编码 1. 本实验用到的理论知识 总结本实验用到的理论知识， 实现理论与实践相结合。 总结尽量简明扼要， 并与本次实验密 切相关，最好能加上自己的解释。 本算法要采用一个循环队列 que,先将二叉树根结点入队列，然后退队列，输出该 结点；若它 有左子树，便将左子树根结点入队列； 若它有右子树，便将右子树根结点入队列， 直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。 2. 算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include #include #define M 100 typedef struct node //二叉链表节点结构 {int data; // 数据域 struct node *lchild,*rchild; }bitree; bitree *que[M]; //定义一个指针数组，说明队列中的元素 int front=0, rear=0; 〃初始化循环列队 bitree *creat() 〃建立二叉树的递归算法 {bitree *t; int x; scanf("%d”,&x); if(x==0) t=NULL; 〃以 else {t=malloc(sizeof(bitree)); t->data=x; t->lchild=creat(); t->rchild=creat(); //左孩子右孩子链 x=0表示输入结束 bitree 指针类型 〃动态生成节点t,分别给节点t 的数据域， //左右孩子域赋值，给左右孩子赋值时用到 // 了递归思想

C++二叉树的创建与遍历实验报告

二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include #include using namespace std; template struct BinTreeNode //二叉树结点类定义 { T data; //数据域 BinTreeNode *leftChild,*rightChild; //左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL ) :data(x),leftChild(l),rightChild(r){} //可选择参数的默认构造函数 }; //------------------------------------------------------------------------- template void PreOrder_2(BinTreeNode *p) //非递归前序遍历 { stack * > S;

数据结构课程设计-二叉树的基本操作

二叉树的基本操作 摘要： 本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式：先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。增加了对二叉树这一数据结构的理解，掌握了使用c语言对二叉树进行一些基本的操作。 关键字：递归、二叉树、层序遍历、子树交换 一、程序简介 本程序名为“二叉树基本操作的实现”，其主要为练习二叉树的基本操作而开发，其中包含了建立、遍历、统计叶子结点和深度等一系列操作。其中定义二叉链表来表示二叉树，用一个字符类型的数据来表示每一个节点中存储的数据。由于没有进行图形界面的设计，用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。 二、功能模块 2.1功能模块图 2.2功能模块详解 2.2.1建立二叉树

输入要建立的二叉树的扩展二叉树的先序遍历序列，来建立二叉树，建立成功会给出提示。 2.2.2遍历二叉树 执行操作之后会有四个选项可供选择：先序遍历、中序遍历、后序遍历、层序遍历。 输入对应的序号即可调动相关函数输出相应的遍历序列。 2.2.3统计叶子节点树 执行之后输出叶子结点的个数。 2.2.4求二叉树深度 执行之后输出二叉树的深度。 2.2.5子树交换 交换成功则会给出提示，用户可通过遍历二叉树来观察子树交换之后的二叉树。 三、数据结构和算法设计 3.1二叉链表的设计 1.typedef struct BiNode { 2.char data; 3.struct BiNode* lchild; //左孩子 4.struct BiNode* rchild; //右孩子 5.}BiTree; 用一个字符型保存节点数据，分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。在BiTree.h中实现相关的功能。 3.2队列的实现 1.typedef struct { 2. ElemType* data; 3.int head;//队头指针 4.int tail;//队尾指针 5.} SqQueue; 队列主要用于二叉树遍历过程中的层序遍历，从根节点开始分别将左右孩子放入队列，然后从对头开始输出。队列的相关操作封装在SqQueue.h中，包括入队、出队、判断队列是否为空等操作。

实验五-二叉树基本操作的编程实现实验分析报告

实验五-二叉树基本操作的编程实现实验报告

————————————————————————————————作者：————————————————————————————————日期：

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验报告 这里一定填 写清楚自己 实验项目实验五实验类别基础篇 学生姓名朱忠栋学生学号20120231515 完成日期2014-12-16 指导教师付勇智 实验成绩评阅日期 评阅教师

实验五二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 以下的选题都可以作为本次实验的推荐题目 1.建立二叉树，并以前序遍历的方式将结点内容输出。 2.将一个表示二叉树的数组结构转换成链表结构。 3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序 及后序遍历结果，并计算出表达式之结果。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】

页面不够，可续页。 根据自己选择的层次不同的实验内容，完善程序代码，调试通过后，分析说明该问题处理的详细算法过程。不需要写出详细的代码，只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数学表达方式来说明。 这次实验考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的结果。 而对于基础篇考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果，是以填空的方式进行考查的。 对于第一空：递归实现的先序遍历，其实现方法是： printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空：递归实现的中序遍历，其实现方法是： if(p->lchild!=NULL) inorder(p->lchild); printf("%d",p->data); if(p->rchild!=NULL) inorder(p->rchild); 对于第三空：递归实现的后序遍历，其实现方法是： if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%d",p->data); 【思考问题】 页面不够，可续页。 1.二叉树是树吗？它的定义为什么是递归的？ 答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。具有n个结点的完全二叉树的深度为log2n +1 ！！！二叉树的计算方法：若一棵二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1 2.三种根序遍历主要思路是什么？ 答：大体思路差不多，但节点访问位置不一样，先序的话，是先访问，然后节点压栈，移到左子树，至节点空退栈，移到右子树。而中序的话，是先节点压栈，移到左子树，至节点空退栈，访问节点，然后移到右子树。另外，所谓前序、中序、后序遍历，全称是前根序遍历，中根序遍历，后根序遍历，不管哪种遍历，访问左子树一定在访问右子树之前，不同的就是根的访问时机。 所以三种递归/或非递归，程序思路都是一样的。 3.如果不用遍历算法一般启用什么数据结构实现后序遍历？ 答：用栈实现后序遍历。 4.举出二叉树的应用范例？ 答：一个集合的幂集、排列问题、组合问题

二叉树的基本操作实验报告

二叉树的基本操作实验报告 学号姓名实验日期 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，?H，且存在D1上的关系H1 ?H;若Dr?Φ，则Dr中存在惟一的元素xr，?H，且存在上的关系 Hr ?H;H={,,H1,Hr};

// (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的叶子结点数。

实验四-二叉树操作实现

实验四-二叉树操作实现

实验四二叉树操作实现 实验日期：2017 年 4 月20 日 实验目的及要求 1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； 2. 重点掌握二叉树的创建、遍历及求深度等算法； 3. 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 实验内容 键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。 二叉树结点类型定义： typedef char datatype; typedef struct tnode{ datatype data; struct tnode *lchild,*rchild; } BiTNode,*BiTree; 任务 1．题目要求 创建一个程序文件sy4.cpp，自定义相应函数完成以下操作：

（1）void visit(BiTree p) /*输出p指针指向的结点*/ （2）void Preorder(BiTree T) /*前序遍历*/ （3）void Inorder(BiTree T) /*中序遍历*/ （4）void Postorder(BiTree T) /*后序遍历*/ （5）BiTree CreateTree( ) /*以前序遍历的顺序建立二叉树*/ （6）int deep(BiTree T) /*求二叉树深度*/ （7）int leaf(BiTree T) /*求叶子结点数*/ （8）int OneChild(BiTree T) /*求1度结点数*/ （9）int TwoChild(BiTree T) /*求2度结点数*/ （10）void Exchange(BiTree T) /*二叉树左右子树交换*/ （11）BiTree InorderLastNode(BiTree T); /*找二叉树中序遍历最后一个结点*/ 2．请回答下列问题 （1）在n个结点二叉树的二叉链表存储中，其指针域的总数为2n 个，其中n-1 个用于链接孩子结点，n+1 个空闲着。 （2）在二叉链表存储中，数据域值为data，左右子树的指针分别为left和right，则判断： 指针p所指结点为0度结点的条件是p->left==NULL&&p->right==NULL ；指针p所指结点为1度结点的条件是(p->left==NULL&&p->right!=NULL)||(p->left!=NULL&&p->right==NULL) ； 指针p所指结点为2度结点的条件是p->left!=NULL&&p->right!=NULL 。（3）T为二叉树的根的地址，该树是空二叉树满足条件：T==NULL 。 3．sy14.cpp源程序清单（含必要的注释） #include #include typedef char datatype; typedef struct tnode { datatype data; struct tnode *lchild, *rchild; } BiTNode, *BiTree; void visit(BiTree p); /*输出p指针指向的结点*/ void Preorder(BiTree T); /*前序遍历*/ void Inorder(BiTree T); /*中序遍历*/ void Postorder(BiTree T); /*后序遍历*/ BiTree CreateTree(); /*以前序遍历的顺序建立二叉树*/