亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

定義

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

G 是沒有回路的連通圖。

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

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

G 是連通的，并且3頂點的完全圖 K 3 {\displaystyle K_{3}} 不是 G 的子圖。

G 內(nèi)的任意兩個頂點能被唯一路徑所連通。

如果無向簡單圖 G 有有限個頂點（設(shè)為 n 個頂點），那么 G 是一棵 樹 還等價于：

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

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

性質(zhì)

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

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

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

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

顯然樹中也沒有自環(huán)和重復(fù)邊。

有根樹

在一棵樹中可以指定一個特殊的節(jié)點： 根 。一個有根的樹叫做 有根樹 。

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

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

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

存儲

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

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

樹的遍歷

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

對于有根樹的從根開始的深度優(yōu)先搜索遍歷，有三種特定的順序：

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

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

森林

森林 比樹少一個條件，指沒有回路的圖。也就是說，森林可能是不連通的，邊數(shù)可能比樹還少，就是說小于頂點數(shù)。

森林也可以看成是好多棵互不相連的非空的樹，只有一棵樹也可以算是森林。不過森林不一定是一棵樹。

森林也可以是有根的，這時候森林中的每一棵樹都有一個根。

一棵樹去掉若干條邊也會成為森林，這時候可以看成一棵樹分成了好多棵樹。森林中的兩棵樹之間加一條邊，也可以把這兩棵樹合在一起，最終合成一棵樹。

很多地方用森林，都是用來表示很多棵樹，包括作為邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的時候等。有一種重要的數(shù)據(jù)結(jié)構(gòu) 并查集 就是一個有根的森林，可以很快的判斷兩個元素是不是屬于同一個互相獨立的集合，以及合并兩個集合等。

邏輯結(jié)構(gòu)

樹也通常會用來表示邏輯結(jié)構(gòu)，例如搜索樹。表示邏輯結(jié)構(gòu)的樹一般是有根樹。這種結(jié)構(gòu)類似于有拓撲序的圖，每個節(jié)點是其之前的節(jié)點的后繼、分支、子節(jié)點等。樹的結(jié)構(gòu)中，每個節(jié)點之前的節(jié)點是唯一的（就是說有唯一的前驅(qū)、上層容器、父節(jié)點等），另外每一個節(jié)點及其后面的部分也都是一棵樹。

作為數(shù)據(jù)結(jié)構(gòu)

樹也是一類重要的數(shù)據(jù)結(jié)構(gòu)，同時也有邏輯結(jié)構(gòu)的性質(zhì)，通常也是有根樹。主要有搜索樹和堆兩種，前者的內(nèi)容是按中序遍歷的順序排序的，后者每個節(jié)點的關(guān)鍵字都比它的子節(jié)點大（或者?。?。復(fù)雜度一般在樹的高度，也就是O(nlogn)以內(nèi)。

搜索樹 可以快速的查找有序的內(nèi)容或者新內(nèi)容在已有內(nèi)容中的位置，也可以進行一些和按這個順序的范圍有關(guān)的統(tǒng)計。

堆 (數(shù)據(jù)結(jié)構(gòu)) 是一種優(yōu)先隊列，比搜索樹功能少，通常只能很方便的求堆中關(guān)鍵字最?。ㄗ畲螅┑臄?shù)據(jù)，不能查找。（當(dāng)然有的時候求次小和第三小也是很方便的）

很多這類數(shù)據(jù)結(jié)構(gòu)會給每個點或者邊加上一些別的參數(shù)。有些數(shù)據(jù)結(jié)構(gòu)還會破壞本來的樹的結(jié)構(gòu)，但是基本還是用的樹的模式，一般還是叫做“樹”。

樹的類型

自由樹

有根樹

二叉樹

Positional tree

空樹

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。