问题与构建树自下而上

Question

我有从底部向上构建二叉树的问题。 树的输入将与这个节点是最终的树的叶子的孩子树内部节点。

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

此后，待添加的下一个内部节点将是新的根（NR），与旧的根（OR）为NR的孩子之一。等等。

这个问题我有是，每当我添加一个NR时，OR的孩子似乎当我做了序遍历丢失。这被证明是这样的，当我做

以解决此问题的任何帮助表示赞赏

与编辑的的getSize（）调用，它返回相同数量的前ADDNODE后节点（树节点）包含节点类代码。 树和节点类都有addChild方法，因为我不太确定将它们放在哪里以便它被占用。对此的任何评论也将不胜感激。

的代码如下：

import java.util.*;

public class Tree {

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); 

    } 
} 

}

公共类节点{

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使用的逻辑是正确的，但令人困惑，即“如果另外一个是不自由，则使用这一个”，而不是更直截了当：“如果这个人是自由，公正用它”。
• 是否有习惯在最小范围内声明和使用局部变量，例如： tree1在addNode可以在它使用的一个块内声明。实际上，它甚至可以完全从代码中写出，例如tree = merge(tree, new Tree(node));。
• 只是你应该确认一下：是node.getChild1().getSeq()容易造成NullPointerException被抛出？
  • //编辑后：好的，它抛出ItemNotFoundException代替。无论哪种情况，您在addNode中的原始状况都是错误的，因为您无法保证两个孩子都存在（因为您无法为其添加孩子）。
• //后编辑：你为什么要在Tree为static方法复制的Node.setChild*功能......然后不使用要么？