将节点插入java中的二叉树问题

Question

即时通讯从C++到java，我很困惑与java的二叉树。有一个Node类是使它成为内部静态类的唯一方法？我看到的所有例子都是这样做的。然而，我这样做的方式是我有一个节点类和二元树类使用此节点类。但是当我尝试在第二次插入后插入树中时，我不断收到错误。我在这条线上得到一个例外if(dataIn <= nodeIn.getLeft().getData()){

我很困惑，我做错了什么....这里是我的代码插入，我有。在此先感谢..

public void insert(int dataIn){ 
    root = insert(root, dataIn); 
} 

private Node insert(Node nodeIn, int dataIn){ 
    if(nodeIn==null){ 
     nodeIn = new Node(null, null, dataIn); 
    }else{ 
     if(dataIn <= nodeIn.getLeft().getData()){ 
      nodeIn.setLeft(insert(nodeIn.getLeft(), dataIn)); 
     }else{ 
      nodeIn.setRight(insert(nodeIn.getRight(), dataIn)); 
     } 
    } 

    return nodeIn; 
} 

Answer 1

您需要测试是否nodeIn.getLeft() == null。

Answer 2

是唯一能让Node类成为内部静态类的方法吗？我看到的所有例子都是这样做的。

号

Node类不需要是内或嵌套类。 （严格来说，“静态内部”类是嵌套类。）

但是，只有内部类或嵌套类可以是private。如果您的Node类是常规类，那么您将实现细节公布给（至少）同一个包中的其他类。这是一个糟糕的主意......这就解释了为什么你会看到Node类被声明为这样。

Answer 3

令人困惑的部分原因是“Node”不应该是插入方法的参数，您应该调用在节点中定义的插入方法。

因此，假设您在“正常代码”中持有“根”节点 - 我们称其为“rootNode”，只是为了模糊。

好了，你的代码插入到树将是：

rootNode.insert(newValue); 

很容易的。

现在定义该方法。

public class Node { 
    private int value; 
    private Node lower; 
    private Node higher; 

    public void insert(int newValue) { 
     if (newValue < value) 
      if(lower == null) 
       lower=new Node(value); 
      else 
       lower.insert(newValue); 
     else 
      if(higher == null) 
       higher=new Node(value); 
      else 
       higher.insert(newValue); 
     } 

// and you'll need a constructor 
    public Node(int value) { 
     this.value=value; 
    } 
} 

这应该更清楚。我要打“Post”，然后我要编辑它，并弄清楚如何轻松折射这个邪恶的邪恶副本&粘贴代码。

第二个想法，我会留在那里，因为它更具可读性。我能看到的最好的解决方法是使节点的数组，然后你：

public class Node { 

    private int value; 
    private Node[] nodes=new Node[2]; 
    private final int LOWER=0; 
    private final int HIGHER=1; 

    public void insert(int newValue) { 
     int index=LOWER; 
     if (newValue > value) 
      index=HIGHER; 

     if(nodes[index] == null) 
      nodes[index]=new Node(value); 
      else 
       nodes[index].insert(newValue); 
     } 
    } 

但我不会取代原来的，因为，正如我所说，它更清晰。

我推荐这本重构书。一旦你真的得到面向对象，它确实有助于简化你的代码。将一个对象传递给静态方法（不使用成员变量的方法）是一种无用的方式。

关于@ ted的评论和OO的更多考虑 - getLeft和getRight不应该成为问题。在抽象之外不是必需的。

一般来说你可能需要在节点这些方法：

public boolean doesContain(int value) { 
    if(value == this.value) 
     return true 
    else 
     return nodes[ this.value < value ? LOWER : HIGHER].doesContain(value); 
} 

，也许

public void getValuesSorted(LinkedList l) { 
    nodes[LOWER].getValuesSorted(l); 
    l.put(value); 
    nodes[HIGHER].getValuesSorted(l); 
} 

然后，你甚至都不需要公开，它是你正在处理与 - 一棵树 - 拜托OO抽象。

Answer 4

相反的：

if (dataIn <= nodeIn.getLeft().getData()) { 

...你想：

if (dataIn < nodeIn.getData()) { 

，则需要比较是与在当前节点的值被插入的值。

我将<=标志更改为<标志，以避免重复。

所以你重构的代码是：

public void insert(int dataIn) { 
    root = insert(root, dataIn); 
} 

private Node insert(Node nodeIn, int dataIn){ 
    if (nodeIn == null) { 
    nodeIn = new Node(null, null, dataIn); 
    } else { 
    if (dataIn < nodeIn.getData()) { 
     nodeIn.setLeft(insert(nodeIn.getLeft(), dataIn)); 
    } else { 
     nodeIn.setRight(insert(nodeIn.getRight(), dataIn)); 
    } 
    } 
    return nodeIn; 
} 

Answer 5

您的所有解决方案都没有考虑到accoount如果节点是树的中间插入会发生什么。你假设它也是最小的或最大的。当你在树的中间插入一些东西时，你会意识到操作变得更加复杂。

Answer 6

您可以使用下面的代码来清除您的理解。大多数情况下，我们不使用任何其他类，一切都可以在单个Node类本身内完成。这里是一个非常基本的例子，我认为这可能会有帮助...另外，当我看到你有两种方法只提供数据而不是根。相信我，最好是在你的主课堂上有根。推理我们有它方便我们需要缓存的地方。

public Node insert(Node root, Node newNode) { 
if (root == null) { 
    root = newNode; 
} else { 
    if(root.data > newNode.data) { 
     root.left = insert(root.left, newNode); 
    } else { 
     root.right = insert(root.right, newNode); 
    } 
} 
return root; 

}

直接从已初始化的任何类调用此方法。这里是一个样本PLZ检查..

Node root = new Node(10); 
    root.insert(root, new Node(5)); 
    root.insert(root, new Node(3)); 
    root.insert(root, new Node(6)); 
    root.insert(root, new Node(1)); 

Answer 7

实际上，对于二叉树没有必要检查插入元素是否或者是大于或左比父节点。我认为没有必要检查这些条件。我们必须从用户那里输入是右键还是左键。

Answer 8

public class TreeNode 
{ 
    private int data; 
    private TreeNode left; 
    private TreeNode right; 

    public Tree() 
    { 
     data = 0; 
     left = null; 
     right = null; 
    } 

    public Tree(int initialInfo, TreeNode initialLeft, TreeNode initialRight) 
    { 
     data = initialInfo; 
     left = initialLeft; 
     right = initialRight; 
    } 

    public void setLeft(TreeNode newLeft) 
    { 
     left = newLeft; 
    } 

    public void setRight(TreeNode newRight) 
    { 
     right = newRight; 
    } 

    public void insert(int element) 
    { 
     if(element <= data) 
     { 
      if(left == null) 
       setLeft(new TreeNode(element, null, null)); 
      else 
       left.insert(element); 
     } 
     else 
     { 
      if(right == null) 
       setRight(new TreeNode(element, null, null)); 
      else 
       right.insert(element); 
     } 
    } 

}