数据结构第五站：树和二叉树

/*二叉树遍历及相关基本操作 先序、中序、后序遍历使用递归实现，层次遍历使用队列实现 */

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define True 1
#define False 0
//测试数据:FCA##DB###EH##GM###

//树结点
typedef struct BiTNode{
char data; //树结点数据域
struct BiTNode *rchild,*lchild;//左右孩子指针
}BiTNode,*BiTree;

//队列结点
typedef struct QNode{
BiTree data; //数据域
struct QNode *next; //指针域
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;

//函数声明
BiTree CreateBiTree(); //二叉树的创建（先序遍历）
void Copy(BiTree T,BiTree NewT); //二叉树的复制
int Depth(BiTree T); //计算二叉树的深度
int NodeCount(BiTree T); //统计二叉树的结点总个数
void PreOrderTraverse(BiTree T); //先序遍历二叉树
void InOrderTraverse(BiTree T); //中序遍历二叉树
void BaOrderTraverse(BiTree T); //后序遍历二叉树
void LevelTraverse(BiTree T); //层次遍历二叉树（队列）
void Swap(BiTree T); //交换左右子树

LinkQueue *InitQueue(); //队列的初始化
void EnQueue(LinkQueue *Q,BiTree T); //入队
void DeQueue(LinkQueue *Q); //出队
int Empty(LinkQueue *Q); //判断队列是否为空
BiTree GetHead(LinkQueue *Q); //获取队头元素

int main(){
BiTree T;
int total,depth;
cout<<"请输入测试数据："<<endl;
T= CreateBiTree();
cout<<"先序遍历结果为："<<endl;
PreOrderTraverse(T);
printf("\n");
cout<<"中序遍历结果为："<<endl;
InOrderTraverse(T);
printf("\n");
cout<<"后序遍历结果为："<<endl;
BaOrderTraverse(T);
printf("\n");
cout<<"层次遍历结果为："<<endl;
LevelTraverse(T);
Swap(T);
printf("\n交换左右子树后的后序遍历结果为：\n");
BaOrderTraverse(T);
total=NodeCount(T);
printf("\n二叉树的结点总数为：%d\n",total);
depth=Depth(T);
printf("二叉树的深度为：%d\n",depth);
return 0;
}

//二叉树的创建
BiTree CreateBiTree()//按照先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
{ BiTree T;
char ch;
cin>>ch;
if(ch=='#')T=NULL; //递归结束，建立树
else{
T = new BiTNode; //生成根结点
T->data=ch; //根结点的数据域置为ch
T->lchild=CreateBiTree();//递归创建左子树
T->rchild=CreateBiTree();//递归创建右子树
}
return T;
}
//复制二叉树
void Copy(BiTree T,BiTree NewT)//复制一棵和T完全相同的二叉树
{
if(T==NULL)
{
NewT=NULL;
printf("T为空树！\n");
}
else{
NewT=new BiTNode;
NewT->data=T->data; //复制根结点
Copy(T->lchild,NewT->lchild); //递归复制左子树
Copy(T->rchild,NewT->rchild); //递归复制右子树
}
}
//计算二叉树的深度
int Depth(BiTree T){
if(T==NULL) return 0;
else{
int m=Depth(T->lchild); //左子树深度
int n=Depth(T->rchild); //右子树深度
if(m>n)return (m+1); //二叉树的深度为m与n的较大者加1
else return (n+1);
}
}

//统计二叉树结点个数
int NodeCount(BiTree T){
if(T==NULL) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

//先序遍历二叉树
void PreOrderTraverse(BiTree T){
if(T)
{ printf("%c ",T->data); //访问根结点
PreOrderTraverse(T->lchild); //先序遍历左子树
PreOrderTraverse(T->rchild); //先序遍历右子树
}
}

//中序遍二叉树
void InOrderTraverse(BiTree T){
if(T)
{
InOrderTraverse(T->lchild);//中序遍历左子树
printf("%c ",T->data); //访问根结点
InOrderTraverse(T->rchild);//中序遍历右子树
}

}


//后序遍历二叉树
void BaOrderTraverse(BiTree T){
if(T){
BaOrderTraverse(T->lchild); //后序遍历左子树
BaOrderTraverse(T->rchild); //后序遍历右子树
printf("%c ",T->data); //访问根结点
}
}

//层次遍历二叉树
void LevelTraverse(BiTree T){
BiTree p;
LinkQueue *Q;
Q=InitQueue();
if(!T)
{
printf("此二叉树为空树！\n");
}
else
{
EnQueue(Q,T);
}
while(!Empty(Q))
{
p=GetHead(Q); //获取队头指针
DeQueue(Q); //删除队头元素
printf("%c ",p->data);
if(p->lchild)
{
EnQueue(Q,p->lchild); //左孩子入队
}
if(p->rchild)
{
EnQueue(Q,p->rchild); //右孩子入队
}
}
}
void Swap(BiTree T) //交换左右子树
{
BiTree p;
if (T)
{
Swap(T->rchild);
Swap(T->lchild);
p = T->rchild;
T->rchild = T->lchild;
T->lchild = p;
}
}
//队列的初始化
LinkQueue* InitQueue()
{
LinkQueue *Q;
Q->rear=Q->front=new QNode; //生成新结点为头结点，队头和队尾指针指向此结点
Q->front->next=NULL; //头结点的指针域置空
return Q;

}
//元素的入队
void EnQueue(LinkQueue *Q,BiTree T){
QNode *p=new QNode; //为入队元素分配结点空间，用指针p指向
p->data=T;
p->next=NULL;
Q->rear->next=p; //将新结点插到队尾
Q->rear=p;
}

//元素的出队
void DeQueue(LinkQueue *Q){
QNode *p;
if(Q->front==Q->rear)
printf("队列已空！\n");
p=Q->front->next; //p指向队头元素
Q->front->next=p->next; //修改头结点的指针域
if(Q->rear==p)
Q->rear=Q->front;
delete p;
}
//判断队列是否空
int Empty(LinkQueue *Q){
if(Q->front==Q->rear){
return True;
}
else{
return False;
}
}
//获取队头元素
BiTree GetHead(LinkQueue *Q){
if(Q->front==Q->rear){
return NULL;
}
else{
return Q->front->next->data; //
}
}

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
#pragma warning (disable:4996)
#define maxSize 100
/*
赫夫曼树的存储结构，它也是一种二叉树结构，
这种存储结构既适合表示树，也适合表示森林。
*/
typedef struct Node
{
int weight; //权值
int parent; //父节点的序号，为-1的是根节点
int lchild, rchild; //左右孩子节点的序号，为-1的是叶子节点
}HTNode, *HuffmanTree; //用来存储赫夫曼树中的所有节点
typedef char **HuffmanCode; //用来存储每个叶子节点的赫夫曼编码

HuffmanTree create_HuffmanTree(int *wet, int n); //创建哈夫曼树
void select_minium(HuffmanTree HT, int k, int &min1, int &min2);//返回两个最小值下标
int Min(HuffmanTree HT, int k); //返回最小值下标
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n);//创建哈夫曼编码
int *Array(int *S,int n); //初始化数组
int main()
{
int *S;
int n,WPL;
printf("请输入元素总数：\n");
scanf("%d",&n);
S=Array(S,n);
HuffmanCode HC = NULL;
HuffmanTree HT = create_HuffmanTree(S, n);
printf("\n从根结点到叶子结点编码结果为：\n");
CreateHuffmanCode(HT, HC, n);
system("pause");
return 0;
}
//初始化数组
int *Array(int *S,int n){
int i;
S=(int *)malloc(sizeof(int)*n);
cout<<"请输入元素："<<endl;
for(i=0;i<n;i++){
scanf("%d",S+i);
}
return S;
}

/*根据给定的n个权值构造一棵赫夫曼树,wet中存放n个权值*/
HuffmanTree create_HuffmanTree(int *wet, int n)
{
//一棵有n个叶子节点的赫夫曼树共有2n-1个节点
int total = 2 * n - 1;
HuffmanTree HT = (HuffmanTree)malloc(total * sizeof(HTNode));
if (!HT)
{
printf("HuffmanTree malloc faild!");
exit(-1);
}
int i;

//以下初始化序号全部用0表示，
//这样在编码函数中进行循环判断parent或lchild或rchild的序号时，
//不会与HT数组中的任何一个下标混淆
//HT[0],HT[1]...HT[n-1]中存放需要编码的n个叶子结点
for (i = 0; i < n; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].weight = *wet;
wet++;
}
//HT[n],HT[n+1]...HT[2n-2]中存放的是中间构造出的每棵二叉树的根节点
for (; i < total; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].weight = 0;
}
int min1, min2; //用来保存每一轮选出的两个weight最小且parent为0的节点
//每一轮比较后选择出min1和min2构成一课二叉树,最后构成一棵赫夫曼树
for (i = n; i < total; i++)
{
select_minium(HT, i, min1, min2);
HT[min1].parent = i;
HT[min2].parent = i;
//这里左孩子和右孩子可以反过来，构成的也是一棵赫夫曼树，只是所得的编码不同
HT[i].lchild = min1;
HT[i].rchild = min2;
HT[i].weight = HT[min1].weight + HT[min2].weight;
}
return HT;
}
/*
从HT数组的前k个元素中选出weight最小且parent为0的两个，分别将其序号保存在min1和min2中
*/
void select_minium(HuffmanTree HT, int k, int &min1, int &min2)
{
min1 = min(HT, k);
min2 = min(HT, k);
}
/*
从HT数组的前k个元素中选出weight最小且parent为-1的元素，并将该元素的序号返回
*/
int Min(HuffmanTree HT, int k)
{
int i = 0;
int min; //用来存放weight最小且parent为-1的元素的序号
int min_weight; //用来存放weight最小且parent为-1的元素的weight值

while (HT[i].parent != 0)
i++;
min_weight = HT[i].weight;
min = i;
for (; i < k; i++)
{
if (HT[i].weight < min_weight && HT[i].parent == 0)
{
min_weight = HT[i].weight;
min = i; //选出weight最小且parent为0的元素，并将其序号赋给min
}
}
HT[min].parent = 1; //选出weight最小的元素后，将其parent置1
return min;
}

//哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
//用来保存指向每个哈夫曼编码串的指针
HC = (HuffmanCode)malloc(n * sizeof(char *));
if (!HC)
{
printf("HuffmanCode malloc faild!");
exit(-1);
}

//临时空间，用来保存每次求得的赫夫曼编码串
//对于有n个叶子节点的赫夫曼树，各叶子节点的编码长度最长不超过n-1
//外加一个'\0'结束符，因此分配的数组长度最长为n即可
char *code = (char *)malloc(n * sizeof(char));
if (!code)
{
printf("code malloc faild!");
exit(-1);
}

code[n - 1] = '\0'; //编码结束符，亦是字符数组的结束标志
//求每个字符的赫夫曼编码
int i;
for (i = 0; i < n; i++)
{
int current = i; //定义当前访问的结点
int father = HT[i].parent; //当前节点的父节点
int start = n - 1; //每次编码的位置，初始为编码结束符的位置
//从叶子节点遍历赫夫曼树直到根节点
while (father != 0)
{
if (HT[father].lchild == current) //如果是左孩子，则编码为0
code[--start] = '0';
else //如果是右孩子，则编码为1
code[--start] = '1';
current = father;
father = HT[father].parent;
}

//为第i个字符的编码串分配存储空间
HC[i] = (char *)malloc((n - start) * sizeof(char));
if (!HC[i])
{
printf("HC[i] malloc faild!");
exit(-1);
}
//将编码串从code复制到HC
strcpy(HC[i], code + start);
}
for (int i = 0; i < n; ++i) {
printf("%d的编号为：%s\n",HT[i].weight, HC[i]);
}
free(code); //释放保存编码串的临时空间
}