java - 二叉搜索树 insert() 和 removeMin()

Question

这是我的 BinaryTree.java :

public abstract class BinaryTree<T> {

public BinaryTree<T> root = null;
//
public T key = null;
public BinaryTree<T> left = null;
public BinaryTree<T> right = null;

public boolean isEmpty() {
    return root == null;
}

public String toString() {
    return canonical();
}

public String canonical() {
    return canonical(root);
}

public String canonical(String comment) {
    System.out.println("______" + comment + "______");
    return canonical(root);
}

static final String ROOT_LEFT = "(";
static final String ROOT_RIGHT = ")";
static final String ROOT_SEP = "-";

public String canonical(BinaryTree<T> t) {
    if (t == null) {
        return ".";
    }
    String str = "";
    if (t.left != null) {
        str += canonical(t.left);
    }
    str += ROOT_SEP + t.key + ROOT_SEP;
    if (t.right != null) {
        str += canonical(t.right);
    }
    return ROOT_LEFT + str + ROOT_RIGHT;
}

public void treeView(String comment) {
    BinaryTreeView<T> btw = new BinaryTreeView<T>(comment, root, 400, 400);
    btw.refresh();
}


public void treePrint(String comment) {
    System.out.println("______" + comment + "______");
    if (isEmpty())
        System.out.println("Empty tree");
    else
        treePrint(root, 0);
}

protected void treePrint(BinaryTree<T> t, int depth) {
    String space = "";
    for (int i = 0; i < depth; i++) {
        space += "   ";
    }
    if (t != null) {
        int d = ++depth;
        treePrint(t.right, d);
        System.out.println(space + "/");
        System.out.print(space + "-");
        System.out.println(t.key);
        System.out.println(space + "\\");
        treePrint(t.left, d);
    } else {
        System.out.println(space + ".");
    }
}

// treeView
public int getHeight() {
    int lH = -1;
    int rH = -1;

    if (left != null) {
        lH = left.getHeight();
    }
    if (right != null) {
        rH = right.getHeight();
    }
    return Math.max(rH, lH) + 1;
}
}

还有我的SearchTree.java:

public class SearchTree extends BinaryTree<String> {

public SearchTree(String key) {
    this.key = key;
    this.left = null;
    this.right = null;
    root = this;
}

public void insert(String key) {
// I need help for this part!
}

private void insert(BinaryTree<String> tree, String key) {
// I need help for this part!
}


 void removeMin() { // I am not sure if this is true!
 if (this.root.left == null) {
 root = root.right;
 } else
 removeMin(this.root.left, this.root);
 }

 void removeMin(BinaryTree<String> current, BinaryTree<String> previous) {
 if (current.left == null) {
 previous.left = current.right;
 return;
} else
 removeMin(current.left, current);
 }

}

你能帮我解决 SearchTree.java 中的 insert() 和 removeMin() 方法吗？我在 removeMin() 方法中尝试了一些东西，但我不确定它是否正确。

而且我不知道如何使用 insert() 方法向这个结构中插入一个新节点。

编辑:测试用例

TEST:   bst_insert_1
description:    Add 1-node tree
Correct:    (-b5-)
Yours:      (-b5-)
2   SUCCESS

TEST:   bst_insert_2
description:    Add 2-node tree, insert left
Correct:    ((-b4-)-b5-)
Yours:      (-b5-)
0   FAILED

TEST:   bst_insert_3
description:    Add 2-node tree, insert right
Correct:    (-b5-(-b6-))
Yours:      (-b5-)
0   FAILED

TEST:   bst_insert_4
description:    Add 2-node tree, insert right, left
Correct:    ((-b4-)-b5-(-b6-))
Yours:      (-b5-)
0   FAILED

TEST:   bst_insert_5
description:    Add 2-node tree, insert right, left, left-left
Correct:    (((-b2-)-b4-)-b5-(-b6-))
Yours:      (-b5-)
0   FAILED

TEST:   bst_insert_6
description:    Add to empty tree
Correct:    (-b4-)
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_1
description:    Remove 1-node tree, (-b5-)
Correct:    .
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_2
description:    Remove 2-node tree, ((-b4-)-b5-)
Correct:    (-b5-)
Yours:      (-b5-)
2   SUCCESS

TEST:   bst_removeMin_3
description:    Remove 2-node tree, (-b5-(-b6-))
Correct:    (-b6-)
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_4
description:    Remove 3-node tree, (-b5-((-b6-)-b7-))
Correct:    ((-b6-)-b7-)
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_5
description:    Remove 2-node tree, (-5-(-7-(-b-)))
Correct:    (-b7-(-b8-))
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_6
description:    Remove 2-node tree, (((-b2-)-b3-)-b5-)
Correct:    ((-b3-)-b5-)
Yours:      (-b5-)
0   FAILED

TEST:   bst_removeMin_7
description:    Remove 2-node tree,((-b3-(-b4-))-b5-)
Correct:    ((-b4-)-b5-)
Yours:      (-b5-)
0   FAILED

Answer 1

我不会给出 insert 的答案.但是看看 removeMin，据我所知，它是正确的，可能有助于通过使用“技巧”找到解决方案:

最小值在最左边的 child 中。如果使用递归，您可以使用函数 result 而不是添加 previous 参数。这简化了理解:

void removeMin() {
    root = removeMinSubtree(root);
}

/**
 * Post-condition: result is the same subtree, possibly minus
 * the minimum element when not empty.
 */
private BinaryTree<String> removeMinSubtree(BinaryTree<String> subtree) {
    if (subtree == null) {
        return null; // Cannot remove.
    } else if (subtree.left == null) {
        return right; // Remove left-most child.
    } else {
        subtree.left = removeMin(subtree.left);
        return subtree;
    }
}

案例越少，不变条件越容易看出left < value < right正在维护中。

对于 insert您可能还想使用返回值而不是参数。

顺便说一句。 class BinaryTree<T extends Comparable<T>>所以可以使用 compareTo将用于具有值(value)比较的一般解决方案。