二叉搜索树（BST）

1、什么是BST(Binary Search Tree)二叉搜索树也叫二叉搜索树或二叉排序树其核心的递归性质如下对于树中任意一个节点该节点左子树中所有节点的值 当前节点值该节点右子树中所有节点的值 当前节点值左、右子树本身也必须是二叉搜索树一般BST不允许重复关键字如果有需要应当添加约定将重复值统一 放在左子树 / 右子树中。2、BST的具体实现依据BST的性质我们可以构建一个BST并实现一些常用的基础操作· 节点定义#include stdio.h #include stdlib.h typedef struct bstNode { int val; struct bstNode* left; struct bstNode* right; }bstNode;· 创建节点并插入bstNode* create_bstNode(int val) { bstNode* node malloc(sizeof(bstNode)); if (!node) { perror(malloc); exit(EXIT_FAILURE); } node-val val; node-left NULL; node-right NULL; return node; } bstNode* bstInsert(bstNode *root,int val) { if (!root) return create_bstNode(val); //如果当前节点为空则直接插入 if (val root-val) root-left bstInsert(root-left, val); //若val小于节点值则在节点的左子树中插入 else if (val root-val) root-right bstInsert(root-right, val); //若val大于节点值则在节点的右子树中插入 /* 相等则不插入 */ return root; }· 注这里插入一下perror的头文件与原型为#include stdio.h void perror(const char *s);其作用是打印自定义字符串s再紧跟一个冒号并自动读取全局变量errno系统最近一次调用出错的错误码将错误码翻译成对应的文字错误描述一并输出到标准错误 (stderr)。exit的头文件与原型为#include stdlib.h void exit(int status);exit的核心作用是终止整个当前进程退出程序。exit(0)表示程序正常结束exit(非0)则表明程序异常退出用来告知系统出错类型。stdlib.h中还声明了#define EXIT_SUCCESS 0 #define EXIT_FAILURE 1· 删除节点bstNode* findMIN(bstNode* root) //找到最小值 { while (root-left) root root-left; return root; } bstNode* bstDelete(bstNode *root,int val) { if (!root) return NULL; if (val root-val) root-left bstDelete(root-left, val); else if (val root-val) root-right bstDelete(root-right, val); else { /* S1叶子节点 */ if (!root-left !root-right) { free(root); return NULL; } /* S2只有右孩子 */ if (!root-left) { bstNode* tmp root-right; free(root); return tmp; } /* S3只有左孩子 */ if (!root-right) { bstNode* tmp root-left; free(root); return tmp; } /* S4左右孩子都有 */ bstNode* tmp findMIN(root-right); root-val tmp-val; root-right bstDelete(root-right, tmp-val); } return root; }· findMIN根据BST的性质找最小值只需要一直找到最左侧的叶子节点即可。· bstDeleteBST的删除会稍微复杂一些下面梳理一下我个人的想法。函数bstDelete可以描述为“永远返回当前递归所处理的这颗子树的新根”。在递归过程中只有找到被删除值的那层递归会直接执行删除操作其余递归层则会根据子树的新的根节点更新自己的左 / 右孩子指针并返回自身作为当前子树的新根。因此在main中调用时会写成root bstDelete(root val);S1——待删除节点是叶子节点叶子那一层返回了NULL表示这棵叶子子树不存在了父节点把对应的孩子指针置为NULL随后父节点返回自己这时更高层次的结构不会发生变化。S2、S3——待删除节点只有一个子节点 / 子树释放当前节点并返回其唯一的子节点作为当前子树的新根。S4——待删除节点有两个子节点 / 子树通过findMIN(root-right)找到当前节点右子树的最小值即当前节点的中序后继节点用后继节点的值覆盖当前节点然后在当前节点的右子树中递归删除后继节点而由于后继节点一定没有左孩子因此此次删除必定退化为S1或S2。· 查找节点bstNode* bstSearch(bstNode* root, int val) { if (!root) return NULL; if (root-val val) return root; if (val root-val) return bstSearch(root-left, val); return bstSearch(root-right, val); }该函数的返回结果是待查值val的节点。· 中序遍历void Inorder(bstNode* root) { if (!root) return; Inorder(root-left); printf(%d ,root-val); Inorder(root-right); }作为一颗BST其中序遍历一定是升序的在测试时也可根据此判断构建的BST是否正确。· 删除整棵树void bstFree(bstNode *root) { if (!root) return; bstFree(root-left); bstFree(root-right); free(root); //注意要先free孩子节点再free父节点 }