我有从底部向上构建二叉树的问题。 树的输入将与这个节点是最终的树的叶子的孩子树内部节点。问题与构建树自下而上
所以最初如果树为空的根将是第一个内部节点。
此后,待添加的下一个内部节点将是新的根(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;
}
}
}
为了防万一它有所作为,我们可以看到'Node.setParent'吗? – polygenelubricants 2010-04-08 03:17:54
我需要看看'Node.getSeq()'和相关的方法。你用这个来检查平等吗?为什么不使用==? – John 2010-04-08 03:24:28