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

Question

我需要创建一个未排序的二叉树（一个要求是它是未排序的），它的值是 String。我的 class 大纲如下所示：

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 插入的最佳方法是什么？

我想到了两个办法。第一种是只有两种方法，setLeftNode(Node root, String desc) 和 setRightNode(Node root, String desc)，有人可以用他们选择的 Node 作为根调用。如果已经有 left/right Node，那么它将向下前进，直到它碰到一个没有左 Node 的节点。但这可能会产生超大高度，从而带来问题。

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

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

Answer 1

根据定义，二叉树的最低元素在左边，最高元素在右边。但是，如果你真的希望一切都搞砸（排序），你可以调用一个随机函数，结果为 0 或 1，如果 0 则随机向左，如果 1 向右。这将导致未排序的树

Answer 2

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++;
            }
        }
    }    
}

Answer 3

Eventually I want to be able to replace any node that matches a String description with a new node that has a new description (including duplicates with the old description).

为此，您必须搜索整棵树：

private Node searchBasedOnValue(String desc, Node currentNode)
{  
    Node result = null
    if (currentNode == null)
        return null;
    if (currentNode.getDesc().equals(desc)) 
        return currentNode ;
    if (currentNode.getLeftNode() != null)
        result = searchBasedOnValue(desc,currentNode.getLeftNode());
    if (result == null)
        result = searchBasedOnValue(desc,currentNode.getRightNode());
    return result;
}

IMO，一个常规的 Binary Tree 永远不会被排序，被排序的那个被称为 Binary Search Tree。对于插入，您需要按照您想要的方式进行处理。也许您可以将节点交替插入树的左右子节点，以便它在某种程度上是平衡的。这取决于你如何处理它。

我没有看到常规 Binary Tree 的实际用法，因为大多数时候我们使用 Binary Search Tree，它在插入、删除和查找方面具有更好的性能 (lg(n)) .

Answer 4

如果是未排序的，为什么要构建二叉树呢？不做全盘扫描是搜索不到的，所以你还不如把所有东西都放在一个数组里，访问任何一个元素都是O(n)，因为无法搜索。

Answer 5

这是构建未排序二叉树的最快方法，对其形状没有任何限制：

首先你需要一个这样的构造器：

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

然后像这样构建树：

   Node root = null;
   for (String input: ...) {
      root = new Node(input, root, null);
   }

显然，这会为您提供一个不平衡的、未排序的树，搜索需要查看所有节点。然而，如果树是未排序的，那么树是不平衡的事实没有区别。

一般来说，搜索未排序的树和搜索列表一样复杂，而且代码更复杂。

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

What is the most efficient way to build an unsorted binary tree in java?

java

tree

binary-tree