將二進制樹轉換爲雙向鏈表

-1

我想在java中編寫一個函數來將二叉樹轉換爲DLL。該函數執行沒有錯誤，但該DLL沒有被創建。以下是功能。 root是指向樹根的指針，並且頭指向DLL的起始節點。將二進制樹轉換爲雙向鏈表

public void dll(Node x) 
    { 

     if(x==null) 
     { 
      return; 
     } 
     else 
     { 
      if(x==root) 
      { 
       Node temp=root; 
       while(temp.left!=null) 
       { 
        temp=temp.left; 
       } 
       head=temp; 
      } 

      if(x.left!=null) 
      { 
       System.out.println(x.data); 

       Node lchild=x.left; 
       Node rightmost=lchild; 
       while(rightmost.right!=null) 
       { 
        rightmost=rightmost.right; 
       } 
       x.left=rightmost; 
       rightmost.right=x; 
       dll(lchild); 

      } 
      if(x.right!=null) 
      { 
       System.out.println(x.data); 

       Node rchild=x.right; 
       Node leftmost=rchild; 

       while(leftmost.left!=null) 
       { 
        leftmost=leftmost.left; 
       } 

       x.right=leftmost; 
       leftmost.left=x; 
       dll(rchild); 
      } 




     } 

    } 
}

的邏輯如下：查找左子樹的最右邊，併爲根的前一個節點，找到最左邊的右子樹，並使其未來的根。遞歸應用於子樹。

enter image description here

當我嘗試打印head.right，它給我空指針異常。 153

Exception in thread "main" java.lang.NullPointerException 
     at BTtoDll.main(BTtoDll.java:153)

線是 -

System.out.println(t.head.right.data);

來源

2014-02-21 nitinsh99

所以我從你的標籤瞭解你正在得到一個NPE？你可以用完整的堆棧跟蹤它嗎？ – m0skit0

可能重複[什麼是空指針異常？]（http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception） –

這是一個邏輯錯誤，不是NPE。請停止downvoting。我錯過了我的邏輯中的東西，這就是爲什麼節點沒有正確連接，其他明智的權利不應該是空的，我知道什麼是NPE，我不明白爲什麼權利爲零 – nitinsh99

其實純遞歸函數的作用是相同的：最右邊的連接x的左子樹和x連接到右側子樹的最左側。 我以爲你可能有興趣看到一致性。

public DLL dll(Node x) { 
    return dll(null, x, null); 
} 

public DLL dll(DLL before, Node x, DDL after) { 
    if (x == null) { 
     return; 
    } 
    if (x.left != null) { 
     before = dll(before, x.left, null); 
    } 
    if (x.right != null) { 
     after = dll(null, x.left, after); 
    } 
    DLL result = new DLL(); 
    result.insert(x.value); 
    result.insertBefore(before); // null being a no-op. 
    result.insertAfter(after); // null being a no-op. 
    return result; 
}

正如人們可以看到的那樣，有幾種變化是可以想象的。

來源

2014-02-21 17:27:53

在這裏，您分配x.left和x.right到x：

if(x.left!=null) 
{ 
    ... 
    rightmost=x; 
    x.left=rightmost; 
    ... 
} 
if(x.right!=null) 
{ 
    ... 
    leftmost=x; 
    x.right=leftmost; 
    ... 
}

我不能告訴它應該是說什麼去改變它但這可能是你的錯誤。該列表不會重新鏈接。

來源

2014-02-21 17:10:13 Radiodef

嗨，謝謝我根據你的答案和其他答案在這裏改變了代碼。但是現在我的代碼沒有終止，如果條件不成立，我無法找出原因。 – nitinsh99

至於你NullPointerException，我認爲

  while(leftmost!=null)

應該

  while(leftmost.left!=null)

來源

2014-02-21 17:25:55 Ray

將二進制樹轉換爲雙向鏈表

回答

相關問題