二叉排序树 BST 的查找算法（递归算法）

悠悠 2022-04-17 04:16 200阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

#include <iostream>using namespace std;// BST的结点typedef struct node{  int key; struct node *lChild, *rChild;}Node, *BST;// 在给定的BST插入element, 使之称为新的BSTbool BSTInsert(Node * &p, int element){ if(NULL == p) // 空树 {  p = new Node;  p->key = element;  p->lChild = p->rChild = NULL;  return true; } if(element == p->key) // BST中不能有相等的值  return false; if(element < p->key)  // 递归  return BSTInsert(p->lChild, element); return BSTInsert(p->rChild, element); // 递归}// 建立BSTvoid createBST(Node * &T, int a[], int n){ T = NULL;  int i; for(i = 0; i < n; i++) {  BSTInsert(T, a[i]); }}// BST的查找（递归）Node *BSTSearch(BST T, int x){ if(NULL == T)  return NULL; if(x == T->key)  return T; if(x < T->key)  return BSTSearch(T->lChild, x); return BSTSearch(T->rChild, x);}int main(){ int a[10] = {
        4, 5, 2, 1, 0, 9, 3, 7, 6, 8}; int n = 10; BST T = NULL; // 并非所有的a[]都能构造出BST,所以，最好对createBST的返回值进行判断 createBST(T, a, n);  Node *p = NULL;  int x; // 待查找的x for(x = -10; x < 20; x++) {  p = BSTSearch(T, x);  cout << x << ":";  if(NULL == p)   cout << "no" << endl;  else   cout << "yes" << endl; } return 0;}

结果为：

\-10:no  
\-9:no  
\-8:no  
\-7:no  
\-6:no  
\-5:no  
\-4:no  
\-3:no  
\-2:no  
\-1:no  
0:yes  
1:yes  
2:yes  
3:yes  
4:yes  
5:yes  
6:yes  
7:yes  
8:yes  
9:yes  
10:no  
11:no  
12:no  
13:no  
14:no  
15:no  
16:no  
17:no  
18:no  
19:no  
Press any key to continue

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220417/5ab9b60cf18e4427bdd2265a97117413.png