掌握二叉搜索树：高效查找与有序遍历

一、先解答上次的思考题对这棵树10 / \ 20 30 \ 40层序遍历10 20 30 40树的高度3二、今天学习目标什么是二叉搜索树 BSTBST 三个核心规则实现查找、插入、中序遍历完整可运行代码三、什么是二叉搜索树 BSTBinary Search Tree带 “查找规则” 的二叉树。三个铁律若左子树不为空左子树所有节点 根节点若右子树不为空右子树所有节点 根节点左、右子树也都是 BST一句话小的放左边大的放右边。特点中序遍历结果一定是递增有序序列查找效率远高于普通链表四、示例 BST5 / \ 3 6 / \ \ 2 4 7中序遍历2 3 4 5 6 7有序五、完整代码BST 查找 插入 中序遍历#include stdio.h #include stdlib.h // BST 节点 struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; }; // 创建节点 struct TreeNode* createNode(int val) { struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode)); node-data val; node-left NULL; node-right NULL; return node; } // 1. 插入 struct TreeNode* insert(struct TreeNode* root, int val) { if (root NULL) { return createNode(val); } if (val root-data) { root-left insert(root-left, val); } else if (val root-data) { root-right insert(root-right, val); } // 相等不插入 return root; } // 2. 查找 struct TreeNode* search(struct TreeNode* 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. 中序遍历输出有序 void inOrder(struct TreeNode* root) { if (root NULL) return; inOrder(root-left); printf(%d , root-data); inOrder(root-right); } // 主函数测试 int main() { struct TreeNode* root NULL; // 插入数据 int arr[] {5,3,6,2,4,7}; int n sizeof(arr)/sizeof(arr[0]); for (int i 0; i n; i) { root insert(root, arr[i]); } printf(BST 中序遍历有序); inOrder(root); // 查找 4 struct TreeNode* res search(root, 4); if (res ! NULL) { printf(\n找到节点%d, res-data); } else { printf(\n未找到); } return 0; }六、运行结果BST 中序遍历有序2 3 4 5 6 7 找到节点4七、BST 核心总结规则小左大右中序 有序递增查找 / 插入平均复杂度O(log n)最坏退化成链表O(n)八、今日小练习依次插入10 7 15 3 9 12 18输出中序遍历结果查找 9 是否存在答案中序3 7 9 10 12 15 18查找 9存在