InOrder遍歷進入無限循環，只打印第一個節點

我試圖編寫一段簡單的代碼來遍歷二叉搜索樹，使用inorder traversal.I能夠完美地調整插入代碼，因爲調試器完全顯示了一棵樹就像我wanted.But我遞歸遍歷心不是給予了正確的results.Here是我的調試器的截圖：InOrder遍歷進入無限循環，只打印第一個節點

左子樹，然後右子樹

Left

Right Subtree

其對應於以下的可視化樹：

Binary Tree

打印出所有節點代替，它只是打印在一個無限循環的第一元件（39）。這裏是我的代碼： Main.java

public class Main { 

public static void main(String[] args) { 
    BinaryTree binaryTree = new BinaryTree(); 
    binaryTree.add(50); 
    binaryTree.add(40); 
    binaryTree.add(39); 
    binaryTree.add(42); 
    binaryTree.add(41); 
    binaryTree.add(43); 
    binaryTree.add(55); 
    binaryTree.add(65); 
    binaryTree.add(60); 
    binaryTree.inOrderTraversal(binaryTree.root); 
} 
}

Node.java

public class Node { 
int data; 
Node left; 
Node right; 
Node parent; 


public Node(int d) 
{ 
    data = d; 
    left = null; 
    right = null; 
} 
}

BinaryTree.java

public class BinaryTree { 
Node root = null; 
public void add(int d) 
{ 
    Node newNode = new Node(d); 
    if(root!=null) 
    { 


     Node futureParent = root; 
     while(true) 
     { 
     if(newNode.data < futureParent.data)  //going left 
     { 
      if(futureParent.left == null) 
      { 
       futureParent.left = newNode; 
       newNode.parent = futureParent; 
       break; 
      } 
      futureParent = futureParent.left; 

     } 
     else 
     { 
      if(futureParent.right == null) 
      { 
       futureParent.right = newNode; 
       newNode.parent = futureParent; 
       break; 
      } 
      futureParent = futureParent.right; 
     } 

     } 

    } 
    else 
    { 
     root = newNode; 
    } 
} 
public void inOrderTraversal(Node node) 
{ 
    while(node!=null) 
    { 
    inOrderTraversal(node.left); 
    System.out.println(node.data); 
    inOrderTraversal(node.right); 
    } 
} 
}

來源

2014-02-27 parth

你不需要的，而（）循環inOrderTraversal（）。這是一個遞歸調用。它造成了無盡的循環。

但是，你確實需要一些東西來阻止遞歸。只有節點不爲空時纔會遞歸。

public void inOrderTraversal(Node node) { 
    if(node==null) return; 

    inOrderTraversal(node.left); 
    System.out.println(node.value); 
    inOrderTraversal(node.right); 
}

來源

2014-02-27 05:02:20 anonymous

我試圖按照[這]（http://www.newthinktank.com/2013/03/binary-tree-in-java/）教程。我幾乎寫了完全相同的方式。可以打擾你，但是你能告訴我爲什麼while循環適用於他的代碼而不適用於我的代碼？ – parth

@zigtones我看到他的代碼，它沒有一個while循環。你在尋找合適的地方嗎？我看着公共無效inOrderTraverseTree（Node focusNode）; – anonymous

有時當我被困住時，我只是看不到東西。無論如何非常感謝幫助我的伴侶。 – parth

當您使用遞歸時，您應該記住基本情況，減少的問題和一般解決方案。

這裏的基本情況是：if node == null，stop recursion。減少的問題是：應該能夠訪問任何單個左/父/右節點一般解決方案是：訪問左側，訪問節點，訪問權限。

所以，你的代碼應該是：

public void lnrTraverse(Node node) { 
    //if (node == null) return; //This is not needed. Valid only if it an empty tree 
    if (node.left != null) { 
     lnrTraversal(node.left); 
    } 
    System.out.println(node); 
    if (node.right != null) { 
     lnrTraversal(node.right); 
    } 
}

來源

2014-02-27 05:22:04 Amudhan

InOrder遍歷進入無限循環，只打印第一個節點

回答

相關問題