如何將樹轉換爲線程化二叉樹

-2

我有一個用於創建二叉樹及其遞歸輸出的代碼。如何將二叉樹轉換爲線程樹並迭代打印？如何將樹轉換爲線程化二叉樹

type 
    PAvl = ^TAvl; 
    TAvl = record 
      key: integer; 
      left: PAvl; 
      right: PAvl; 
      isThreaded: boolean; 
     end; 

procedure create(var root: PAvl; digit: integer); 
begin 
    if root = nil then begin 
    New(root); 
    root^.key := digit; 
    root^.left := nil; 
    root^.right := nil; 
    end 
    else if root.key > digit then 
    create(root.left, digit) 
    else 
    create(root.right, digit); 
end; 

procedure Print(root: PNode; depth: integer = 0); 
var 
    i: integer; 
begin 
    if root <> nil then 
    begin 
    Print(root^.right, depth + 1); 
    for i:=1 to depth do 
     Write(#9); 
    Writeln(root^.data); 
    Print(root^.left, depth + 1); 
    end; 
end;

來源

2016-05-30 Alexander Dimov

維基百科有一個很好的解釋：https://en.wikipedia.org/wiki/Threaded_binary_tree – Johan

代碼不是真實的，只是來自兩個來源的混合。 – MBo

答案與您所做的一樣簡單直接。（雙關意圖）你可以事先決定你喜歡哪種遍歷方法。孩子第一或自我第一。然後你做遍歷，建立鏈接。基本上你有一個樹和一個鏈表實現。

更難的問題是保持野獸的平衡。有一個鏈表和節點數有助於這一點。提示，我將使用遞歸函數來查找列表的中間部分，使新葉節點（或者如果沒有節點存在，則爲root），然後將自身從臨時左側鏈和臨時右側鏈中刪除。調用每個臨時鏈上的函數以獲取子節點。

對於大多數不涉及搜索優化的實現，您將希望指向父代，而不是讓節點指向子代。這允許給定父母的任何n個孩子。如果需要，可以將子列表設置爲不齊整的數組或鏈表。所以最後你會將搜索鏈與其他數據結構結合起來以得到你的結果。

當然，另一個問問自己的是實施是否保證將所有內容都保存在內存中。很多時候，如果數據庫存在的話，讓數據庫完成這項工作會更好。

祝福。好問題。

來源

2016-05-31 12:02:47 Michael

如何將樹轉換爲線程化二叉樹

回答

相關問題