第236章 聲名鵲起（2/2）

對於隨機的樹，高度的平均複雜度是O(logn)，但是沒有限制而且不隨機的樹高度也可以達到O(n)，也就是除了葉節點都只有一個子樹，或者常數個分支的情況。所以樹作為數據結構時通常需要另外進行平衡。

存儲

對於普通的樹，可以像圖一樣為每一個點存儲一個邊表（通常按順序存和每一個點的關係的叫做鄰接矩陣，存具體的邊的叫做鄰接表），或者直接存儲所有邊的邊表等。由於樹是稀疏圖，所以一般不用鄰接矩陣存儲。對於有根樹，如果用為每一個點儲存一個邊表的方法，由於每一棵樹都只有一個父節點，所以通常指向父節點的邊不存在這個表中。同時如果子節點是沒有順序的，也是因為一個節點的子節點不會同時是其他節點的子節點，也可以把子節點直接當成存邊的鍊表的節點，這時候每個節點只需要儲存兩個指針，所以這種存儲方法有時候也會被叫做多叉樹轉二叉樹。

對於子節點是有順序的有根樹，每條邊都可以以固定的位置分別儲存。對於完全二叉樹甚至能直接用一個數組訪問所有節點，不另外儲存邊的信息。有的樹可以被設計成固定的從根節點開始訪問，這時候可以不儲存父節點。同樣的，有的樹也可以省略子節點，例如並查集。

樹的遍歷

【領現金紅包】看書即可領現金！關注微信.公眾號【書友大本營】，現金/點幣等你拿！

對於一般的樹，可以用和普通的圖一樣的方法遍歷，比如深度優先搜索和寬度優先搜索。如果和樹的每個節點相鄰的點有固定的順序，深度優先搜索可以不儲存當前點以外的任何信息，而且不用判重。而在有根樹中更方便，所以有根樹中很少使用寬度優先搜索。

對於有根樹的從根開始的深度優先搜索遍歷，有三種特定的順序：

前序遍歷

先訪問根節點，然後再訪問所有的子樹；

後序遍歷

先訪問子樹，然後再訪問根節點；

中序遍歷

二叉樹專用，先訪問左子樹，然後是根節點，最後是右子樹。

注意對於每一種遍歷，事實上都得先訪問根節點，這裡的遍歷順序是指處理節點中的數據的順序。已知中序遍歷和任一其他遍歷的情況下，可以還原一個二叉樹。一個直觀的方法是按前序或者反轉的後序插入一個按中序排序的搜索樹。已知前序和中序也可以還原一棵樹，但是不能知道二叉樹中一個節點唯一的子樹是在左邊還是右邊。

事實上也可以把左右的順序反過來。這些由根開始的遍歷方法也適用於特定的一個子樹。

森林