# 查找

2023-10-07

### 顺序查找

int search(int a[], int key) {
for (int i = 0; i < len; i ++) {
if (a[i] == key) {
return i;
}
}
return -1;
}


### 折半查找

int Binary_Search(int a[], int key) {
int low = 0, high = len - 1, mid;
int mid = (low + high) / 2;
while(low <= high) {
mid = (low + high) / 2;
if (a[mid] == x)
return mid;
else if(a[mid] > x)
r = mdi - 1;
else
l = mid + 1;
}
return -1;
}


### 二叉排序树

BiTree BST_Search(BiTree T, char key) {
if (T->data == key)
return T;
if (T->data > key)
return BST_Search(T->lchild, key);
else
return BST_Search(T->rchild, key);
}


BiTree BST_Search(BiTree T, char key) {
while(T != NULL && key != T->data) {
if (key < T->data)
T = T->lchild;
else
T = T->rchild;
}
return T;
}


int BST_Insert(BiTree &T, char key) {
if (T == NULL) {
//原树为空，新插入的记录为根节点
T = new BiTNode;
T -> data = key;
T -> lchild = T -> rchild = NULL;
return 1; 	//插入成功
} else if (key == T->data) {	//已经存在，插入失败
return 0;
} else if (key < T-> data) {	//插入到左子树
return BST_Insert(T->lchild, key);
} else {	//插入到右子树
return BST_Insert(T->rchild, key);
}
}


#### 写出折半查找的递归算法

int BinserachRec(int a[], int key, int low, int high) {
if (low > high) {
return 0;
}
mid = (low + high) / 2;
if (key > a[mid]) {
BinserachRec(a, key, mid + 1, high);
}
else if (key <a[mid]) {
BinserachRec(a, key, low, mid - 1);
}
else
return mid;
}


#### 判断二叉树是否是二叉排序树

int predt = -32767;
bool JudgeBST(BiTree T) {
bool left, right;
if (T == NULL)	//空树
return true;
else {
left = JudgeBST(T->lchild);
//若左子树返回值为假，或者前驱大于等于当前结点，不是二叉排序树
if (!left || predt >= T->data) {
return false;
}
predt = T->data;
right = JudgeBST(T->rchild);
return right;
}
}


#### 求二叉排序树的层次

int LevelBST(BiTree T, BiTNode *p) {
int n = 0;
BiTree t = T;
if (T != NULL) {
n ++;
while(t -> data != p -> data) {
if (p -> data < t -> data)
t = t -> lchild;
else
t = t -> rchild;
n ++;
}
}
return n;
}


#### 利用二叉树遍历思想，判断二叉树是否是平衡二叉树

1. 若T为空，则高度为0，balance=1
2. 若T仅有根节点，则高度为1，balance=1
3. 否则，对T的左右子树执行递归操作，返回左右子树的高度和平衡标记，T的高度为最高子树和最低子树加1。若左右子树高度差大于1，则balance=0；若左右子树的高度差小于或等于1，且左右子树都平衡时balance=1，否则balance=0
void Judge_AVL(BiTree T, int &balance, int &h) {
int bl = 0, br = 0, hl = 0, hr = 0;
if (T == NULL) {
h = 0;
balance = 1;
}
else if (T -> lchild == NULL && T -> rchild == NULL) {
h = 1;
balance = 1;
} else {
Judge_AVL(T->lchild, bl, hl);
Judge_AVL(T->rchild, br, hr);
h = (hl > hr ? hl : hr) + 1;
if (abs(hl - hr) < 2)
balance = bl && br;
else
balance = 0;
}
}


#### 求出给定二叉排序树中最大和最小的关键字

int findMin(BiTree T) {
while(T -> lchild != NULL) {
T = T -> lchild;
}
return T->data;
}

int findMax(BiTree T) {
while(T -> rchild != NULL) {
T = T -> rchild;
}
return T->data;
}


#### 从大到小输出二叉排序树中所有不小于k的关键字

void OutPut(BiTree T, int k) {
if (T == NULL)
return ;
if (T -> rchild != NULL)
OutPut(T->rchild, k);
if (T->data >= k) {
cout << T->data << " ";
}
if (T->lchild != NULL) {
OutPut(T->lchild, k);
}
}


#### 编写一个递归算法，在一颗n个结点的、随机建立的二叉排序树上查找第k小元素，并返回该结点的指针

• $t->lchild$为空时
1. $t->rchild$非空且$k==1$，则$*t$为第$k$小的元素
2. $t->rchild$非空且$k!=1$，则第$k$小的元素必在$*t$的右子树
• $t->lchild$不为空时
1. $t->lchild->count==k-1$, $*t$为第$k$小元素
2. $t->lchild->count>k-1$，第$k$小元素必在$*t$的左子树中，继续到$*t$的左子树中查找
3. $t->lchild->count，第$k$小元素必在$*t$的右子树中，继续搜索右子树，寻找第$k-(t->lchild->count+1)$小的元素
BiTNode *Search_Small(BiTree t, int k) {
if (k < 1 || k > t -> count)
return NULL;
if (t -> lchild == NULL) {
if (k == 1)	return t;
else 	return Search_Small(t->rchild, k-1);
}
else {
if (t->lchild->count == k - 1)
return t;
if (t->lchild->count > k - 1)
return Search_Small(t->lchild, k);
if (t->lchild->count <k - 1)
return Search_Small(t->rchild, k - (t->lchild-count+1));
}
}


Q.E.D.