二叉树 -- 二叉排序树
2019-05-07 本文已影响0人
TomyZhang
一、概念
二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),也称二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值。
- 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
二、数据结构
struct BinaryTreeNode {
int id;
BinaryTreeNode *left, *right;
};
三、相关操作
- 二叉排序树插入
- 二叉排序树查找
- 二叉排序树删除
四、实现
#include<stdio.h>
#include<malloc.h>
struct BinaryTreeNode {
int id;
BinaryTreeNode *left, *right;
};
BinaryTreeNode* mallocBinaryTreeNode() {
BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
return node;
}
BinaryTreeNode* searchBST(BinaryTreeNode *node, int id) { //递归搜索,返回搜索结果结点
if(node == NULL) { //搜索不到目标结点,返回空结点
return NULL;
}
if(id == node->id) { //搜索到目标结点,返回该结点
return node;
} else if(id < node->id) {
return searchBST(node->left, id); //递归搜索左子树,返回搜索结果结点
} else {
return searchBST(node->right, id); //递归搜索右子树,返回搜索结果结点
}
}
BinaryTreeNode* insertBST(BinaryTreeNode *node, int id) { //递归插入,返回根节点
if(node == NULL) { //当前结点为空,新结点即为根结点,返回该结点
node = mallocBinaryTreeNode();
node->left = NULL;
node->right = NULL;
node->id = id;
return node;
}
if(id < node->id) {
node->left = insertBST(node->left, id); //递归插入左子树,返回根结点
} else {
node->right = insertBST(node->right, id); //递归插入右子树,返回根结点
}
return node; //返回根结点
}
BinaryTreeNode* deleteBST(BinaryTreeNode *node, int id) { //递归删除,返回根结点
if(node == NULL) { //当前结点为空,返回空结点
return NULL;
}
if (id < node->id) {
node->left = deleteBST(node->left, id); //递归删除左子树,返回根结点
} else if(id > node->id) {
node->right = deleteBST(node->right, id); //递归删除右子树,返回根结点
} else {
if(node->left != NULL && node->right != NULL) { //待删除的结点有两个孩子结点
BinaryTreeNode *p = node->right; //寻找当前结点的后继结点
while(p->left != NULL) {
p = p->left;
}
node->id = p->id;
node->right = deleteBST(node->right, p->id); //递归删除右子树,返回根结点
} else if(node->left == NULL && node->right == NULL){ //待删除的结点无孩子结点
node = NULL;
} else if(node->right == NULL) { //待删除的结点只有左孩子结点
BinaryTreeNode *p = node;
node = node->left;
free(p);
} else { //待删除的结点只有右孩子结点
BinaryTreeNode *p = node;
node = node->right;
free(p);
}
}
return node;
}
void createBinaryTree(BinaryTreeNode *root) { //创建二叉排序树
int n = 7;
int data[100] = {4, 2, 5, 1, 3, 7, 6};
root->id = 4;
root->left = NULL;
root->right = NULL;
for(int i = 1; i < n; i++) {
insertBST(root, data[i]);
}
}
void preOrder(BinaryTreeNode *node) { //先序遍历二叉树
if(node == NULL) {
return;
}
printf("%d ", node->id);
preOrder(node->left);
preOrder(node->right);
}
void main() {
BinaryTreeNode root;
createBinaryTree(&root);
preOrder(&root);
printf("\n");
BinaryTreeNode *p = searchBST(&root, 5);
if(p != NULL) {
printf("search %d\n", p->id);
} else {
printf("search null\n");
}
deleteBST(&root, 7);
preOrder(&root);
printf("\n");
}