java - 如何在二叉搜索树中找到最大对象

Question

嗨，我为 BST 构建了这段代码: 公共(public)类 BinarySearchTreeCode {

private class BSTNode {
    public Object data;
    public BSTNode left;
    public BSTNode right;
    BSTNode(Object newdata) {
        data = newdata;
        left = null;
        right = null;
    }
    BSTNode(Object data, BSTNode left, BSTNode right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public String toString(){
        return "data: "+data+" ";
    }
}


// tree root
private BSTNode root;

public BinarySearchTreeCode(){
    root = null;

}
public BinarySearchTreeCode(BSTNode n){
    root = n;
}

public BinarySearchTreeCode(BinarySearchTreeCode bst){// copy constructor
    this.root = clone(bst.root);
}
BSTNode clone(final BSTNode source){
    if (source == null) return null;
    else
        return  new BSTNode(source.data, clone(source.left), clone(source.right));
}

// compare two objects (integer type)
private static int compare(Object o1, Object o2) {       
    int ans = 0;
    int n1 = (Integer)o1;
    int n2 = (Integer)o2;
    if(n1>n2) ans = 1;
    else if(n1<n2) ans = -1;
    return ans;
}

// insert element to the tree
public void insertRecurs(Object elem) {
    root = insertRecurs(root, elem);
}
BSTNode insertRecurs(BSTNode node, Object elem) {
    if (node == null) {

        return new BSTNode(elem);
    }
    if (compare(elem, node.data) < 0) {
        node.left = insertRecurs(node.left, elem);
        return node;
    }
    else{
        node.right = insertRecurs(node.right, elem);
        return node;
    }
}

// search for element elem
public boolean find(Object elem) {
    return find(root,elem);
}
boolean find(BSTNode tree, Object elem) {
    if (tree == null)
        return false;
    if (compare(elem, tree.data) == 0) 
        return true;
    if (compare(elem, tree.data) < 0)
        return find(tree.left, elem);
    else
        return find(tree.right, elem);
}

// print all tree nodes
public void print() {
    print(" ",root);
    System.out.println();
}
void print(String s,BSTNode tree) {//Inorder
    if (tree != null) {
        print(s+"L ,",tree.left);
        System.out.println(tree.data+" : "+s);
        print(s+"R ,",tree.right);
    }
}
///////////////////////////
public void remove(Object elem) {
    root = remove(root, elem);
}
public static BSTNode remove(BSTNode node, Object n){
    if(node != null){
        if(compare(n,node.data) > 0){
            node.right = remove(node.right,n);
        }
        else if(compare(n,node.data) < 0){
            node.left = remove(node.left,n);
        }
        else{//the node that should be deleted is found
            if(node.left == null && node.right == null){
                node = null;
            }
            else if(node.left != null && node.right == null){//the node has only one child (left)
                node = node.left;
            }
            else if(node.right != null && node.left == null){//the node has only one child (right)
                node = node.right;
            }
            else{//node "tree" has two children
                if(node.right.left == null){// his right node has only one child (right)
                    node.right.left = node.left;
                    node = node.right;
                }
                else{// remove the smallest element
                    BSTNode q, p = node.right;
                    while(p.left.left != null)
                        p = p.left;
                    q = p.left;
                    p.left = q.right;
                    node.data = q.data;
                }
            }
        }
    }
    return node;
}
public void insertLoop(Object elem) {
    BSTNode newNode = new BSTNode(elem);
    if (root == null){
        root = newNode;
    }
    else{
        BSTNode n = root;
        boolean flag = true;
        while (flag){
            if (compare(elem,n.data) > 0){
                if (n.right != null) n = n.right;
                else{
                    n.right = newNode;
                    flag = false;;
                }
            }
            else{
                if (n.left != null) n = n.left;
                else{
                    n.left = newNode;
                    flag = false;;
                }
            }
        }

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

//代码结束

问题是我如何构建一个函数来给出 BNT 中的最大对象，如下所示

公共(public)对象最大值(){

}

有什么建议吗？

感谢您的帮助。

Answer 1

二叉搜索树中的最大对象是最右边的节点。您可以通过以下方式获取:

1)从根节点开始

2)检查node.right是否为空

3) 如果是，则节点是最大对象。终止搜索。

4) 如果没有，则移动到最右边的 nde (node = node.right) 并重复步骤 2。

示例代码:

public BSTNode  findMaxNode()
{
     Node temp = root;
     Node max = null;
     while(temp != null)
     {
        max = temp;
        temp = temp.right
     }

   return max;
}