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

文章插图

主要方法

既然已经构造号一棵树，那么就需要实现主要的方法。因为二叉排序树中每个节点都能看作一棵树。所以我们创建方法的是时候加上节点参数(也就是函数对每一个节点都能有效)

findmax(),findmin()
findmin()找到最小节点：

因为所有节点的最小都是往左插入，所以只需要找到最左侧的返回即可。

findmax()找到最大节点：

因为所有节点大的都是往右面插入，所以只需要找到最右侧的返回即可。
代码使用递归函数

public node findmin(node t)//查找最小返回值是node，调用查看结果时需要.value{ if(t==null) {return null;} else if(t.left==null) {return t;} else return(findmin(t.left)); }public node findmax(node t)//查找最大{ if(t==null) {return null;} else if(t.right==null) {return t;} else return(findmax(t.right)); }

文章插图

isContains(int x)
这里的意思是查找二叉查找树中是否存在x 。

假设我们我们插入x，那么如果存在x我们一定会在查找插入路径的过程中遇到x 。因为你可以如果已经存在的点，再它的前方会走一次和它相同的步骤。也就是说前面固定，我来1w次x，那么x都会到达这个位置。那么我们直接进行查找比较即可！

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=https://www.isolves.com/it/rj/czxt/linux/2019-08-19/=x) {return true;}return false;}【数据结构与算法—二叉排序树详解】insert(int x)
插入的思想和前面isContains类似。找到自己的位置(空位置)插入。但是又不太一样。你可能会疑问为什么不直接找到最后一个空，然后将current赋值过去current=new node(x) 。这样的化current就相当于指向一个new node(x)节点。和树就脱离关系，所以要提前判定是否为空，若为空将它的left或者right赋值即可。
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;//其中用不到}

比如说上面结构插入51

文章插图

delete(int x)
删除操作算是一个相对较难理解的操作了。
删除节点规则：

先找到这个点。这个点用这个点的子树可以补上的点填充该点，然后在以这个点为头删除替代的子节点（调用递归）然后在添加到最后情况（只有一个分支，等等）。
首先要找到移除的位置，然后移除的那个点分类讨论，如果有两个儿子，就选右边儿子的最左侧那个点替代，然后再子树删除替代的那个点。如果是一个节点，判断是左空还是右空，将这个点指向不空的那个。不空的那个就替代了这个节点。入股左右都是空，那么他自己变空null就删除了。

删除的节点没有子孙: