計算BST的內部路徑長度只能從預訂或後序遍歷

Question

您好StackOverflow社區！

我想弄清楚如何計算BST的內部路徑長度只給予前序或後序遍歷（它應該沒有多大的區別）而不構造樹;也就是說，我只想使用上面提到的遍歷之一。這對你們大多數人來說可能是一個簡單的答案，但正如你可能已經認爲我在樹上很新的東西。

那麼任何想法是表示讚賞和感謝。

Answer 1

如果我瞭解您的問題，則可能無法完成。考慮兩棵樹

A   A 
/\  | 
B C  B 
      | 
      C 

這些具有相同的序遍歷（ABC），但不同的內部路徑長度（2和3）。

Answer 2

在http://geeksforgeeks.org/?p=6633有一個頁面，它討論瞭如何從其前序和有序遍歷中構建一棵樹。在這裏，因爲你的樹是一棵搜索樹，所以你有隱式的順序遍歷（使用鍵的排序順序）。您可以使用像該站點那樣的遞歸算法來計算每個樹節點的級別（無需構建樹），然後將這些級別一起添加以獲取內部路徑長度。該算法可能不是最有效的，因爲它在遍歷上搜索以找到每個節點的正確子節點，但它應該起作用。這是一個關於如何做一個單通算法（假設所有的按鍵都不同）我最好的猜測：

int internal_path_length(key_iter& cur_node, key_iter end, int level, key max_key) { 
    if (cur_node == end) return 0; 
    key cur_key = *cur_node; 
    if (cur_key > max_key) return 0; 
    ++cur_node; 
    int len1 = internal_path_length(cur_node, end, level + 1, cur_key); 
    int len2 = internal_path_length(cur_node, end, level + 1, max_key); 
    return len1 + len2 + level; 
} 

開始：

key_iter i = preorder.begin(); 
internal_path_length(i, preorder.end(), 0, mk); 

其中mk比最大可能的密鑰較大的樹。

Answer 3

既然它是一個BST，我們就隱式地遍歷樹（排序的元素列表）。

我們可以創建一個獨特的樹只從預購或後序遍歷 前將[R，更少的元件則R的名單，元素更大的則R列表] 發表會[則R元素少的列表，列表的元素大於R，R]

僞代碼將如下所示。

findIPLPreOrder(poArray,startIndex,endIndex, height) { 
    if(startIndex==endIndex){ 
      retrn height; 
    } 
    m=findIndexOfEndofLeftSubTree(poArray,start,end); 
    return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);  
} 

findIndexOfEndofLeftSubTree(poArray,start,end){ 
    R=poArray[start] 
    for(i=start+1;i<=end;i++){ 
    if(R < poArray[i]){ 
     return i-1; 
     } 
    } 
}