实验三 二叉树的基本运算
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
表演区活动目标
二、实验内容
题目一：二叉树的基本操作实现 （必做题）
[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做)
4. 将二叉树每个结点的左右子树交换位置。（选做）
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层序：ABCDEFG
[选作内容]
采用非递归算法实现二叉树遍历。
三、 算法设计
1、 主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后用指针对树进行操作，重点掌握二叉树的结构和性质。
2、 本程序包含四个模块：
（1）结构体定义
（2） 创建二叉树
（3） 对树的几个操作
（4） 主函数
四、 调试分析
这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰
五、 实验结果
六、 总结
此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。
七、源程序
#include<iostream>
心情愉悦
#include<queue>
using namespace std;
#define TElemType char
#define Status int
美女动漫图片#define OK 1
#define ERROR 0
typedef struct BiTNode{
TElemType data;
struct BiTNode * lchild, *rchild;
}BiTNode,* BiTree;
Status CreateBiTree(BiTree &T)
{
TElemType ch;
cin >> ch;
旋转三要素 if (ch == '#')
T = NULL;
el
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))五粮液一马当先
exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PreOrderTraver(BiTree T)
{
if (T)
{
cout << T->data;
if (PreOrderTraver(T->lchild))
if (PreOrderTraver(T->rchild))
return OK;瘀血怎么快速消除
return ERROR;
}
el
return OK;
}
Status InOrderTraver(BiTree T)
{
if (T)
{
InOrderTraver(T->lchild);
cout << T->data;
InOrderTraver(T->rchild);
}
return OK;
}
Status PostOrderTraver(BiTree T)惊羡
{
if (T)
{
PostOrderTraver(T->lchild);
PostOrderTraver(T->rchild);
cout << T->data;
}
return OK;
}
Status leOrderTraver(BiTree T)
{
std::queue<BiTree> Q;
if (T == NULL)return ERROR;
el{
Q.push(T);
while (!Q.empty())
{
T = Q.front();
Q.pop();
cout << T->data;
if (T->lchild != NULL)
Q.push(T->lchild);
if (T->rchild != NULL)
Q.push(T->rchild);
装烤瓷牙 }
}
return OK;
}
Status change(BiTree T)
{
BiTree temp = NULL;
if (T->lchild == NULL && T->rchild == NULL)
return OK;
el{
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
if (T->lchild)
change(T->lchild);
if (T->rchild)
change(T->rchild);
return OK;
}
int FindTreeDeep(BiTree T){
int deep = 0;
if (T){
int lchilddeep = FindTreeDeep(T->lchild);
int rchilddeep = FindTreeDeep(T->rchild);
deep = lchilddeep >= rchilddeep ? lchilddeep + 1 : rchilddeep + 1;
}
return deep;
}
int main()
{
BiTree T;
CreateBiTree(T);
cout << "先序遍历顺序为：";
PreOrderTraver(T);
cout << endl;
cout << "中序遍历顺序为：";
InOrderTraver(T);
cout << endl;
cout << "后序遍历顺序为：";
PostOrderTraver(T);
cout << endl;
cout << "层序遍历顺序为：";
leOrderTraver(T);
cout << endl;
