C语言实现二叉查找树（BST）的基本操作
38 浏览量
2020-12-22
16:03:39
上传
评论
收藏 52KB PDF 举报
C语言实现二叉查找树（语言实现二叉查找树（BST）的基本操作）的基本操作
我们在上一篇博客中讲解了二叉树，这一次我们来实现二叉树的进阶——二叉查找树（Binary Search Tree），又称二插
排序树(Binary Sort Tree)。所以简称为BST。二插查找树的定义如下：
1.若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
2.若右子树不为空，则右子树上所有节点的值均大于它的根节点的值；
3.左右子树也分别为二叉排序树；
二叉排序树的一个重要特点是中序遍历是一个递增序列。示例代码上传至：
https://github.com/chenyufeng1991/BinarySearchTree 。
（1）节点的构造
typedef int elemType;
typedef struct BTNode{
int data;
struct BTNode *lChild;
struct BTNode *rChild;
}BiTNode，*BiTree;
（2）创建二叉树
创建二插排序树的过程是一个不断插入节点的过程，并且重要的是查找插入的合适位置。
//创建二叉查找树
/**
* 输入-1时创建结束，其实是一个不断插入的过程
*/
int CreateBinarySearchTree(BiTree *T){
printf("请输入创建二叉查找树的数字序列：
");
int num;
scanf("%d"，&num);
while (num != -1) {
Insert(T，num);
scanf("%d"，&num);
}
printf("%s函数执行，二叉查找树创建成功
"，__FUNCTION__);
return 1;
}
（3）插入节点
//插入节点
void Insert(BiTree *T，int x){
//这里创建一个要插入的节点
BiTNode *pInsert = (BiTNode *)malloc(sizeof(BiTNode));
pInsert->data = x;
pInsert->lChild = NULL;
pInsert->rChild = NULL;
if ((*T) == NULL) {
*T = pInsert;
}
if ((*T)->lChild == NULL && x < (*T)->data) {
(*T)->lChild = pInsert;
}
if ((*T)->rChild == NULL && x > (*T)->data) {
(*T)->rChild = pInsert;
}
//递归实现
if (x < (*T)->data) {
Insert(&(*T)->lChild， x);
}
if (x > (*T)->data) {
Insert(&(*T)->rChild， x);
}
return;
}
（4）树的中序遍历和先序遍历
树的先序遍历+中序遍历可以的确定一棵树。并且二叉排序树的中序遍历必定是一个递增的序列。用这样的方法可以来验
证我们对一颗二叉排序树进行操作后是否正确。
//中序遍历二叉查找树
//打印的应该是一个递增的序列
void MiddleOrder(BiTree T){
评论0