数据结构与算法—二叉排序树详解( 三 ) _二叉排序树

如果这个节点是最底层我们很好考虑，可以直接替换值，然后将最底层的点删除即可。但是如果这个节点有左枝。我们该怎么办？

这个分析起来也不难，用递归的思想啊。我们删除这个节点，用可以满足的节点替换了。会产生什么样的后果？

文章插图

多出个用过的19节点，转化一下，在左子树中删除19的点！那么这个问题又转化为删除节点的问题，查找左子树中有没有能够替代19这个点的。

所以整个删除算法流程为：

文章插图

代码为
public node remove(int x, node t)// 删除节点 {if (t == null) {return null;}if (x < t.value) {t.left = remove(x, t.left);} else if (x > t.value) {t.right = remove(x, t.right);} else if (t.left != null && t.right != null)// 左右节点均不空{t.value = https://www.isolves.com/it/rj/czxt/linux/2019-08-19/findmin(t.right).value;// 找到右侧最小值替代t.right = remove(t.value, t.right);} else // 左右单空或者左右都空{if (t.left == null && t.right == null) {t = null;} else if (t.right != null) {t = t.right;} else if (t.left != null) {t = t.left;}return t;}return t; }完整代码
二叉排序树完整代码为：
package 二叉树;import JAVA.util.ArrayDeque;import java.util.Queue;import java.util.Stack;public class BinarySortTree { class node {// 结点public int value;public node left;public node right;public node() {}public node(int value) {this.value = https://www.isolves.com/it/rj/czxt/linux/2019-08-19/value;this.left = null;this.right = null;}public node(int value, node l, node r) {this.value = value;this.left = l;this.right = r;} } node root;// 根 public BinarySortTree() {root = null; } public void makeEmpty()// 变空 {root = null; } public boolean isEmpty()// 查看是否为空 {return root == null; } public node findmin(node t)// 查找最小返回值是node，调用查看结果时需要.value {if (t == null) {return null;} else if (t.left == null) {return t;} elsereturn (findmin(t.left)); } public node findmax(node t)// 查找最大 {if (t == null) {return null;} else if (t.right == null) {return t;} elsereturn (findmax(t.right)); } public boolean isContains(int x)// 是否存在 {node current = root;if (root == null) {return false;}while (current.value != x && current != null) {if (x < current.value) {current = current.left;}if (x > current.value) {current = current.right;}if (current == null) {return false;} // 在里面判断如果超直接返回}// 如果在这个位置判断是否为空会导致current.value不存在报错if (current.value == x) {return true;}return false; } public node insert(int x)// 插入 t是root的引用 {node current = root;if (root == null) {root = new node(x);return root;}while (current != null) {if (x < current.value) {if (current.left == null) {return current.left = new node(x);}else current = current.left;}else if (x > current.value) {if (current.right == null) {return current.right = new node(x);}else current = current.right;}}return current;//其中用不到 } public node remove(int x, node t)// 删除节点 {if (t == null) {return null;}if (x < t.value) {t.left = remove(x, t.left);} else if (x > t.value) {t.right = remove(x, t.right);} else if (t.left != null && t.right != null)// 左右节点均不空{t.value = findmin(t.right).value;// 找到右侧最小值替代t.right = remove(t.value, t.right);} else // 左右单空或者左右都空{if (t.left == null && t.right == null) {t = null;} else if (t.right != null) {t = t.right;} else if (t.left != null) {t = t.left;}return t;}return t; }}结语