数据结构 (一), BST 二叉搜索树 (1)，app 可视化开发工具

1. 查找

• 先查找根节点,

• < 根, 则找左子树;

• > 根, 则找右子树;

• = 根, 则找到返回;

算法时间复杂度 对于 n 个节点的树

• 最优 f(n) = 需要查找的次数 = 二叉树的层数 ~= O(logn)

• 最差 f(n) = 需要查找的次数 = 二叉树的层数 = n = O(n)

public Node search(int num) {return doSearch(root, num);}

private Node doSearch(Node root, int num) {if (root == null) {return null;}

if (root.data == num) {return root;} else if (root.data > num) {return doSearch

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

(root.left, num);} else if (root.data < num) {return doSearch(root.right, num);}return null;}

2. 插入

• 比对根节点, 小于就往左节点比对, 大于就往右节点比对

• 直到需要比对的节点为空, 而这个空就是你需要插入的位置

算法时间复杂度:

• 最优 f(n) = 需要比对的次数 = 二叉树的层数 ~= O(logn)

• 最差 f(n) = 需要查找的次数 = 二叉树的层数 = n = O(n)

public void insert(int num) {root = doInsert(root, num);}

private Node doInsert(Node parent, int num) {if (parent == null) {parent = new Node(num);} else if (num > parent.data) {parent.right = doInsert(parent.right, num);} else if (num < parent.data) {parent.left = doInsert(parent.left, num);}

return parent;}

3. 删除

• 先查找到目标节点

• 若: 目标左子树为空, 则, 用目标右子树根节点替换目标

• 若: 目标右子树为空, 则, 用目标左子树根节点替换目标

• 若: 都不为空, 则, 选取左子树值最大节点或者右子树最小节点替换目标, 并, 递归删除替换目标的节点

public void remove(int num) {root = doRemove(root, num);}

private Node doRemove(Node parent, int num) {

if (parent == null) {return null;}

if (num > parent.data) {parent.right = doRemove(parent.right, num);} else if (num < parent.data) {parent.left = doRemove(parent.left, num);}// 找出左子树最大的值或者右子树最小的值替换, 这里选择前者来实现 else if (parent.left != null && parent.right != null) {

// 找到左子树最大值替换 parent.data = findMax(parent.left).data;