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 方法...然后两者都不使用？