首页

# <二叉树>

# 二叉树函数

# 二叉树的存储结构

1
2
3
4
5
typedef struct BiTNode
{
	TElemType data;//数据域
	struct BiTNode *lchild, *rchild;//左右孩子
}BiTNode, *BiTree;

# 二叉树的操作

# 创建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
int InitTree(BiTree &T)
{
	TElemType a;
	scanf("%d", &a);
	if (-1 == a) T = NULL;
	else {
		T = (BiTree)malloc(sizeof(BiTNode));
		T->data = a;
		InitTree(T->lchild);
		InitTree(T->rchild);
	}
	return 0;
}

# 先序遍历

1
2
3
4
5
6
7
8
9
void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		printf("%d ", T->data);
		PreOrder(T->lchild);//递归先序遍历左右子树
		PreOrder(T->rchild);
	}
}

# 中序遍历

1
2
3
4
5
6
7
8
9
10

void InOrder(BiTree T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);//递归中序遍历左右子树
		printf("%d ", T->data);
		InOrder(T->rchild);
	}
}

# 后序遍历

1
2
3
4
5
6
7
8
9
10

void PostOrder(BiTree T)
{
	if (T != NULL)
	{
		PostOrder(T->lchild);//递归后序遍历左右子树
		PostOrder(T->rchild);
		printf("%d ", T->data);
	}
}

# 层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void LevelOrder(BiTree T)
{
	queue<BiTNode> q;//借助队列
	if (T != NULL)
	{
		BiTNode temp;//暂存要出队的结点
		q.push(*T);//根结点入队
		while (!q.empty())//队列非空
		{
			temp = q.front();
			q.pop();
			printf("%d ", temp.data);
			if (temp.lchild != NULL) q.push(*temp.lchild);//队列先进先出，先入左孩子
			if (temp.rchild != NULL) q.push(*temp.rchild);
		}
	}
}

# 完整可测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType int
using namespace std;
//链式二叉树数据结构
typedef struct BiTNode
{
	TElemType data;//数据域
	struct BiTNode *lchild, *rchild;//左右孩子
}BiTNode, *BiTree;
//********************************基本操作函数********************************//
//创建二叉树 规定数据域为-1，则为空 先序创建
int InitTree(BiTree &T)
{
	TElemType a;
	scanf("%d", &a);
	if (-1 == a) T = NULL;
	else {
		T = (BiTree)malloc(sizeof(BiTNode));
		T->data = a;
		InitTree(T->lchild);
		InitTree(T->rchild);
	}
	return 0;
}
//先序遍历-递归
//先序遍历 按照逻辑来说,执行这个函数前,应该进行逻辑判断（树是否为空），放在里面的话也没有else进行输出提示，不太好
//这里就按照课本敲代码了，在对应功能实现函数进行逻辑判断
void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		printf("%d ", T->data);
		PreOrder(T->lchild);//递归先序遍历左右子树
		PreOrder(T->rchild);
	}
}
//中序遍历-递归
void InOrder(BiTree T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);//递归中序遍历左右子树
		printf("%d ", T->data);
		InOrder(T->rchild);
	}
}
//后序遍历-递归
void PostOrder(BiTree T)
{
	if (T != NULL)
	{
		PostOrder(T->lchild);//递归后序遍历左右子树
		PostOrder(T->rchild);
		printf("%d ", T->data);
	}
}
//层序遍历
void LevelOrder(BiTree T)
{
	queue<BiTNode> q;//借助队列
	if (T != NULL)
	{
		BiTNode temp;//暂存要出队的结点
		q.push(*T);//根结点入队
		while (!q.empty())//队列非空
		{
			temp = q.front();
			q.pop();
			printf("%d ", temp.data);
			if (temp.lchild != NULL) q.push(*temp.lchild);//队列先进先出，先入左孩子
			if (temp.rchild != NULL) q.push(*temp.rchild);
		}
	}
}
//**********************************功能实现函数*****************************//
//调用InitTree
void CreateBiTree(BiTree &T)
{
	printf("请按照先序遍历输入二叉树(-1无):");
	InitTree(T);
	printf("二叉树先序遍历序列:");
	PreOrder(T);
	printf("\n");
}
//遍历功能函数 调用PreOrder InOrder PostOrder LevelOrder
void Traverse(BiTree T)
{
	int choice;
	while (1)
	{
		printf("********1.先序遍历    2.中序遍历*********\n");
		printf("********3.后序遍历    4.层次遍历*********\n");
		printf("********5.返回上一单元\n");
		printf("请输入菜单序号：\n");
		scanf("%d", &choice);
		if (5 == choice) break;
		switch (choice)
		{
		case 1: {printf("二叉树先序遍历序列:");PreOrder(T);printf("\n");}break;
		case 2: {printf("二叉树中序遍历序列:");InOrder(T);printf("\n");}break;
		case 3: {printf("二叉树后序遍历序列:");PostOrder(T);printf("\n");}break;
		case 4: {printf("二叉树层次遍历序列:");LevelOrder(T);printf("\n");}break;
		default:printf("输入错误！！！\n");break;
		}
	}
}
//菜单
void menu()
{
	printf("********1.创建    2.遍历*********\n");
	printf("********3.退出\n");
}
//主函数
int main()
{
	BiTree T = NULL;int choice = 0;
	while (1)
	{
		menu();
		printf("请输入菜单序号：\n");
 
		scanf("%d", &choice);
		if (3 == choice) break;
		switch (choice)
		{
		case 1:CreateBiTree(T);break;
		case 2:Traverse(T);break;
		default:printf("输入错误！！！\n");break;
		}
	}
	return 0;
}

# 二叉树查找树

# 二叉查找树函数

# 插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//二叉查找树插入 参数T，二叉查找树根节点 作用：插入数据data,保证中序非严格递增（即可重复）
int BST_Insert(BSTree &T, TElemType data)
{
	if (T == NULL)//树为空
	{
		T = (BSTree)malloc(sizeof(BSTNode));//申请结点空间
		T->data = data;                     //赋值
		T->lchild = NULL;                   //左右孩子为空
		T->rchild = NULL;
		return 1;
	}
	else if (data < T->data)               //比当前节点数据小，插入左子树
	{
		return BST_Insert(T->lchild,data);
	}
	else                                   //这里规定二叉查找树可以重复，等于及大于当前结点时，插入右子树
	{
		return BST_Insert(T->rchild,data);
	}
}

# 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//层序遍历 借助队列
void LevelOrder(BSTree T)
{
	queue<BSTNode> q;//借助队列
	if (T != NULL)
	{
		BSTNode temp;//暂存要出队的结点
		q.push(*T);//根结点入队
		while (!q.empty())//队列非空
		{
			temp = q.front();
			q.pop();
			cout << temp.data << " ";
			if (temp.lchild != NULL) q.push(*temp.lchild);//队列先进先出，先入左孩子
			if (temp.rchild != NULL) q.push(*temp.rchild);
		}
	}
}

# 查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//二叉查找树查找 参数 BSTree T, TElemType key，作用查找key是否存在于二叉查找树中，若存在，返回指向该结点的指针，否则，返回空
BSTNode * BST_Search(BSTree T, TElemType key)
{
   BSTNode *cur = T; //当前结点指针cur
   while (cur&&key!=cur->data)
   {
	   if (key<cur->data)     //比当前结点数据小
	   {
		   cur = cur->lchild;
	   }
	   else                  //比当前结点数据大
	   {
		   cur = cur->rchild;
	   }
   }
   return cur;
}

# 删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//二叉查找树删除 参数 BSTree T, TElemType key，作用查找key是否存在于二叉查找树中，若存在，删除，返回true,否则，返回false
bool BST_Delete(BSTree &T, TElemType key)
{
	BSTNode*  cur = T;
	BSTNode*  cur_par = NULL;//当前结点的双亲结点
	while (cur&&key != cur->data)
	{
		if (key<cur->data)     //比当前结点数据小
		{
			cur_par = cur;    //记录双亲结点
			cur = cur->lchild;
		}
		else                  //比当前结点数据大
		{
			cur_par = cur;    //记录双亲结点
			cur = cur->rchild;
		}
	}
	if (cur)//找到啦，分情况删除：叶子结点（度为0） 单支结点（度为1） 双支结点（度为2）
	{
		if (cur->lchild==NULL&&cur->rchild==NULL)//叶子结点
		{
			if (cur == T)//根节点
			{
				T = NULL;
			}
			else if (cur_par->lchild == cur)//要删除的是cur_par的左孩子
			{
				cur_par->lchild = NULL;
			}
			else
			{
				cur_par->rchild = NULL;
			}
		}
		else if (cur->lchild == NULL || cur->rchild == NULL)//单支结点
		{
			if (cur == T)//根节点
			{
				if (cur->lchild)//有左孩子
				{
					T = cur->lchild;
				}
				else
				{
					T = cur->rchild;
				}
			}
			else //非根结点，双亲结点指向要删除结点的子结点即可
			{
				if (cur_par->lchild == cur&&cur->lchild)//cur为cur的双亲结点的左孩子，且有左孩子
				{
					cur_par->lchild = cur->lchild;
				}
				else if (cur_par->lchild == cur&&cur->rchild)
				{
					cur_par->lchild = cur->rchild;
				}
				else if (cur_par->rchild == cur&&cur->lchild)
				{
					cur_par->rchild = cur->lchild;
				} 
				else{
					cur_par->rchild = cur->rchild;
				}
			}
		}
		else //双支结点  可以选择与直接前驱交换数据域，然后删除直接前驱。
			//或者，与直接后继交换数据域，删除直接后继。这里选择后者。
		{
			BSTNode* temp = cur;//记录需要删除的结点，接下来要与直接后继交换数据域
			cur_par = cur;      //用cur找到temp的直接后继 则cur为temp右子树的最左孩子
			cur = cur->rchild;  //右子树
			while (cur->lchild)//找到直接后继，即右子树的最左孩子（最小值）
			{
				cur_par = cur;
				cur=cur->lchild;
			}
			temp->data = cur->data;//交换数据域
			if (cur_par == temp)//待删除结点的右子树没有左子树，即右子树根节点即为待删除结点后继
			{
				cur_par->rchild = cur->rchild;
			}
			else               //待删除结点的右子树有左子树
			{
				cur_par->lchild = cur->rchild;//将cur的右子树给双亲结点
			}		
		}
		free(cur);
		return true;
	}//if
	return false;
}

# 哈夫曼树

# 哈夫曼树函数

# 哈夫曼树存储结构

1
2
3
4
5
6
7
8
9
//哈夫曼树结点结构
typedef struct HNode 
{
	char data; //数据,非叶节点为NULL
	double weight;//权重
	int parent;//双亲，-1表示没有双亲，即根节点
	int lchild;//左孩子，数组下标,-1表示无左孩子，即叶节点
	int rchild;//右孩子
}Hnode;

# 操作函数

# 创建哈夫曼树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//创建哈夫曼树
void CreateHT()
{
	int n;//字符个数，即哈夫曼树叶节点个数
	minnodes mins;
	cout << "请输入字符个数：" << endl;
	cin >> n;
	cout << "请输入字符及权值：" << endl;
	for (int i=0;i<n;i++)
	{
		cin >> HT[i].data >> HT[i].weight;
		HT[i].lchild = -1;HT[i].rchild = -1;
	}
	/*
	HT[0].data = 'a';HT[0].weight = 45;HT[0].lchild = -1;HT[0].rchild = -1;
	HT[1].data = 'b';HT[1].weight = 13;HT[1].lchild = -1;HT[1].rchild = -1;
	HT[2].data = 'c';HT[2].weight = 12;HT[2].lchild = -1;HT[2].rchild = -1;
	HT[3].data = 'd';HT[3].weight = 16;HT[3].lchild = -1;HT[3].rchild = -1;
	HT[4].data = 'e';HT[4].weight = 9; HT[4].lchild = -1;HT[4].rchild = -1;
	HT[5].data = 'f';HT[5].weight = 5; HT[5].lchild = -1;HT[5].rchild = -1;*/
	int i = n;
	for (;;i++)
	{
		mins = Select(i);//找到两棵根权值最小的树
		if (mins.flag == false)//仅剩余一棵树时跳出
		{
			HT[mins.m1].parent = -1;
			break;
		}			
		HT[i].weight = HT[mins.m1].weight + HT[mins.m2].weight;//新加入哈夫曼树结点为两个结点权值之和
		HT[i].data = ' ';
		HT[mins.m1].parent = i;                                //两个权值最小结点双亲为新加入结点
		HT[mins.m2].parent = i;
		HT[i].lchild = mins.m1;//左小又大
		HT[i].rchild = mins.m2;
	} 
	PrintHT(i);//打印哈夫曼树
}

# 哈夫曼编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//哈夫曼树编码
void Code()
{
	int i = 0;
	for (;;i++)//给所有叶子结点编码
	{
		int j = i;
		string str="";
		HC[i].data = HT[i].data;//复制数据
		while (-1!=HT[j].parent)//从叶节点找到根
		{
			if (HT[HT[j].parent].lchild == j)//左0右1
			{
				str += '0';
			}
			else
			{
				str += '1';
			}
			j = HT[j].parent;
		}
		reverse(str.begin(),str.end());//逆序
		HC[i].code = str;              //保存至编码
		if (HT[i].lchild == -1 && HT[i].rchild == -1)continue;//非叶子不编码
		else break;
	}
	PrintHC(i);
}

# 哈夫曼解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//哈夫曼树解码 从根开始，左0右1，直至叶节点
void Encode() 
{
	string s;
	int root=0;//记录根节点的下标
	cout << "请输入01字符串:" << endl;
	cin >> s;
	while (HT[root].parent != -1) root++;
	int j = root;
	for (int i=0;i<s.length();i++)//遍历输入的01串
	{
		if ('0' == s[i])
		{
			j = HT[j].lchild;
		}
		else
		{
			j = HT[j].rchild;
		}
		if (HT[j].lchild == -1 && HT[j].rchild == -1)//到达叶节点
		{
			cout << HT[j].data;
			j = root;//返回根节点继续
		}
	}
	cout << endl;
}

# 计算带权路径长度

1
2
3
4
5
6
7
8
9
10
11
//计算WPL
void WPL() 
{
	double WPL=0;
	for (int i = 0;;i++)
	{
		if (HT[i].lchild != -1 || HT[i].rchild != -1)break;
		WPL += HT[i].weight*HC[i].code.length();//权值×路径长度（编码长度）	
	}
	cout << "WPL:" << WPL << endl;
}
更新于 阅读次数 次