二叉樹的用法

4

在C＃中，使用Java，Python，C++（使用STL）以及其他高級語言，大部分時間您將使用內置/庫 - 之一包括用於存儲數據的類型，至少是當前處理的數據，所以大多數情況下您不會明確使用二叉樹或其他類型的樹。

這就是說，這些內置類型中的一些被實現爲「在後臺」的一種或另一種樹，在某些情況下，您將不得不自己實現一個。

此外，你必須知道的相關事情是二分查找。這主要是在二叉樹（二叉搜索樹：P）中完成的，但即使沒有涉及樹，這個想法也可以外推到很多問題上，所以試着理解它。

編輯：現實生活中經典的例子：

試想一下，你要搜索一個特定的人在大城市的電話指導的電話號碼。所有的事情都是平等的，你會在中間大概打開它，尋找那個頁面中的人，看看你的「目標」是在它之前還是之後，從而將數據減半。然後在你知道你的「目標」的那一半重複這個操作，並且一次又一次地直到你找到你的「目標」。由於每次查看前一半的數據時，都需要執行一次log（base 2）n操作才能到達「目標」，其中n是數據的總大小。因此，在一百萬個電話簿中，您可以在log（基數2）100萬= 20的比較中找到您的目標，而不是像在線性搜索中那樣逐一比較（在最差情況下是100萬比較）。

請注意，這隻適用於已排序的數據。

來源

2009-11-09 02:36:25 AntonioMO

0

一個簡單的例子就是搜索。例如，如果您將列表數據存儲在樹中，則會得到O（log（n））查找時間。列表的標準數組實現將實現O（n）查找時間。

來源

2009-11-09 00:55:48

+0

因此，你可以存儲任何你想存儲在樹中的數組？但是在樹中，查找時間更少......我想這隻適用於包含大量數據的數據結構。 – 2009-11-09 00:57:53

+1

@Tony：不一定。任何具有顯式層次結構的東西都適用於樹（可能不是二叉樹，但一般樹），即使它不是那麼多項目。（考慮你的家譜：即使你不知道你的許多親屬仍然是一棵樹！） – 2009-11-09 01:26:58

+1

二叉搜索樹需要** O **（log2 * n *）比較。線性列表需要** O **（* n */2）。在8個元素中，您會發現樹需要（至多）3個比較，但線性搜索需要（平均）4. – 2009-11-09 01:58:38

1

在Java中，樹木被用於實現某些排序的數據結構，如TreeSet的：

http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html

它們用於在您想要的順序是基於的某些屬性數據結構元素，而不是放置順序。

來源

2009-11-09 00:55:55 Peter

0

XML，HTML（和SGML）文檔是樹。

來源

2009-11-09 00:57:16

+0

但是它們不是二叉樹嗎？因爲它們可能有兩個以上屬於一個節點的子節點，所以它不符合二叉樹規則。 – Tarik 2009-11-09 01:07:46

+0

它們是n元樹，任何節點都可以有任意數量的子節點。它用於靈活性（所以你的HTML文檔可以有任何結構），其中二叉樹和它的堂兄弟（紅/黑等）被構建用於存儲大量數據並且相對於數字非常快地插入或檢索任何數據項存儲在樹中的東西。 – 2009-11-09 01:21:48

+0

嗯 - 現在我不記得n-ary樹是否是正確的詞。不過，我的其他描述還是可以的。 – 2009-11-09 01:26:10

4

Balanced binary trees，存儲數據維護按排序順序，用於實現O（log（n））查找，刪除和插入時間。「平衡」僅僅意味着在最淺和最深葉片的深度之間存在有界限，將空的左/右節點計爲葉片。（最好左邊和右邊的子樹的深度最多相差一個，有些實現可以放寬這個使算法更簡單）

您可以使用二進制搜索的排序順序來使用數組而不是樹，以實現O（ log（n））查找時間，但插入/刪除時間是O（n）。

某些樹（特別是數據庫的B-trees）在每個節點上使用2個以上的分支，以擴大樹並減少最大深度（決定搜索時間）。

~~我想不出有什麼理由使用未按排序順序維護的二叉樹（這裏沒有提到大多數答案），但也許有一些應用程序。~~ 除了排序後的二進制平衡樹之外，任何具有層次結構的東西（如其他回答者已經提到的，XML或目錄結構）對樹來說都是一個很好的應用程序，無論是否是二元樹。

編輯：回覆：未排序的二叉樹：我只記得LISP和Scheme都大量使用不平衡的二叉樹。 cons函數接受兩個參數（例如(define c (cons a b))）並返回一個樹節點，其分支是兩個參數。 car函數接受這樣一個樹節點並返回給予cons的第一個參數。 cdr函數類似，但將第二個參數返回到cons。最後nil代表一個空對象。這些是用來製作LISP和Scheme中所有數據結構的原語。列表是使用極端不平衡二叉樹實現的。含有文字元素'Alabama，'Alaska，'Arizona列表，'Arkansas可以明確地構造爲

(cons 'Alabama (cons 'Alaska (cons 'Arizona (cons 'Arkansas nil))))

，並且可以使用car和cdr（其中car用來獲取該列表的頭部和cdr被遍歷用於得到不包括列表頭的子列表）。這是計劃如何運作，我認爲LISP是相同或非常相似的。更復雜的數據結構，如二叉樹（每個節點需要3個成員：兩個用於保存左右節點，第三個用於保存節點值）或包含每個節點兩個以上分支的樹可以使用列表構造實現每個節點。

來源

2009-11-09 01:02:00

3

Unix下的目錄結構如何？例如，du命令，即磁盤使用命令執行表示目錄結構的樹的遍歷命令遍歷（遍歷順序::左子節點 - >右子節點 - >根節點），以便獲取該目錄使用的磁盤空間。

下面的幻燈片應該有所幫助。

http://www.cse.unt.edu/~rada/CSCE3110/Lectures/Trees.ppt

歡呼

來源

2009-11-09 01:13:00 Arnkrishn

+0

很好的例子 - 儘管目錄結構不是二叉樹 – 2009-11-09 01:31:28

+0

是的，它們不是二叉樹。託尼在他的提問中提到了一棵普通的樹，我只是把它貼出來。 – Arnkrishn 2009-11-09 02:26:21

1

下面是一些例子：

解析的程序或表達的內存中表示爲樹。在表達式（不包括三元運算符）的情況下，該樹將是二元的。
GUI的組件被組織爲一棵樹。
任何「包容」層次結構都可以表示爲一棵樹。（HTML，XML和SGML是實例。

當然而且，二進制文件（和n進制）樹可以被用來表示索引，地圖，組等的「通用」的數據結構。

來源

2009-11-09 02:56:54

二叉樹的用法

回答

相關問題