具有給定級別的節點的二叉樹數量

我需要編寫一個程序來計算從二進制樹中給定的某個級別的節點數量。具有給定級別的節點的二叉樹數量

我的意思是< numberofnodes（INT級）{}>

我想沒有任何成功寫它，因爲我沒有怎麼去到一定水平，然後去計算節點的數量。

來源

2010-05-17 sadatwins

這是家庭作業3級節點的數量？你到目前爲止嘗試過什麼？ – Johnsyweb 2010-05-17 22:03:07

@Johnsyweb - 這聽起來像是對我功課 – 2010-05-17 22:03:22

如果這是家庭作業，標記爲這樣。你嘗試做什麼？ – Rubys 2010-05-17 22:03:31

嗯，有很多方法可以做到這一點。最好的辦法是有一個單維數組，用於跟蹤每個級別添加/刪除的節點數量。考慮到你的要求是最簡單的方法。

但是，如果只提供了一個二叉樹，則必須遍歷並進入許多級別並對節點進行計數，但我沒有看到任何其他選擇。

要達到某個級別，通常需要一個名爲'current_depth'的變量，它將跟蹤您所處的級別。一旦達到您的興趣級別並且節點被訪問一次（通常a爲了遍歷就足夠了）你可以增加你的計數。希望這有助於。

來源

2010-05-17 22:04:07 bragboy

可以ü發表一些代碼示例 – sadatwins 2010-05-17 22:05:35

雖然它不直接回答你的問題，你可以用它作爲參考：http://www.technicalypto.com/2010/02/trace-path-of-binary-tree。 html – bragboy 2010-05-17 22:25:00

使用遞歸函數只能下降到一定的水平。

來源

2010-05-17 22:05:41 tamasd

我認爲OP是要求**從**某個級別，而不是**到**某個級別。 – 2010-05-17 22:19:52

我認爲OP要求**在某個級別**，但誰知道。 – sth 2010-05-17 22:31:17

我假設你的二叉樹不一定是完整的（即，不是每個節點都有兩個或零個子節點，或者這變得微不足道）。我還假設你應該只計算某個級別的節點，而不是該級別或更深的節點。

有很多方法可以做你要求的東西，但是你可以把它想象成一個圖搜索問題 - 給你一個起始節點（樹的根節點），一種遍歷邊的方法（孩子鏈接）和一個標準 - 距根的一定距離。

在這一點上，你可能學習了圖搜索算法 - 哪種算法聽起來很適合你的任務？

來源

2010-05-17 22:05:49 Uri

一般條款：
遞歸。
在遞歸的每一次迭代中，你都需要測量你在什麼級別上，因此要知道你需要超出目前的位置。
遞歸部分：

你是什麼情況？你在什麼條件下說「好吧，時間停止遞歸」？
如何在沒有任何全局計數的情況下計算遞歸中的某些內容？

來源

2010-05-17 22:07:32 Rubys

我認爲最簡單的方法是簡單地跟隨樹的遞歸性質，使用累加器來跟蹤當前級別（或者可能還有待下降的級數）。

該函數的非遞歸分支是當您遇到有問題的級別時。此時你只需返回1（因爲你在該級別找到了一個節點）。

遞歸分支，簡單地總結從左和右遞歸調用返回的該級別的節點數量。

來源

2010-05-17 22:10:03

這是僞代碼，這是假定根具有0

int count(x,currentLevel,desiredLevel) 
    if currentLevel = desiredLevel 
     return 1 
    left = 0 
    right = 0 
    if x.left != null 
     left = count(x.left, currentLevel+1, desiredLevel 
    if x.right != null 
     right = count(x.right, currentLevel+1, desiredLevel 
    return left + right

水平因此，要獲得你打電話

count(root,0,3)

來源

2010-05-17 22:56:19 Enrique

具有給定級別的節點的二叉樹數量

回答

相關問題