一棵樹中每兩個點之間都有且只有一條路徑(指沒有重複邊的路徑)。一顆有N個點的樹有N-1條邊，也就是連接N個點所需要的最少邊數。所以如果去掉樹中的一條邊，樹就會不連通。

　如果在一棵樹中加入任意的一條邊，就會得到有且只有一個環的圖。這是因為這條邊連接的兩個點(或是一個點)中有且只有一條路徑，這條路徑和新加的邊連在一起就是一個環。如果把一個連通圖中的多余邊全部刪除，所構成的樹叫做這個圖的生成樹。

　如果要在樹中加入一個點，就要加入一條這個點和原有的點相連的邊。這條邊不會給這棵樹增加一個環或者多余的路徑。所以每次這樣加入一個點，就可以構成一棵樹。

　一棵樹既可以是有向的也可以是無向的。顯然，樹是連通圖，但不會是雙連通圖(對於無向圖)或者強連通圖(對於有向圖)。樹可以算是稀疏圖。

　顯然樹中也沒有自環和重複邊。

　定義

　如果一個無向簡單圖G 滿足以下相互等價的條件之一，那麽G 是一棵樹:

　G 是沒有回路的連通圖。

　G 沒有回路，但是在G內添加任意一條邊，就會形成一個回路。

　G 是連通的，但是如果去掉任意一條邊，就不再連通。

　G 是連通的，並且3頂點的完全圖?不是G的子圖。

　G內的任意兩個頂點能被唯一路徑所連通。

　如果無向簡單圖G有有限個頂點(設為n個頂點)，那麽G 是一棵樹還等價於:

　G是連通的，有n ? 1條邊，並且G沒有簡單回路。

　如果一個無向簡單圖G中沒有簡單回路，那麽G是森林。

　性質

　一棵樹中每兩個點之間都有且只有一條路徑(指沒有重複邊的路徑)。一顆有N個點的樹有N-1條邊，也就是連接N個點所需要的最少邊數。所以如果去掉樹中的一條邊，樹就會不連通。

　如果在一棵樹中加入任意的一條邊，就會得到有且只有一個環的圖。這是因為這條邊連接的兩個點(或是一個點)中有且只有一條路徑，這條路徑和新加的邊連在一起就是一個環。如果把一個連通圖中的多余邊全部刪除，所構成的樹叫做這個圖的生成樹。

　如果要在樹中加入一個點，就要加入一條這個點和原有的點相連的邊。這條邊不會給這棵樹增加一個環或者多余的路徑。所以每次這樣加入一個點，就可以構成一棵樹。

　一棵樹既可以是有向的也可以是無向的。顯然，樹是連通圖，但不會是雙連通圖(對於無向圖)或者強連通圖(對於有向圖)。樹可以算是稀疏圖。

　顯然樹中也沒有自環和重複邊。

　有根樹

　在一棵樹中可以指定一個特殊的節點:根。一個有根的樹叫做有根樹。

　有根樹中的節點可以根據到根的距離分層。一顆有根樹的層數叫做這棵樹的高度。節點最多的那一層的節點數叫做這棵樹的寬度。對於有根樹，每條邊都有一個特殊的方向:指向根節點的方向，或者說上一層的方向(或者相反的，指向葉節點的方向，下一層的方向)。一條邊的兩個端點中，靠近根的那個節點叫做另一個節點的父節點(也叫父親、雙親、雙親節點)，相反的，距離根比較遠的那個節點叫做另一個節點的子節點(也可以叫孩子，兒子，子女等)。父親方向的所有節點都叫做這個節點的祖先，兒子方向的所有節點都叫做這個節點的子孫。沒有子節點的子節點叫做葉節點(或者葉子節點)。由於到根的路徑只有一條，根節點以外的節點的父節點永遠只有一個，祖先就是這個點到根的路徑上的所有節點(包括根，不包括這個節點本身)。另外，以一個節點為根的樹是指包括這個節點和其所有子孫，並以這個節點為根的樹。由於一般不需要這以外的子樹，每一個節點也可以對應到一個以其為根的樹，一個節點的子樹通常也是指以這個節點的子節點為根的樹。

　如果一顆有根樹每個節點的子樹最多有n個，同時每個節點在其父節點中都有固定的可能可以留空的位置，這棵樹叫做n叉樹。其中每個節點都可以有兩個固定位置的子樹的有根樹叫做二叉樹，二叉樹中每個節點的兩個子樹分別叫做左子樹和右子樹，由於位置固定，沒有左子樹的時候也是可以有右子樹的。而“多叉樹”通常並不指n為任意值的n叉樹，只是在和n叉樹作比較的時候表示普通的有根樹。

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

　存儲

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

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

　樹。。。。。

　說小於頂點數。

　，以及合並兩個集合等。

　加載更多