數(shù)據(jù)結(jié)構(gòu)之“樹”（c語言實現(xiàn)）-創(chuàng)新互聯(lián)

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

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

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

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

樹是由一條條有向的邊所連接

1.2樹的基本特征

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

根（root）：樹的開始節(jié)點

如果樹擁有子樹，則子樹同樣擁有自己的根，如上圖二叉樹中始根有兩個子樹，兩個子樹擁有對應自己的根

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

父親（parent）：根（root）是每一棵對應此根的子樹的根的父親

樹葉（leaf）:沒有兒子的節(jié)點叫做樹葉

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

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

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

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

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

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

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

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

高度（height）:對于任意節(jié)點，從節(jié)點到一片樹葉的最長路徑的長，所有樹葉的高度都為0

關(guān)系補充：

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

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

2樹的實現(xiàn) 2.1如何實現(xiàn)一個樹？

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

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

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

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

以下面的樹為例（畫的比較抽象，抱歉）

利用上述方法，可得

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

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

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

廣告

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