Java二叉树。打印InOrder遍历
问题描述:
我在打印二叉树的inOrder遍历时遇到了一些问题。即使在树中插入多个项目后,它只会打印3个项目。Java二叉树。打印InOrder遍历
public class BinaryTree {
private TreeNode root;
private int size;
public BinaryTree(){
this.size = 0;
}
public boolean insert(TreeNode node){
if(root == null)
root = node;
else{
TreeNode parent = null;
TreeNode current = root;
while(current != null){
if(node.getData().getValue().compareTo(current.getData().getValue()) <0){
parent = current;
current = current.getLeft();
}
else if(node.getData().getValue().compareTo(current.getData().getValue()) >0){
parent = current;
current = current.getRight();
}
else
return false;
if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
parent.setLeft(node);
else
parent.setRight(node);
}
}
size++;
return true;
}
/**
*
*/
public void inOrder(){
inOrder(root);
}
private void inOrder(TreeNode root){
if(root.getLeft() !=null)
this.inOrder(root.getLeft());
System.out.println(root.getData().getValue());
if(root.getRight() != null)
this.inOrder(root.getRight());
}
}
答
看起来您没有在插入时正确地遍历树,以找到新节点的正确位置。现在,你总是在插入根的一个孩子,因为插入代码是while
循环内 - 它应该是后它:
public boolean insert(TreeNode node){
if(root == null)
root = node;
else{
TreeNode parent = null;
TreeNode current = root;
while(current != null){
if(node.getData().getValue().compareTo(current.getData().getValue()) <0){
parent = current;
current = current.getLeft();
}
else if(node.getData().getValue().compareTo(current.getData().getValue()) >0){
parent = current;
current = current.getRight();
}
else
return false;
}
if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
parent.setLeft(node);
else
parent.setRight(node);
}
size++;
return true;
}
+0
你们是对的。谢谢。 – user69514 2010-04-24 21:51:18
答
您插入的方法有问题。它找到了正确的父节点来附加新的元素,但它在整个树上弄乱了它。您应该将插入代码移出while循环:
public boolean insert(TreeNode node){
if(root == null)
root = node;
else{
TreeNode parent = null;
TreeNode current = root;
while(current != null){
if(node.getData().getValue().compareTo(current.getData().getValue()) <0){
parent = current;
current = current.getLeft();
}
else if(node.getData().getValue().compareTo(current.getData().getValue()) >0){
parent = current;
current = current.getRight();
}
else
return false;
}
if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
parent.setLeft(node);
else
parent.setRight(node);
}
size++;
return true;
}
}
答
哎这里的家伙是一个简单的..尝试了这一点..它适用于我...
public void levelOrderTraversal(Node root){
Queue<Node> queue = new ArrayDeque<Node>();
if(root == null) {
return;
}
Node tempNode = root;
while(tempNode != null) {
System.out.print(tempNode.data + " ");
if(tempNode.left != null) queue.add(tempNode.left);
if(tempNode.right != null) queue.add(tempNode.right);
tempNode = queue.poll();
}
}
这功课吗? – 2010-04-24 21:20:22
我想你可以称它为硬件。我正在对二叉树进行测试,而在序列遍历中可能是其中一个问题。我只是想刷新一些东西。 – user69514 2010-04-24 21:23:21
我强烈建议你没有一个方法,当类也有一个字段'root'时,需要一个参数'root'。这使事情变得非常混乱。 – 2010-04-24 21:24:57