樹高的定義是什麼？

我似乎無法找到這個一個明確的答案，我試圖做堆一些基本的證據，但這裏是什麼扔我了一點點：樹高的定義是什麼？

是一個空的樹是否有效？如果是這樣，它的高度是多少？
我認爲這應該是0.

什麼是單個節點樹的高度？
我會認爲這將是1，但我已經看到它是0的定義（如果是這種情況，那麼我不知道如何解釋一棵空樹）。

來源

2010-02-05 Brad

我想你應該看看在NIST網站上的Dictionary of Algorithms and Data Structures。有definition for height表示單個節點的高度爲0.

definition of a valid tree確實包含空的結構。該網站沒有提到這樣的樹的高度，但基於高度的定義，它也應該是0.

來源

2010-02-05 19:34:11 nlucaroni

謝謝，很高興有一個可靠的來源引用此（不要以爲一位教授或同行評議會認爲維基百科是一個可接受的來源）。雖然他們的定義似乎有些矛盾，但他們將樹定義爲「空（無節點），或者根和零個或多個子樹」。但是他們的高度定義是根節點定義的。 – Brad

我同意。我認爲你應該明確地給他發電子郵件（所以你可以在該頁面引用它來提出這個區別）。但考慮到定義意味着從根到邊的最大邊數，我們必須說空樹的高度爲0. – nlucaroni

我剛剛檢查了新的Cormen，他沒有區分（p。1177）。 – nlucaroni

樹的高度是從該樹根到最遠節點（即離根最遠的葉節點）的路徑長度。

只有根節點的樹高度爲0，並且具有零節點的樹將被視爲空。空樹的高度爲-1。請檢查this。

我希望這會有所幫助。

來源

2010-02-05 19:28:47 Arnkrishn

我相信它是一個用於實現的約定。由於當樹中有一個或多個節點時，所有正高度值和高度值零都會被表示，所以您應該有一些東西來表示空樹。所以這個約定就是-1。你可以把它作爲任何其他負值。它的實現問題是數據結構的實際抽象 - 樹不會涵蓋這些東西。 – Arnkrishn

具有高度-1的空樹約定實際上在AVL樹中具有一些實際用途，因爲它簡化了計算平衡因子和何時旋轉兒童。這個實現在實踐中顯示它：http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java – Robert

我已經看到它以兩種方式使用（將單個節點統計爲0或1），但大多數源將定義僅作爲高度爲0的樹的根，並且不會考慮0節點樹有效。

來源

2010-02-05 19:30:53

根據Wikipedia，單個節點的（子）樹的高度爲0.沒有節點的樹的高度爲-1。但我認爲這取決於你，你如何定義身高和你的證明應該適用於任何一個定義。

來源

2010-02-05 19:31:56 MartinStettner

如果你的樹是一個遞歸定義的數據結構，它可以是空的，也可以是一個節點一個左右子樹（例如搜索樹，或者你的堆），那麼自然的定義是把0賦給空樹，把1 +最高子樹的高度賦給非空樹。

如果你的樹是一個圖，那麼自然定義是從根到葉的最長路徑，所以只有根的樹的深度爲0.在這種情況下，你通常不會考慮空樹。

來源

2010-02-05 19:53:58 starblue

我想指出，（a）你顯然是對的，（b）NIST和許多其他人不以我們的方式看待事物（y）。我相信這種不幸的狀況主要是由於CLR，「恐懼無效」。 –

樹的高度是其任一子節點中到達終端節點的最長路徑的長度。

維基百科說the height of an empty tree is -1。我不同意。空樹實際上只是一個包含一個終端節點（表示空樹的空值或特殊值）的樹。由於該節點沒有子節點，因此其最長路徑必須爲的長度爲empty sum = 0，而不是-1。

同樣，一棵非空的樹有兩個孩子，所以根據定義，至少有一個路徑> = 1到終端節點。

我們可以如下定義我們的樹：

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Nil 

let rec height = function 
    | Node(left, x, right) -> 1 + max (height left) (height right) 
    | Nil -> 0

來源

2010-02-05 20:09:16 Juliet

「空樹實際上只是一棵包含一個終端節點的樹。」不，甚至比那更空虛... – Thomas

因爲Caml +1 – Wok

-3

actully對樹的高度完美DEFN是從根d最長路徑的葉子的d級加1..accordin 2本DEFN發樹空的，它不會考慮任何級別nv不認爲它有零，根的零水平等於零.so空樹級別是-1，比accordin 2定義它的-1 + 1 = 0..so零空sd的高度樹... bt n許多書他們hav給出-1 bt沒有給出解釋

來源

2010-10-20 12:53:21 angad

樹高的定義是什麼？

回答

相關問題