实验三二叉树的基本操作
- 格式:doc
- 大小:33.00 KB
- 文档页数:8
实验三二叉树的基本运算
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容
题目一:二叉树的基本操作实现(必做题)
[问题描述]
建立一棵二叉树,试编程实现二叉树的如下基本操作:
1. 按先序序列构造一棵二叉链表表示的二叉树T;
2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列;
3. 求二叉树的深度/结点数目/叶结点数目;(选做)
4. 将二叉树每个结点的左右子树交换位置。(选做)
[基本要求]
从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),
[测试数据]
如输入:ABCффDEфGффFффф(其中ф表示空格字符)
则输出结果为
先序:ABCDEGF
中序:CBEGDFA
后序:CGEFDBA
层序:ABCDEFG
[选作内容]
采用非递归算法实现二叉树遍历。
三、算法设计
1、主要思想:根据二叉树的图形结构创建出二叉树的数据结构,然后
用指针对树进行操作,重点掌握二叉树的结构和性质。
2、本程序包含四个模块:
(1)结构体定义
(2)创建二叉树
(3)对树的几个操作
(4)主函数
四、调试分析
这是一个比较简单程序,调试过程中并没有出现什么问题,思路比较清晰
五、实验结果
六、总结
此次上机实验对二叉树进行了以一次实际操作,让我对二叉树有了更深的了解,对二叉树的特性有了更熟悉的认知,让我知
道了二叉树的重要性和便利性,这对以后的编程有更好的帮助。
七、源程序
#include
#include
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;
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PreOrderTraverse(BiTree T)
{
if (T)
{
cout << T->data;
if (PreOrderTraverse(T->lchild))
if (PreOrderTraverse(T->rchild))
return OK;
return ERROR;
}
else
return OK;
}
Status InOrderTraverse(BiTree T)
{
if (T)
{
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
return OK;
}
Status PostOrderTraverse(BiTree T) {
if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data;
}
return OK;
}
Status leOrderTraverse(BiTree T)
{
std::queue
if (T == NULL)return ERROR;
else{
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;
else{
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}