java - 自下而上构建树的问题

Question

我在自下而上构建二叉树时遇到问题。 树的输入将是树的内部节点，该节点的子节点是最终树的叶子。

所以最初如果树是空的，根将是第一个内部节点。

之后，下一个要添加的内部节点将是新根(NR)，旧根(OR)是 NR 的子节点之一。等等。

我遇到的问题是，每当我添加 NR 时，OR 的子项似乎在我进行中序遍历时丢失。事实证明，当我执行 getSize() 调用时，它在 addNode(Tree,Node) 之前和之后返回相同数量的节点

感谢任何解决此问题的帮助

编辑包含节点类代码。 树类和节点类都有 addChild 方法，因为我不太确定将它们放在哪里才能被使用。对此的任何评论也将不胜感激。

代码如下:

import java.util.*;

<p>public class Tree {</p> <pre><code>Node root; int size; public Tree() { root = null; } public Tree(Node root) { this.root = root; } public static void setChild(Node parent, Node child, double weight) throws ItemNotFoundException { if (parent.child1 != null && parent.child2 != null) { throw new ItemNotFoundException("This Node already has 2 children"); } else if (parent.child1 != null) { parent.child2 = child; child.parent = parent; parent.c2Weight = weight; } else { parent.child1 = child; child.parent = parent; parent.c1Weight = weight; } } public static void setChild1(Node parent, Node child) { parent.child1 = child; child.parent = parent; } public static void setChild2(Node parent, Node child) { parent.child2 = child; child.parent = parent; } public static Tree addNode(Tree tree, Node node) throws ItemNotFoundException { Tree tree1; if (tree.root == null) { tree.root = node; } else if (tree.root.getSeq().equals(node.getChild1().getSeq()) || tree.root.getSeq().equals(node.getChild2().getSeq())) { Node oldRoot = tree.root; oldRoot.setParent(node); tree.root = node; } else { //form a disjoint tree and merge the 2 trees tree1 = new Tree(node); tree = mergeTree(tree, tree1); } System.out.print("addNode2 = "); if(tree.root != null ) { Tree.inOrder(tree.root); } System.out.println(); return tree; } public static Tree mergeTree(Tree tree, Tree tree1) { String root = "root"; Node node = new Node(root); tree.root.setParent(node); tree1.root.setParent(node); tree.root = node; return tree; } public static int getSize(Node root) { if (root != null) { return 1 + getSize(root.child1) + getSize(root.child2); } else { return 0; } } public static boolean isEmpty(Tree Tree) { return Tree.root == null; } public static void inOrder(Node root) { if (root != null) { inOrder(root.child1); System.out.print(root.sequence + " "); inOrder(root.child2); } } </code></pre> <p>}</p>

公共(public)类节点{

Node child1;
Node child2;
Node parent;
double c1Weight;
double c2Weight;
String sequence;
boolean isInternal;

public Node(String seq) {
    sequence = seq;
    child1 = null;
    c1Weight = 0;
    child2 = null;
    c2Weight = 0;
    parent = null;
    isInternal = false;
}

public boolean hasChild() {
    if (this.child1 == null && this.child2 == null) {
        this.isInternal = false;
        return isInternal;
    } else {
        this.isInternal = true;
        return isInternal;
    }
}

public String getSeq() throws ItemNotFoundException {
    if (this.sequence == null) {
        throw new ItemNotFoundException("No such node");
    } else {
        return this.sequence;
    }
}

public void setChild(Node child, double weight) throws ItemNotFoundException {
    if (this.child1 != null && this.child2 != null) {
        throw new ItemNotFoundException("This Node already has 2 children");
    } else if (this.child1 != null) {
        this.child2 = child;
        this.c2Weight = weight;
    } else {
        this.child1 = child;
        this.c1Weight = weight;
    }
}
public static void setChild1(Node parent, Node child) {
    parent.child1 = child;
    child.parent = parent;
}

public static void setChild2(Node parent, Node child) {
    parent.child2 = child;
    child.parent = parent;
}

public void setParent(Node parent){
    this.parent = parent;
}

public Node getParent() throws ItemNotFoundException {
    if (this.parent == null) {
        throw new ItemNotFoundException("This Node has no parent");
    } else {
        return this.parent;
    }
}

public Node getChild1() throws ItemNotFoundException {
    if (this.child1 == null) {
        throw new ItemNotFoundException("There is no child1");
    } else {
        return this.child1;
    }
}

public Node getChild2() throws ItemNotFoundException {
    if (this.child2 == null) {
        throw new ItemNotFoundException("There is no child2");
    } else {
        return this.child2;
    }
}

Answer 1

只看附加的代码，找不到显式调用的 setChild，只有 setParent。如果您还附加了 setParent 的代码，那么我们可以确认该方法是否也创建了从父级到子级的反向链接。

我的猜测是 setParent 不会 setChild，在这种情况下，到子项的链接并没有丢失:它们从一开始就没有创建。

//编辑后:

好的，现在可以确认 setParent 不会 setChild，所以您一开始就没有创建这些链接。您应该增加以下形式的所有调用:

someNode.setParent(otherNode);

还有:

otherNode.setChild(someNode);

---

其他备注:

• setChild 可以通过调用 setChild1 和 setChild2 来减少重复。
• 在 setChild 中可以免费使用哪个链接的逻辑是正确的，但令人困惑，即“如果另一个不免费，则使用这个”，而不是更直接的“如果这个是免费的，就用它吧。”
• 养成在尽可能小的范围内声明和使用局部变量的习惯，例如addNode 中的 tree1 可以在使用它的一个 block 内声明。事实上，它甚至可以完全从代码中写出来，例如tree = merge(tree, new Tree(node));.
• 只是您应该确认的事情:node.getChild1().getSeq() 是否容易导致抛出 NullPointerException？
  • //编辑后:好的，它会抛出 ItemNotFoundException。在任何一种情况下，您在 addNode 中的原始条件都是错误的，因为您不能保证两个子节点都存在(因为那样您将无法向其添加子节点)。
• //after edit: 为什么要将 Tree 中 Node.setChild* 的功能复制为 static 方法...然后两者都不使用？