Java二叉树。打印顺序遍历
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2706181/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Binary Tree. Printing InOrder traversal
提问by user69514
I am having some problems printing an inOrder traversal of my binary tree. Even after inserting many items into the tree it's only printing 3 items.
我在打印二叉树的 inOrder 遍历时遇到了一些问题。即使在向树中插入许多项目后，它也只打印 3 个项目。
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());
}
}
采纳答案by Péter T?r?k
It seems that you are not traversing the tree properly upon insertion, to find the right place for the new node. Right now you are always inserting at one child of the root, because the insertion code is inside the whileloop - it should be afterit:
似乎您在插入时没有正确遍历树，以找到新节点的正确位置。现在你总是在根的一个孩子处插入，因为插入代码在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;
}
回答by FRotthowe
You insert method has a problem. It finds the right parent node to attach the new element to, but on the way it messes up the whole tree. You should move the insertion code out of the while loop:
你的插入方法有问题。它找到了将新元素附加到的正确父节点，但在途中它弄乱了整个树。您应该将插入代码移出 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;
}
}
回答by Vrajendra Singh Mandloi
hey fellows here is one simple one.. try this out.. it works for me well...
嘿伙计这里是一个简单的..试试这个..它对我很有效......
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();
}
}
