樹

    圖論

    共18個(gè)含義

    樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。它是一種無向圖（undirectedgraph），其中任意兩個(gè)頂點(diǎn)間存在唯一一條路徑。樹圖廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)中，比如二叉查找樹、堆、Trie樹以及數(shù)據(jù)壓縮中的霍夫曼樹等。

    頂點(diǎn)

    v

    邊

    v-1

    色數(shù)

    2

    定義

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

    G是沒有回路的連通圖。

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

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

    G是連通的，并且3頂點(diǎn)的完全圖?不是G的子圖。

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

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

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

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

    性質(zhì)

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

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

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

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

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

    有根樹

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

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

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

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

    加載更多

    相關(guān)搜索

    常見園林樹木160種

    樹圖片

    樹木種類大全

    關(guān)于樹的成語

    樹的寓意和象征

    大樹圖片

    盆景樹木種類前十名

    關(guān)于樹的古詩

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

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

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