二叉樹中排名的總和 - 有沒有更好的方法

Question

也許這個問題不屬於，因爲這本身不是一個編程問題，如果是這樣的話，我會道歉。

我只是在抽象的數據結構考試，並有這樣的疑問：

樹節點的等級的定義是這樣的：如果你是樹的根，你的等級是0。否則，您的排名是您父母的排名+1。

設計一種算法來計算二叉樹中所有節點的排名總和。你的算法的運行時間是多少？

我的回答，我相信可以解決這個問題，我的僞代碼是這樣的：

int sum_of_tree_ranks(tree node x) 
{ 
    if x is a leaf return rank(x) 
    else, return sum_of_tree_ranks(x->left_child)+sum_of_tree_ranks(x->right_child)+rank(x) 
} 

其中函數排名是

int rank(tree node x) 
{ 
    if x->parent=null return 0 
    else return 1+rank(x->parent) 
} 

這很簡單，一棵樹的行列總和是左子樹+右子樹+根的和的總和。

我相信這個算法的運行時間是n^2。我相信這是因爲我們沒有給出二叉樹是平衡的。可能是樹中有n數字，但也有n不同的「級別」，如在樹中看起來像鏈接列表而不是樹。所以要計算一片葉子的等級，可能我們會逐步提高。葉的父親將n-1臺階等...所以多數民衆贊成在n+(n-1)+(n-2)+...+1+0=O(n^2)

我的問題是，這是正確的？我的算法能解決問題嗎？我對運行時的分析是否正確？最重要的是，有沒有更好的解決方案來解決這個問題，那不在n^2中運行？

Answer 1

算法的工作原理。你的分析是正確的。這個問題可以在O（n）的時間來解決：（自行照顧葉）

int rank(tree node x, int r) 
{ 
    if x is a leaf return r 
    else 
     return rank(x->left_child, r + 1)+ ranks(x->right_child, r + 1) + r 
} 
rank(tree->root, 0) 

Answer 2

它可以O(n)時間，其中n is number of Nodes二叉樹來解決。
這只是根節點高度爲零的所有節點的高度的總和。 作爲

算法：用左，右孩子 輸入二叉樹
總和= 0;
輸出總和

PrintSumOfrank(root,sum): 
if(root==NULL) return 0; 
return PrintSumOfrank(root->lchild,sum+1)+PrintSumOfRank(root->Rchild,sum+1)+sum; 

編輯：
這可以是也使用隊列或遍歷樹的級別順序來解決。
算法使用隊列：

int sum=0; 
int currentHeight=0; 
Node *T; 
Node *t1; 
if(T!=NULL) 
enque(T); 
while(Q is not empty) begin 
currentHeight:currentHeight+1 ; 
for each nodes in Q do 
    t1 = deque(); 
if(t1->lchild!=NULL)begin 
    enque(t1->lchild);sum = sum+currentHeight; 
end if 
if(t1->rchild!=NULL)begin 
    enque(t1->rchild);sum = sum+currentHeight; 
end if 
end for 
end while 
print sum ; 

Answer 3

你是正確的，但有一個爲O（n）解決方案爲您提供可以使用更「複雜」的數據結構。 讓每個節點保持其等級和更新的行列，只要你添加/刪除，這樣你可以使用O（1）聲明：

return 1 + node->left.rank + node->right.rank; 

，並做到這一點的每個節點上的樹實現Ø （n）。

減少複雜性時拇指規則是：如果你能複雜的數據結構和增加新的功能，以使其適應你的問題，你可以複雜時間減少到O（n）的大部分的時間。