在java中构建未排序的二叉树的最有效方法是什么？

Question

我需要创建一个未排序的二叉树(一个要求是未排序),它保存一个String值作为其值.我的班级大纲看起来像这样:

public class Node {

 private String desc;
 private Node leftNode = null;
 private Node rightNode = null;

 public Node(String desc) {
  this.desc = desc;
 }

 public String getDesc() {
  return desc;
 }

 public Node getLeftNode() {
  return leftNode;
 }

 public Node getRightNode() {
  return rightNode;
 }
}

最终,我希望能够将具有String描述的任何节点替换为具有新描述的新节点(包括具有旧描述的重复节点).

所以我的问题是,Node在创建未排序的二叉树时,处理s 的插入的最佳方法是什么？

我想到了两种方式.第一种方法是只有两种方法,setLeftNode(Node root, String desc)而且setRightNode(Node root, String desc)有人可以用Node自己选择的方式作为根.如果已经有一个左/右Node,那么它将向前推进直到它击中一个没有左边的节点Node.但这可能通过产生超大的高度来引入问题.

我想到的第二种方式是拥有一个专用的根Node,在这种情况下是第一个Node创建的,然后Node按顺序构建新的.

那么创建未排序的二叉树的最佳方法是什么？

Answer 1

public class BinaryTree{
    private BinaryTree right;
    private BinaryTree left;
    private String data;        

    public BinaryTree(String s){
        data = s;
        right = null;
        left = null;           
    }

    public void setLeft (BinaryTree l){ left  = l; }
    public void setRight(BinaryTree r){ right = r; }        
}

您的问题表明树应该是平衡的，因此在插入元素时，您应该递归检查树每一侧的节点数：

public int checkTree(){
    if(left == null && right == null){
        return 1;
    }else if(left == null){
        return 1 + right.checkTree();
    }else if(right == null){
        return 1 + left.checkTree();
    }else{
        return 1 + left.checkTree() + right.checkTree();
    }
}

public void insert(BinaryTree bt){
    if(left == null){
        setLeft(bt);
    }else if(right == null){
        setRight(bt);
    }else{
        if(left.checkTree() <= right.checkTree()){
            left.insert(bt);
        }else{
            right.insert(bt);
        }
    }
}

编辑：

public class BinaryTree {
    private BinaryTree right;
    private BinaryTree left;
    private String data;
    private int weight;

    public BinaryTree(String s){
        data = s;
        right = null;
        left = null; 
        weight = 1;
    }    

    public void setLeft (BinaryTree l){ 
        left  = l;
        weight++;
    }

    public void setRight(BinaryTree r){
        right = r;
        weight++;
    } 

    public int getWeight(){ return weight; }

    public void insert(BinaryTree bt){
        if(left == null){
            setLeft(bt);
        }else if(right == null){
            setRight(bt);
        }else{
            if(left.getWeight() <= right.getWeight()){
                left.insert(bt);
                weight++;
            }else{
                right.insert(bt);
                weight++;
            }
        }
    }    
}