Java二叉樹。打印InOrder遍歷

Question

我在打印二叉樹的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()); 
    } 



} 

Answer 1

看起來您沒有在插入時正確地遍歷樹，以找到新節點的正確位置。現在，你總是在插入根的一個孩子，因爲插入代碼是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; 
    } 

Answer 2

您插入的方法有問題。它找到了正確的父節點來附加新的元素，但它在整個樹上弄亂了它。您應該將插入代碼移出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; 
    } 
} 

Answer 3

哎這裏的傢伙是一個簡單的..嘗試了這一點..它適用於我...

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