二元搜索樹和二元樹樹有什麼區別？

我的意思是一棵二叉搜索樹是一個樹，左邊的孩子比右邊的孩子更大/等於父親。二元搜索樹和二元樹樹有什麼區別？

線程化的二叉樹有線程。這是如何使它不同？

來源

2015-03-31 user4275686

你可以有一個線程二叉搜索樹。 *任何*二叉樹都可以線程化。對二叉搜索樹進行線程化的優點是，您可以輕鬆地從任意節點向前和向後遍歷。這對於非線程BST非常困難。 – 2015-03-31 17:59:58

在帶線程的二叉樹中，將具有空引用的樹葉替換爲對有序子樹（或右子元素）或前驅樹（對於左子樹）節點的引用。如果只使用後繼或前輩引用，則樹是單線程，如果兩者都是，那麼它是雙線程。這使得節點的有序遍歷在計算上更便宜。

此圖像（從Wikipedia借用）示出的數據結構很好：

enter image description here

請參考Wikipedia article獲得更多信息。

來源

2015-03-31 06:25:52 meskobalazs

因此，如果我猜測我認爲Threaded二叉樹的葉子節點不指向空但是有效的節點（或者說沒有葉節點？），而在二叉搜索樹中葉節點指向空。 – user4275686 2015-03-31 07:01:23

「通過使通常爲零的所有正確的子指針指向節點的中間繼承者來對二叉樹進行線程化」這回答了您的問題:) – meskobalazs 2015-03-31 07:07:54

'在線程化的二叉樹中，總是有一個_direct_指針指向in-訂單繼承人和/或前任元素。「 - 不，不一定。（在圖中，B沒有_Direct_指向C的指針）。 – greybeard 2015-03-31 14:48:27

這裏thread並不意味着另一個並行執行堆棧。它意味着指向樹的每個節點的下一個元素和前一個元素。

請參閱Wikipedia的說明。

來源

2015-03-31 06:25:25

Wiki「通過使通常爲空的所有正確的子指針指向節點的中繼繼承者（如果它存在），並且所有通常爲空的所有左子指針指向按照節點的前任。「

您通常會這樣做，因此您可以快速找到節點的中繼節點（給定節點），而不是遍歷，直到每次遍歷時都保留主節點和繼承節點。

雖然對於二叉搜索樹是正確的，但左側的節點將比父節點小，而右側的節點將比父節點大。

來源

2015-03-31 06:27:17 SMA

Threaded Binary Tree Article in Wikipedia

「二叉樹是通過使所有的右子指針正常情況下可空點到節點的序後繼（如果存在的話）螺紋，以及所有左子指針，通常會爲空指向節點的前驅節點「。

來源

2015-03-31 06:29:15 Tarik

比較這兩個概念有點像比較蘋果和水牛。 :)二叉搜索樹是二叉搜索樹的特例，其中元素滿足您提到的排序 - 左側子樹中的所有內容必須小於根節點，並且右側子樹中的所有內容都必須更大。一個線程樹沒有任何這樣的限制，事實上，一個線程樹不需要在節點中有數據可以與一個排序關係進行比較。實際上，二叉搜索樹是一個與樹的實現本質無關的概念，而線程樹只有關於樹是如何實現的，你如何設置樹節點中的指針。如果您決定以這種方式實現它，則二叉搜索樹可以是線程樹。

來源

2015-03-31 06:33:22 ajb

你可以提到每個的幾個用途嗎？爲什麼我想要一個線程樹？「其他」不提供的任何優勢？ – user4275686 2015-03-31 06:54:06

對不起，StackOverflow是一個問題和答案的地方，而不是問題和整本書章節。恐怕你在這裏問得太多了。 – ajb 2015-03-31 06:58:05

其實我試圖確定它們是完全不同的，並且沒有任何關係，正如你所宣稱的那樣。 – user4275686 2015-03-31 06:59:33

二元搜索樹和二元樹樹有什麼區別？

回答

相關問題