查找

2023-10-07   


顺序查找

算法思想:
最直观的查找方法,从线性表的一段开始,逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足条件,则查找成功;若已经查找到表的另一端,还没有查找到符合条件的元素,则返回失败信息。

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

折半查找

算法思想:
首先将给定值key与表中中间位置的元素比较,若相等,则查找成功,返回该元素位置。若不相等,则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内就行进行同样的查找,如此重复,直到找到位置,或确定表中没有所需要查找的元素。(仅适合有序数组)

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

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

算法思想:
设置二叉树的平衡标记为balance,已返回二叉树T是否为平衡二叉树
若为平衡二叉树,则返回1,否则返回0;h为二叉树T的高度。
采用后序遍历的递归算法:

  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*t,根据结点存储的信息,有以下几种情况。

  • t>lchildt->lchild为空时
    1. t>rchildt->rchild非空且k==1k==1,则t*t为第kk小的元素
    2. t>rchildt->rchild非空且k!=1k!=1,则第kk小的元素必在t*t的右子树
  • t>lchildt->lchild不为空时
    1. t>lchild>count==k1t->lchild->count==k-1, t*t为第kk小元素
    2. t>lchild>count>k1t->lchild->count>k-1,第kk小元素必在t*t的左子树中,继续到t*t的左子树中查找
    3. t>lchild>count<k1t->lchild->count<k-1,第kk小元素必在t*t的右子树中,继续搜索右子树,寻找第k(t>lchild>count+1)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.