数据结构第七章查找-树表的查找(二叉排序树的查找)

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct
{
char key;
}ElemType;
typedef struct BSTNode
{
ElemType data;
struct BSTNode* rchild,* lchild;
}BSTNode,*BSTree;
//插入元素
BSTree InsertBST(BSTree T, char key)
{
if (T == NULL)
{
T = (BSTree)malloc(sizeof(BSTNode));
T->data.key = key;
T->lchild = T->rchild = NULL;
}
else if (key < T->data.key)
{
T->lchild = InsertBST(T->lchild, key);
}
else {
T->rchild = InsertBST(T->rchild, key);
}
return T;
}
//查找函数
BSTree SearchBST(BSTree T, char key)
{
if (T == NULL || T->data.key == key)
{
return T;
}
else if (key < T->data.key)
{
return SearchBST(T->lchild, key);
}
else
{
return SearchBST(T->rchild, key);
}
}
//打印
void printBST(BSTree T)
{
if (T)
{
printBST(T->lchild);
printf("%c ", T->data.key);
printBST(T->rchild);
}
}
//释放空间
void FreeBST(BSTree T)
{
if (T)
{
free(T->lchild);
free(T->rchild);
free(T);
}
}
int main()
{
BSTree root = NULL;
char keys[] = {'D','B','A','C','E','F'};
int n = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < n; i++)
{
root = InsertBST(root, keys[i]);
}
printf("打印如下\n");
printBST(root);
printf("\n");
char keyNum = 'C';
BSTree result = SearchBST(root, keyNum);
if (result)
{
printf("找到了 %c 在BST中\n", result->data.key);
}
else
{
printf("找不到 %c 在BST中\n",keyNum);
}
FreeBST(root);
return 0;
}

书本也提出了查找函数使用非递归方法，但是书本只给出了查找算法函数的代码，下面是使用非递归算法实现二叉排序查找

BSTree SearchBST(BSTree T, char key)
{
while (T != NULL)
{
if (key == T->data.key)
{
return T;
}
else if (key < T->data.key)
{
T = T->lchild;
}
else
{
T = T->rchild;
}
}
return NULL;
}

原文地址：https://blog.csdn.net/2305_78057683/article/details/143577497

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！