二叉树的基本操作
2020-03-24 本文已影响0人
白大胡
一、基本内容
-
二叉树的创建（先顺遍历的方法）
-
二叉树的先序遍历
-
二叉树的中序遍历
-
二叉树的后序遍历
-
哈夫曼树的创建与哈夫曼编码
二、实验内容
二叉树结点结构体
typedef struct BitTree
{
char data;
struct BitTree *lchild,*rchild;
}BitTree;
链式先序遍历二叉树的创建
链式二叉树创建思想：
[图片上传失败...(image-b7787f-1585053392374)]
创建结点输入结点数据，判断是否结束，递归函数创建当前结点的左子树，左子树创建结束后，递归函数创建右子树；结束后返回根结点。
代码实现
BitTree *Creat(BitTree *root)
{
char c;
puts("输入结点的值，输入0时结束。");
scanf("%c",&c);
//putchar(c);
fflush(stdin);
if(c=='0')
root = NULL;
else
{
root =(BitTree *)malloc(sizeof(BitTree));
root->data=c;
root->lchild=Creat(root->lchild);
root->rchild=Creat(root->rchild);
}
return root;
}
二叉树的先序遍历
先序遍历思想：访问根结点、访问当前节点的左树、访问当前节点的右树。
[图片上传失败...(image-37624c-1585053392374)]
先序遍历流程：
-
访问结点1，读取节点1的数据1
-
进入结点1 的左子树2，读取当前结点的数据2
-
进入结点2 的左子树4，读取当前结点的数据4
-
结点4没有子树，退回到结点2
-
进入节点2的右子树5，读取数据5
-
节点5没有子树，退回到结点1，节点1点左子树遍历完毕。
-
进入结点1的右子树3
……
图片.png
先序遍历上图二叉树的结果为：1245367
递归思想代码实现
void Ftraverse(BitTree *root)
{
char c;
if(root!=NULL)
{
c=root->data;
printf("%c ",c);
Ftraverse(root->lchild);
Ftraverse(root->rchild);
}
}
中序遍历
中序遍历思想：访问当前结点的左子树，访问根结点，访问当前结点的右子树。即访问结点的左子树，没有左子树就退回来读取当前结点，然后再进入右结点。
图片.png
中序遍历结果：4251637
代码实现
void Mtraverse(BitTree *root)
{
char c;
if(root!=NULL)
{
Mtraverse(root->lchild);
printf("%c",root->data);
Mtraverse(root->rchild);
}
}
后序遍历
后序遍历思想：从根结点出发，遍历结点的左右子树，当左右子树遍历完成后，访问该结点的数据。
图片.png
上图后序遍历结果为：4526731
代码实现：
void Ltraverse(BitTree *root)
{
char c;
if(root!=NULL)
{
Ltraverse(root->lchild);
Ltraverse(root->rchild);
printf("%c",root->data);
}
}
哈夫曼树与哈夫曼编码
哈夫曼树本质上是二叉树，是经过权重优化后的二叉树。通过哈夫曼树对数据优化这一特性，可以对数据进行编码。哈夫曼编码在数组中建构。
