中国大学MOOC-陈越、何钦铭-数据结构-习题解答-04 树（中）

中国大学MOOC-陈越、何钦铭-数据结构-习题解答-04 树（中）

1. 04-树4 是否同一棵二叉搜索树 (25 分)

【题目描述】

题目链接

【题解】

用的是和老师讲解的思路，先按照第一个输入次序建立一棵二叉搜索树，之后将其余输入序列依次读入，用Judge函数将其与建好的二叉搜索树进行判别，不建立实际的树。具体代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElementType_Tree int
/*树结点定义*/ 
typedef struct TreeNode* BinTree;
struct TreeNode {
	ElementType_Tree Data;
	BinTree Left;
	BinTree Right;
	int flag;					//结点是否被访问过的标签 
};
BinTree MakeTree(int N);
bool Judge(BinTree BST,int N);
void Reset(BinTree BST);
void FreeTree(BinTree BST); 

BinTree NewTreeNode(ElementType_Tree X);
BinTree Insert(BinTree BST,ElementType_Tree X);
bool check(BinTree BST,ElementType_Tree num);

int main(void)
{
	int N,L;			//N：树的结点数；L：要检查的输入序列数 
	scanf("%d",&N);
	while (N) {
		scanf("%d",&L);
		BinTree BST=MakeTree(N);	//建树 
		for (int i=0;i<L;i++) {
			if (Judge(BST,N))		//读入一个输入序列并进行判别 
				printf("Yes\n");
			else
				printf("No\n");
			Reset(BST);				//将树的结点全部重新标记为未访问 
		}
		FreeTree(BST);				//当前二叉搜索树已经全部判别完，释放这棵树 
		scanf("%d",&N);
	}
	
	return 0;
}
BinTree MakeTree(int N)			/*建立二叉搜索树函数*/ 
{
	BinTree BST;
	ElementType_Tree X;
	scanf("%d",&X);				//读入结点数据 
	BST=NewTreeNode(X);			//申请一个树结点的空间并装填数据		
	for (int i=1;i<N;i++) {		//依次插入其余结点 
		scanf("%d",&X);
		BST=Insert(BST,X);
	}
	return BST;
}
bool Judge(BinTree BST,int N)	/*判别是否是同一二叉搜索树函数*/ 
{
	bool flag=true;
	ElementType_Tree num;
	
	scanf("%d",&num);			//读入根结点 
	if (num!=BST->Data)			//判别根结点是否一致 
		flag=false;				//注意不能直接return，因为还要判别下一组数据 
	else 
		BST->flag=1;
	for (int i=1;i<N;i++) {		//依次判别其他结点 
		scanf("%d",&num);
		if (flag && !check(BST,num))	//如果根结点相同，则继续检查 
			flag=false;
	}
	if (flag)					//全部读完一组数据后再返回结果 
		return true;
	else 
		return false;
}
void Reset(BinTree BST)			/*重置flag值的函数*/ 
{
	if (BST->Left)
		Reset(BST->Left);
	if (BST->Right)
		Reset(BST->Right);
	BST->flag=0;
}
void FreeTree(BinTree BST)		/*释放树的函数*/ 
{
	if (BST->Left)
		FreeTree(BST->Left);
	if (BST->Right)
		FreeTree(BST->Right);
	free(BST);
}

BinTree NewTreeNode(ElementType_Tree X)		/*申请并装填树结点函数*/ 
{
	BinTree T=(BinTree)malloc(sizeof(struct TreeNode));
	T->Data=X;
	T->Left=T->Right=NULL;
	T->flag=0;
	return T;
}
BinTree Insert(BinTree BST,ElementType_Tree X)	/*插入树结点函数（按照二叉搜索树的方式）*/ 
{
	if (!BST) {					//空树 
		BST=NewTreeNode(X);
	} else {					//非空树，递归插入 
		if (X < BST->Data)
			BST->Left=Insert(BST->Left,X);
		else if (X > BST->Data)
			BST->Right=Insert(BST->Right,X);
	}
	return BST;
}
bool check(BinTree BST,ElementType_Tree num) /*检查树结点函数*/ 
{
	if (BST->flag) {		//结点已经访问过 
		if (num < BST->Data)		//沿左子树继续递归检查 
			return check(BST->Left,num);
		else if (num > BST->Data)	//沿右子树继续递归检查 
			return check(BST->Right,num);
		return false;
	} else {				//结点未访问，则待检查数据必须与该树结点数据一致 
		if (num == BST->Data) {
			BST->flag=1;
			return true;
		} else
			return false;
	}
}
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

2. 04-树5 Root of AVL Tree (25 分)

【题目描述】

题目链接

【题解】

这个是二叉平衡树最基本的操作——调整一棵二叉搜索树为二叉平衡树，主要是单旋和双旋函数的设计，直接上代码：

#include <stdio.h>
#include <stdlib.h>
#define ElementType int
typedef struct AVLNode* AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left;
	AVLTree Right;
	int Height;
};
AVLTree Insert(AVLTree T,ElementType X);		/*插入函数*/ 
AVLTree SingleLeftRotation(AVLTree A);			/*左单旋函数*/ 
AVLTree SingleRightRotation(AVLTree A);			/*右单旋函数*/ 
AVLTree DoubleLeftRightRotation(AVLTree A);		/*左-右双旋函数*/ 
AVLTree DoubleRightLeftRotation(AVLTree A);		/*右-左双旋函数*/
int Max(int a,int b);
int GetHeight(AVLTree T);

int main(void)
{
	int N;
	ElementType X;
	AVLTree T=NULL;
	scanf("%d",&N);
	for (int i=0;i<N;i++) {
		scanf("%d",&X);
		T=Insert(T,X);
	}
	printf("%d\n",T->Data);
	
	return 0;
}

AVLTree Insert(AVLTree T,ElementType X)
{
	if (!T) {
		T=(AVLTree)malloc(sizeof(struct AVLNode));
		T->Data=X;
		T->Left=T->Right=NULL;
		T->Height=1;
	} else {
		if (X < T->Data) {
			T->Left=Insert(T->Left,X);
			if (GetHeight(T->Left)-GetHeight(T->Right)==2)	//需要左旋 
				if (X < T->Left->Data)
					T=SingleLeftRotation(T);				//左单旋	
				else
					T=DoubleLeftRightRotation(T);			//左右单旋 
		} else if (X > T->Data) {
			T->Right=Insert(T->Right,X);
			if (GetHeight(T->Left)-GetHeight(T->Right)==-2)	//需要右旋 
				if (X > T->Right->Data)
					T=SingleRightRotation(T);				//右单旋 
				else
					T=DoubleRightLeftRotation(T);			//右左单旋 
		}
	}
	T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1; 	//必须更新树的高度！ 
	
	return T;
}
AVLTree SingleLeftRotation(AVLTree A)
{
	AVLTree B=A->Left;
	A->Left=B->Right;
	B->Right=A;
	A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;
	B->Height=Max(GetHeight(B->Left),A->Height)+1;				//GetHeight(B->Right)==A->Height;
	
	return B;
}
AVLTree SingleRightRotation(AVLTree A)
{
	AVLTree B=A->Right;
	A->Right=B->Left;
	B->Left=A;
	A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;
	B->Height=Max(GetHeight(B->Right),A->Height)+1;
	
	return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A)
{
	A->Left=SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A)
{
	A->Right=SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

int Max(int a,int b)
{
	return (a>b?a:b);
}
int GetHeight(AVLTree T)
{
	if (!T)					//一定要考虑空树的情况！ 
		return 0;
	else
		return T->Height;
}
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

3. 04-树6 Complete Binary Search Tree (30 分)

【题目描述】

题目链接

【题解】

这道题目有一定难度，我是看了陈越老师的思路讲解后做出来的。题目要求将一个输入序列建立为完全二叉搜索树，所谓完全二叉搜索树的意思是：

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

也就是这棵树既是一棵二叉搜索树，也是一棵完全搜索树。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MaxN 1000
int A[MaxN],T[MaxN];	//A：存储输入数据；T：存储完全搜索二叉树 

int compare(const void*a, const void*b);	//辅助qsort函数 
void BuildCBSTree(int ALeft, int ARight, int TRoot);
int GetLeftLength(int n);

int main(void)
{
	int N;
	scanf("%d",&N);
	for (int i=0;i<N;i++)
		scanf("%d",&A[i]);
	qsort(A,N,sizeof(int),compare);		//库函数，快速排序 
	BuildCBSTree(0,N-1,0);		//核心算法，建立完全搜索二叉树 
	
	printf("%d",T[0]);			//打印结果	
	for (int i=1;i<N;i++)
		printf(" %d",T[i]);
	printf("\n");
	
	return 0;
}
int compare(const void*a, const void*b)
{
	return *(int*)a-*(int*)b;
}
void BuildCBSTree(int ALeft, int ARight, int TRoot)	/*构建完全搜索二叉树*/ 
{ 
	int n,L,TLeftRoot,TRightRoot;
	n=ARight-ALeft+1;		//结点数 
	if (n==0)				//结束递归的条件 
		return;
	L=GetLeftLength(n);			//得到左子树的结点数 
	T[TRoot]=A[ALeft+L];		//根结点的值 
	TLeftRoot=TRoot*2+1;		//左子树根结点位置 
	TRightRoot=TLeftRoot+1;		//右子树根结点位置 
	BuildCBSTree(ALeft,ALeft+L-1,TLeftRoot);	//递归构建左子树 
	BuildCBSTree(ALeft+L+1,ARight,TRightRoot);	//递归构建右子树 
}
int GetLeftLength(int n)		/*获取左子树的结点数*/ 
{
	int L,H,X;				//L：左子树的结点数；H：树的高度；X：最低一层的结点数 
	/*以下式子经数学推导得来*/ 
	H=log(n+1)/log(2);		//log，pow函数参数和返回值均为double，此处进行了自动类型转换 
	X=n+1-pow(2,H);
	X=(X < pow(2,H-1))?X:pow(2,H-1);
	L=pow(2,H-1)-1+X;
	
	return L;
}
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