在二叉排序树中查找指定的关键字,并在查找过程中输出查找过程中历经的节点typedef int KeyType; typedef struct node { KeyType key; struct node *lchild,*rchild; } BSTNode; int ReadData(int a[]); BSTNode *CreatBST(KeyType A[],int n); int SearchBST(BSTNode *bt,KeyType k) ;
时间: 2024-01-30 19:02:36 浏览: 28
下面是二叉排序树中查找指定关键字的代码:
```c++
#include <iostream>
using namespace std;
typedef int KeyType;
typedef struct node {
KeyType key;
struct node *lchild,*rchild;
} BSTNode;
// 读入数据
int ReadData(int a[]) {
int n;
cout << "请输入数组长度:";
cin >> n;
cout << "请输入数据:";
for (int i = 0; i < n; i++) {
cin >> a[i];
}
return n;
}
// 创建二叉排序树
BSTNode *CreatBST(KeyType A[],int n) {
BSTNode *root = NULL; // 根节点初始化为空
for (int i = 0; i < n; i++) {
BSTNode *p = root; // 从根节点开始遍历
BSTNode *prev = NULL;
while (p != NULL) {
prev = p;
if (A[i] < p->key) {
p = p->lchild;
} else {
p = p->rchild;
}
}
// 找到插入位置
BSTNode *newNode = new BSTNode;
newNode->key = A[i];
newNode->lchild = NULL;
newNode->rchild = NULL;
if (prev == NULL) {
root = newNode; // 根节点为空时,直接插入
} else if (A[i] < prev->key) {
prev->lchild = newNode;
} else {
prev->rchild = newNode;
}
}
return root;
}
// 在二叉排序树中查找指定关键字
int SearchBST(BSTNode *bt, KeyType k) {
BSTNode *p = bt; // 从根节点开始查找
int depth = 0;
while (p != NULL) {
depth++; // 统计遍历的层数
if (p->key == k) {
cout << "查找成功,共遍历了" << depth << "层" << endl;
return 1;
} else if (k < p->key) {
p = p->lchild;
} else {
p = p->rchild;
}
}
cout << "查找失败" << endl;
return 0;
}
int main() {
int a[100];
int n = ReadData(a);
BSTNode *bt = CreatBST(a, n);
KeyType k;
cout << "请输入要查找的关键字:";
cin >> k;
SearchBST(bt, k);
return 0;
}
```
这段代码中,`CreatBST` 函数用于创建二叉排序树,`SearchBST` 函数用于在二叉排序树中查找指定关键字。在查找过程中,统计每次遍历的层数,输出查找成功或失败的信息及遍历的层数。