查找及其相关算法_输入10 个不同整数,依次插入到一颗初始为空的二叉排序树中,并对其进行中序遍历,以

一、静态查找表

1.1 顺序表查找

1.2 有序表查找

1.2 .1折半查找（二分查找）

优点：查找的效率高
缺点：已排好序，只适用于顺序存储

例题：
随机产生80 个整数构成的递增序列，
使用折半查找算法查找指定的整数，并统计比较次数。
提示：可用 a[i] = a[i-1] + rand() % 10 + 1 产生递增序列。 (1,10-1+1)

/*
* 


rand() % n +a;
 其中的a是起始值，n-1+a是终止值，n是整数的范围
	
	
	*/

#include <iostream>
using namespace std;

int c=0;

//折半查找
int Search_bin(int *a, int key) {
	int low = 1;
	int high = 80;
	while (low<=high)
	{
		c++;
		int mid=(low + high) / 2;
		if (key==a[mid]) {
			return mid;
			
		}
		else if(key<a[mid]){
			high = mid - 1;

		}
		else {
			low = mid + 1;
		}
		

	}
	return -1;
}


int main() {
	int a[80];
	
	for (int i = 1; i <= 80; i++) {
		if (i == 1) {
			a[i] = rand() % 10 + 1;
		}
		else {
			a[i] = a[i - 1] + rand() % 10 + 1;
		}
	}
	for (int i = 1; i <= 80; i++) {
		cout << a[i] << "\t";
		if (i % 10 == 0) {
			cout << endl;
		}
	}
	cout << endl;

	int k;
	cout << "请输入你要查找的元素的值:";
	cin >> k;

	if (Search_bin(a,k)) {
		cout << k << "在a[]中位置为：" << Search_bin(a, k) << endl;
		cout << "比较次数为：" << c << endl;
	}
	else {
		cout << "不在a中";
	}

	return 0;
}
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

1.2.2 索引顺序表

二、动态查找表

二叉排序树（二叉查找树）

/*
输入10 个不同整数，依次插入到一颗初始为空的二叉排序树中，
并对其进行中序遍历，以验证树的正确性
*/
#include <iostream>
using namespace std;


#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

//栈存储结构
typedef struct {
	int* base; //栈构造之前和销毁之后，值都为NULL
	int* top; //栈顶指针
	int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;

/*初始化*/
int InitStack(SqStack& S) {
	S.base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
	if (!S.base) //存储分配失败
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return 1;

}
/*判断栈是否为空*/
int StackEmpty(SqStack S)
{
	if (S.base == S.top)
		return 1;
	else
		return 0;
}

/*插入*/
int Push(SqStack& S, int e) {
	//e 新的栈顶元素
	if (S.top - S.base >= S.stacksize) {
		S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));
		if (!S.base)
			exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return 1;
}
/*删除栈顶元素并返回其值*/
int Pop(SqStack& S, int& e) {
	if (S.top == S.base)
		return 0;
	e = *--S.top;
	return 1;
}

/*二叉链表存储结构*/
typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

int SearchBST(BiTree T, int key, BiTree f, BiTree& p)
//查找成功，参数p指向查找到的结点，f指向它的双亲；否则p指向key应插入的父结点或指向空（当T为空时）
{
	if (!T)
	{
		p = f;
		return 0;
	}
	else if (key == T->data)
	{
		p = T;
		return 1;
	}
	else if (key < T->data)
		return (SearchBST(T->lchild, key, T, p));
	else
		return (SearchBST(T->rchild, key, T, p));
}


int InsertBST(BiTree& T, int e)
//在二叉排序树中插入值为elem的元素，T指向二叉排序树根结点
{
	BiTree p = NULL, f = NULL;
	if (!SearchBST(T, e, f, p)) // 如果查找不成功
	{
		BiTree s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e;
		s->lchild = s->rchild = NULL;
		if (!p) // 若二叉树为空被插结点作为树的根结点
			T = s; 
		else if (e< p->data) //被插结点插入到p的左子树中
			p->lchild = s;
		
		else  //被插结点插入到p的右子树中
			p->rchild = s; 
		return 1;
	}
	else // 查找成功,不插
		return 0; 
}

/*非递归中序遍历*/
void InOrderTraverse(BiTree t)
{
	SqStack S;
	InitStack(S);
	BiTree p = t;
	while (p || !StackEmpty(S))
	{
		if (p) {
			Push(S, (int)p);
			p = p->lchild;
		}
		else {
			Pop(S, (int&)p);
			cout << p->data;
			p = p->rchild;
		}
	}


}

int main() {
	int a[10];
	cout << "输入10 个不同整数:" << endl;
	for (int i = 0; i < 10; i++) {
		cin >> a[i];
	}

	BiTree t;


	for (int i = 0; i < 10; i++) {
		InsertBST(t,a[i]);
	}
	InOrderTraverse(t);

	return 0;
}
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
141
142
143
144
145

三、哈希表