b.对于这棵树中的节点的节点值
左子树中的所有节点值 a59fd6efdc11065a7592cf00bb3f20b153
后继:在以58为根的bst中第一个大于58的节点->59
当我们使用后继节点时，先连removemin(root.right),在连root.left
treenode successor = findmin(root.right);successor.right = removemin(root.right);successor.left = root.left;
3.完整代码import java.util.nosuchelementexception; /** * 基于整型的 * 普通的二分搜索树 */public class bst { private class treenode{ private int val; private treenode left; private treenode right; public treenode(int val) { this.val = val; } } private int size; private treenode root; /** * 向以root为根的bst中插入一个新的结点val * @param val */ public void add(int val){ root = add(root,val); } private treenode add(treenode root, int val) { if(root == null){ //创建一个新节点 treenode newnode = new treenode(val); size++; return newnode; } //左子树插入 if(val < root.val){ root.left = add(root.left,val); } //右子树插入 if(val > root.val){ root.right = add(root.right,val); } return root; } /** * 判断当前以root为根的bst中是否包含了val * @param val * @return */ public boolean contains(int val){ return contains(root,val); } private boolean contains(treenode root, int val) { if(root == null){ return false; } if(val == root.val){ //找到了 return true; }else if(val < root.val){ //递归左子树查找 return contains(root.left,val); }else{ //递归右子树查找 return contains(root.right,val); } } /** * 找到最小值 * @return */ public int findmin(){ //判空 if(root == null){ //抛出一个空指针异常 throw new nosuchelementexception("root is empty! cannot find min"); } treenode minnode = findmin(root); return minnode.val; } private treenode findmin(treenode root) { //当此节点左子树为空，说明此节点是最小值 if(root.left == null){ return root; } //递归访问左子树 return findmin(root.left); } /** * 找到最大值 * @return */ public int findmax(){ //判空 if(root == null){ throw new nosuchelementexception("root is empty! cannot find max"); } treenode maxnode = findmax(root); return maxnode.val; } private treenode findmax(treenode root) { //当此节点右子树为空，说明此节点是最大值 if(root.right == null){ return root; } //递归访问右子树 return findmax(root.right); } /** * 在当前bst中删除最小值节点，返回删除的最小值 * @return */ public int removemin(){ int min =findmin(); root = removemin(root); return min; } private treenode removemin(treenode root) { if(root.left == null){ treenode right = root.right; //找到最小值，删除节点 root = root.left = null; size--; return right; } root.left = removemin(root.left); return root; } /** * 在当前bst中删除最大值节点，返回删除的最大值 * @return */ public int removemax(){ int max = findmax(); root = removemax(root); return max; } //在当前以root为根的bst中删除最小值所在的节点，返回删除后的树根 private treenode removemax(treenode root) { if(root.right == null){ treenode right = root.right; //找到最大值，删除节点 root = root.right = null; size--; return right; } root.right = findmax(root.right); return root; } /** * 在当前以root为根节点的bst中删除值为val的节点 * 返回删除后的新的根节点 * @return */ public void removevalue(int value){ root = removevalue(root,value); } private treenode removevalue(treenode root, int value) { if(root == null){ throw new nosuchelementexception("root is empty! cannot find remove"); }else if(value < root.val){ root.left = removevalue(root.left,value); return root; }else if(value > root.val){ root.right = removevalue(root.right,value); return root; }else { //此时value == root.value if(root.left == null){ //删除最小数 treenode right = root.right; root = root.right = null; size--; return right; } if(root.right == null){ //删除最大数 treenode left = root.left; root = root.left =null; size--; return left; } //找到当前该删除节点的前驱或者后继节点作为删除后的新节点 //当我们使用后继节点时，先连removemin(root.right),在连root.left treenode successor = findmin(root.right); successor.right = removemin(root.right); successor.left = root.left; return successor; } } @override public string tostring() { stringbuilder sb = new stringbuilder(); generatebststring(root,0,sb); return sb.tostring(); } //直观打印，可以看到树的深度 private void generatebststring(treenode root, int height, stringbuilder sb) { if(root == null){ sb.append(generateheightstring(height)).append("null\n"); return; } sb.append(generateheightstring(height)).append(root.val).append("\n"); generatebststring(root.left,height+1,sb); generatebststring(root.right,height+1,sb); } private string generateheightstring(int height) { stringbuilder sb = new stringbuilder(); for (int i = 0; i < height; i++) { sb.append("--"); } return sb.tostring(); }}
以上就是java如何实现二分搜索树的详细内容。