1樹(shù)的定義 1.1樹(shù)的基礎(chǔ)定義

樹(shù)可以用幾種方式定義，其中一種自然的方法是遞歸方法

創(chuàng)新互聯(lián)2013年至今，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元安塞做網(wǎng)站,已為上家服務(wù),為安塞各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:028-86922220

一棵樹(shù)是一些節(jié)點(diǎn)的集合，有些節(jié)點(diǎn)具有特殊的叫法（如“根”），這個(gè)集合可以是空集，若非空，則一棵樹(shù)則是根與數(shù)個(gè)或零個(gè)的非空的子樹(shù)的集合

樹(shù)是由一條條有向的邊所連接

1.2樹(shù)的基本特征

1.2.1樹(shù)的基礎(chǔ)相關(guān)概念

根（root）：樹(shù)的開(kāi)始節(jié)點(diǎn)

如果樹(shù)擁有子樹(shù)，則子樹(shù)同樣擁有自己的根，如上圖二叉樹(shù)中始根有兩個(gè)子樹(shù)，兩個(gè)子樹(shù)擁有對(duì)應(yīng)自己的根

兒子（child) : 每一棵子樹(shù)的根叫做根（root）的兒子（真是令人眼前一黑的神級(jí)翻譯）

父親（parent）：根（root）是每一棵對(duì)應(yīng)此根的子樹(shù)的根的父親

樹(shù)葉（leaf）:沒(méi)有兒子的節(jié)點(diǎn)叫做樹(shù)葉

兄弟（sibling）:具有相同父親的節(jié)點(diǎn)叫做兄弟

同樣的可以明確祖父（grandparent）與孫子（grandchild）的關(guān)系

1.2.2樹(shù)的一般結(jié)構(gòu)

一棵樹(shù)由N個(gè)節(jié)點(diǎn)與N-1條邊組成，一般的，其中位于頭部的節(jié)點(diǎn)是樹(shù)的根，每條邊都將他的節(jié)點(diǎn)連接到他的父親，去除樹(shù)的根外，每一個(gè)節(jié)點(diǎn)都有他的父親，去除樹(shù)葉，每一個(gè)節(jié)點(diǎn)都有他的兒子

1.2.3樹(shù)的結(jié)構(gòu)關(guān)系概念

路徑（path）:從節(jié)點(diǎn)n1到nk的一個(gè)序列，此序列使得對(duì)于從n1到nk的的每一個(gè)節(jié)點(diǎn)都順序是下一節(jié)點(diǎn)的父親，

路徑的長(zhǎng)（length）：該路徑上的邊的條數(shù)

深度（depth):對(duì)于任意節(jié)點(diǎn)，從根到節(jié)點(diǎn)的的唯一路徑的長(zhǎng),根的深度為0

高度（height）:對(duì)于任意節(jié)點(diǎn)，從節(jié)點(diǎn)到一片樹(shù)葉的最長(zhǎng)路徑的長(zhǎng)，所有樹(shù)葉的高度都為0

關(guān)系補(bǔ)充：

如果存在從n1到n2的一條路徑，則n1是n2的一位祖先（ancestor）,而n2是n1的一位后裔（descendant）

對(duì)于n1!=n2的情況，那么n1是n2的一位真祖先（ancestor）,而n2是n1的一位真后裔（descendant）， （類比于集合的基礎(chǔ)知識(shí)）

2樹(shù)的實(shí)現(xiàn) 2.1如何實(shí)現(xiàn)一個(gè)樹(shù)？

使用c語(yǔ)言為例，很自然的可以想到利用結(jié)構(gòu)體來(lái)創(chuàng)建一個(gè)“樹(shù)”數(shù)據(jù)結(jié)構(gòu)

但是問(wèn)題是我們事先不知道各個(gè)節(jié)點(diǎn)的兒子數(shù)，它可以變化很大，因此我們無(wú)法直接區(qū)建立根與子樹(shù)的聯(lián)系，否則對(duì)于空間是一種浪費(fèi)

于是可以這樣解決：將每個(gè)節(jié)點(diǎn)的所有兒子放在樹(shù)節(jié)點(diǎn)的鏈表中，如下例

typedof struct TreeNode *PtrToNode
struct TreeNode
{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode NextSibling
}

以下面的樹(shù)為例（畫(huà)的比較抽象，抱歉）

利用上述方法，可得

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：數(shù)據(jù)結(jié)構(gòu)之“樹(shù)”（c語(yǔ)言實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://chinadenli.net/article32/hcopc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站設(shè)計(jì)、域名注冊(cè)、品牌網(wǎng)站制作、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)