【数据结构与算法】第27篇：二叉排序树（BST

一、二叉排序树的定义1.1 性质二叉排序树Binary Search TreeBST满足以下性质左子树所有节点的值 根节点的值右子树所有节点的值 根节点的值左右子树本身也是二叉排序树示例text50 / \ 30 70 / \ / \ 20 40 60 801.2 特点中序遍历得到递增有序序列查找效率与树高相关平均时间复杂度 O(log n)最坏 O(n)二、节点定义与基本操作2.1 节点结构ctypedef struct BSTNode { int data; struct BSTNode *left; struct BSTNode *right; } BSTNode, *BSTree;2.2 创建节点cBSTNode* createNode(int value) { BSTNode *node (BSTNode*)malloc(sizeof(BSTNode)); node-data value; node-left NULL; node-right NULL; return node; }三、查找操作3.1 递归实现cBSTNode* search(BSTree root, int key) { if (root NULL || root-data key) { return root; } if (key root-data) { return search(root-left, key); } else { return search(root-right, key); } }3.2 非递归实现cBSTNode* searchIter(BSTree root, int key) { BSTNode *cur root; while (cur ! NULL cur-data ! key) { if (key cur-data) { cur cur-left; } else { cur cur-right; } } return cur; }四、插入操作插入新节点一定在叶子节点位置不会改变树的结构。cBSTree insert(BSTree root, int value) { if (root NULL) { return createNode(value); } if (value root-data) { root-left insert(root-left, value); } else if (value root-data) { root-right insert(root-right, value); } // 值相等时根据需求决定通常不插入 return root; }五、删除操作重点5.1 三种情况删除节点需要分三种情况处理情况描述处理方法情况1删除叶子节点直接删除情况2删除只有左子树或只有右子树的节点用子节点替换情况3删除有左右子树的节点用前驱或后继替换再删除前驱/后继5.2 找前驱和后继前驱左子树中最右边的节点最大值后继右子树中最左边的节点最小值text50 / \ 30 70 / \ / \ 20 40 60 80 节点50的前驱40 节点50的后继605.3 删除逻辑用后继替换c// 找最小值节点 BSTNode* findMin(BSTree root) { while (root-left ! NULL) { root root-left; } return root; } // 删除节点 BSTree deleteNode(BSTree root, int key) { if (root NULL) return NULL; // 查找要删除的节点 if (key root-data) { root-left deleteNode(root-left, key); } else if (key root-data) { root-right deleteNode(root-right, key); } else { // 找到要删除的节点 // 情况1 情况2只有一个孩子或没有孩子 if (root-left NULL) { BSTNode *temp root-right; free(root); return temp; } else if (root-right NULL) { BSTNode *temp root-left; free(root); return temp; } // 情况3有两个孩子用后继替换 BSTNode *minNode findMin(root-right); root-data minNode-data; root-right deleteNode(root-right, minNode-data); } return root; }画图理解删除节点50用后继60替换text删除前 50 / \ 30 70 / \ / \ 20 40 60 80 删除后 60 / \ 30 70 / \ \ 20 40 80六、完整代码演示c#include stdio.h #include stdlib.h typedef struct BSTNode { int data; struct BSTNode *left; struct BSTNode *right; } BSTNode, *BSTree; BSTNode* createNode(int value) { BSTNode *node (BSTNode*)malloc(sizeof(BSTNode)); node-data value; node-left NULL; node-right NULL; return node; } // 查找递归 BSTNode* search(BSTree root, int key) { if (root NULL || root-data key) return root; if (key root-data) return search(root-left, key); return search(root-right, key); } // 查找非递归 BSTNode* searchIter(BSTree root, int key) { BSTNode *cur root; while (cur ! NULL cur-data ! key) { if (key cur-data) cur cur-left; else cur cur-right; } return cur; } // 插入 BSTree insert(BSTree root, int value) { if (root NULL) return createNode(value); if (value root-data) root-left insert(root-left, value); else if (value root-data) root-right insert(root-right, value); return root; } // 找最小值 BSTNode* findMin(BSTree root) { while (root-left ! NULL) root root-left; return root; } // 删除 BSTree deleteNode(BSTree root, int key) { if (root NULL) return NULL; if (key root-data) { root-left deleteNode(root-left, key); } else if (key root-data) { root-right deleteNode(root-right, key); } else { // 情况1 2 if (root-left NULL) { BSTNode *temp root-right; free(root); return temp; } else if (root-right NULL) { BSTNode *temp root-left; free(root); return temp; } // 情况3用后继替换 BSTNode *minNode findMin(root-right); root-data minNode-data; root-right deleteNode(root-right, minNode-data); } return root; } // 中序遍历 void inorder(BSTree root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); } // 前序遍历用于看结构 void preorder(BSTree root) { if (root NULL) return; printf(%d , root-data); preorder(root-left); preorder(root-right); } int main() { BSTree root NULL; // 插入节点 int values[] {50, 30, 70, 20, 40, 60, 80}; for (int i 0; i 7; i) { root insert(root, values[i]); } printf(中序遍历有序: ); inorder(root); printf(\n); printf(前序遍历结构: ); preorder(root); printf(\n); // 查找 int key 40; BSTNode *found search(root, key); printf(\n查找 %d: %s\n, key, found ? 找到 : 未找到); // 插入重复值不会插入 root insert(root, 40); printf(插入重复值40后: ); inorder(root); printf(\n); // 删除叶子节点20 root deleteNode(root, 20); printf(\n删除20后: ); inorder(root); printf(\n); // 删除只有一个孩子的节点70 // 先插入一个节点让70只有右孩子 root insert(root, 90); printf(插入90后: ); inorder(root); printf(\n); root deleteNode(root, 70); printf(删除70后: ); inorder(root); printf(\n); // 删除有两个孩子的节点50 root deleteNode(root, 50); printf(删除50后: ); inorder(root); printf(\n); return 0; }运行结果text中序遍历有序: 20 30 40 50 60 70 80 前序遍历结构: 50 30 20 40 70 60 80 查找 40: 找到 插入重复值40后: 20 30 40 50 60 70 80 删除20后: 30 40 50 60 70 80 插入90后: 30 40 50 60 70 80 90 删除70后: 30 40 50 60 80 90 删除50后: 30 40 60 80 90七、删除操作的详细图解以删除根节点50为例text50 ← 要删除 / \ 30 70 / \ / \ 20 40 60 80 步骤1找到后继右子树最小值→ 60 步骤2用60替换50的值 60 / \ 30 70 / \ / \ 20 40 60 80 步骤3删除原来的60节点叶子节点 60 / \ 30 70 / \ \ 20 40 80八、复杂度分析操作平均时间复杂度最坏时间复杂度空间复杂度查找O(log n)O(n)O(1)插入O(log n)O(n)O(1)删除O(log n)O(n)O(1)最坏情况当插入顺序有序时如 1,2,3,4,5BST退化成链表时间复杂度 O(n)。text1 \ 2 \ 3 \ 4九、小结这一篇我们学习了二叉排序树要点说明性质左 根 右中序遍历有序查找递归/非递归O(log n)插入在叶子节点位置插入删除分三种情况重点掌握后继替换缺点可能退化成链表删除的核心逻辑叶子直接删单孩子子节点替换双孩子找后继或前驱替换再删后继下一篇我们讲平衡二叉树AVL树它解决了BST退化成链表的问题。十、思考题为什么BST的中序遍历一定是有序的删除有两个孩子的节点时用前驱替换和用后继替换有什么区别哪种更好如果按升序顺序插入节点BST会变成什么形状时间复杂度是多少尝试实现用前驱替换的删除算法。欢迎在评论区讨论你的答案。