提到存儲(chǔ)結(jié)構(gòu)，可以很自然的想到順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。樹(shù)這種數(shù)據(jù)結(jié)構(gòu)類(lèi)型，它是由結(jié)點(diǎn)和聯(lián)接結(jié)點(diǎn)的邊構(gòu)成。這些邊，聯(lián)接了樹(shù)中的任意兩個(gè)結(jié)點(diǎn)，從計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式來(lái)看，其實(shí)，就是通過(guò)指針保存了地址，從而實(shí)現(xiàn)了兩個(gè)結(jié)點(diǎn)間的聯(lián)接。

目前累計(jì)服務(wù)客戶(hù)上千家，積累了豐富的產(chǎn)品開(kāi)發(fā)及服務(wù)經(jīng)驗(yàn)。以網(wǎng)站設(shè)計(jì)水平和技術(shù)實(shí)力，樹(shù)立企業(yè)形象，為客戶(hù)提供網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站策劃、網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷(xiāo)、VI設(shè)計(jì)、網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。成都創(chuàng)新互聯(lián)始終以務(wù)實(shí)、誠(chéng)信為根本，不斷創(chuàng)新和提高建站品質(zhì)，通過(guò)對(duì)領(lǐng)先技術(shù)的掌握、對(duì)創(chuàng)意設(shè)計(jì)的研究、對(duì)客戶(hù)形象的視覺(jué)傳遞、對(duì)應(yīng)用系統(tǒng)的結(jié)合，為客戶(hù)提供更好的一站式互聯(lián)網(wǎng)解決方案，攜手廣大客戶(hù)，共同發(fā)展進(jìn)步。

  那么關(guān)于樹(shù)的表示方式，先講一下最簡(jiǎn)單的，就是雙親表示法，我把它稱(chēng)之為父節(jié)點(diǎn)表示法。畢竟，在樹(shù)中，雙親結(jié)點(diǎn)其實(shí)就是父節(jié)點(diǎn)。既然，鏈表也是有結(jié)點(diǎn)構(gòu)成，那么，這個(gè)結(jié)點(diǎn)中，必然的必須得有能夠存放數(shù)據(jù)的變量，以及存放下一個(gè)結(jié)點(diǎn)的地址的變量，如果沒(méi)有這個(gè)變量，如何建立兩個(gè)結(jié)點(diǎn)間的聯(lián)接呢？但是，此時(shí)，這個(gè)存放的地址的變量，并不是存放下一個(gè)結(jié)點(diǎn)的地址，存放的是它的父節(jié)點(diǎn)的地址，也就是父節(jié)點(diǎn)在數(shù)組中的下標(biāo)位置。然后還得再定義一個(gè)樹(shù)結(jié)構(gòu)，這個(gè)數(shù)結(jié)構(gòu)中，必須得包含一個(gè)數(shù)組，因?yàn)閿?shù)組就是用來(lái)表示結(jié)點(diǎn)的，還得有一個(gè)根節(jié)點(diǎn)的位置變量以及結(jié)點(diǎn)數(shù)的變量。那么，該結(jié)構(gòu)定義如下：

#define MAX_TREE_SIZE  100
typedef int TElemType;
typedef struct PTNode{

    TElemType data;
    int parent;
}PTNode;

typedef struct{

    PTNode nodes[MAX_TREE_SIZE];
    int r, n;
}PTree;

因?yàn)椋?jié)點(diǎn)就是祖先，所以它沒(méi)有父類(lèi)，所以，約定,根節(jié)點(diǎn)的位置域設(shè)置為-1。

如上圖所示，結(jié)點(diǎn)A就是根結(jié)點(diǎn)。

下標(biāo)    data    parent
 0        A        -1
 1        B        0
 2        C        0
 3        D        0
 4        E        1
 5        F        1
 6        G        1
 7        H        2
 8        I        3
 9        J        3

因?yàn)锽的父親是A，所以B中存放了A的下標(biāo)0，C和D的父親都是A，所以都存放了下標(biāo)0，E、F和G的父親是B，所以它們存放了B的下標(biāo)1；H的父親是C，所以H存放了下標(biāo)2；I和J的父親是D，所以它們存放了D的下標(biāo)3。這種方式可以知道哪個(gè)結(jié)點(diǎn)是哪個(gè)結(jié)點(diǎn)的父親，哪個(gè)結(jié)點(diǎn)是哪個(gè)結(jié)點(diǎn)的兒子，但是卻無(wú)法確定順序，也就是說(shuō)，一個(gè)結(jié)點(diǎn)可能擁有多個(gè)子節(jié)點(diǎn)，但是卻無(wú)法確定這些子節(jié)點(diǎn)哪個(gè)在前哪個(gè)在后。雙親表示法求父節(jié)點(diǎn)方便，因?yàn)槊總€(gè)結(jié)點(diǎn)中都保存了其父節(jié)點(diǎn)的下標(biāo)。

  第二種方式。孩子表示法。依然采用連續(xù)存儲(chǔ)，也就是數(shù)組存儲(chǔ)，不過(guò)，一個(gè)結(jié)點(diǎn)分為兩部分，一部分放數(shù)據(jù)，另一部分放其子節(jié)點(diǎn)的指針（地址）。若是一個(gè)結(jié)點(diǎn)有多個(gè)孩子，假設(shè)A有三個(gè)孩子，B、C和D。那么，A中就存放B的指針域，在B中則存放C的指針域，C中則存放D的指針域，也就是A的孩子采用了鏈?zhǔn)酱鎯?chǔ)的方式，串聯(lián)了起來(lái)。孩子表示法，求其子節(jié)點(diǎn)比較方便，而求其父節(jié)點(diǎn)就比較麻煩。

孩子表示法結(jié)構(gòu)代碼如下：

#define MAXZ_TREE_SIZE  100
typedef struct CTNode{
    
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct{

    TElemType data;
    ChildPtr firstchild;
}CTBox;

typedef struct{

    CTBox nodes[MAX_TREE_SIZE];
    int r, n;   //存放樹(shù)的根和結(jié)點(diǎn)數(shù)
    
}CTree;

  第三種方式。父親孩子表示法。顧名思義，就是將前兩種方式結(jié)合了。也就是說(shuō)，一個(gè)結(jié)點(diǎn)不止存放數(shù)據(jù)，還存放該該節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)，還存放該節(jié)點(diǎn)子節(jié)點(diǎn)的指針，那為什么父節(jié)點(diǎn)可以存放下標(biāo)，存放子節(jié)點(diǎn)就只能存放子節(jié)點(diǎn)的指針？因?yàn)椋粋€(gè)結(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，卻有多個(gè)子節(jié)點(diǎn)，或者是沒(méi)有子節(jié)點(diǎn)，所以沒(méi)有辦法確定子節(jié)點(diǎn)的個(gè)數(shù)，于是，就只能通過(guò)鏈?zhǔn)酱鎯?chǔ)了。

        二叉樹(shù)法（孩子兄第表示法）就是將一般樹(shù)轉(zhuǎn)化為二叉樹(shù)。具體轉(zhuǎn)化方式為：左指針指向它的第一個(gè)孩子結(jié)點(diǎn)，右指針指向它的第一個(gè)兄弟結(jié)點(diǎn)。

二叉樹(shù)法結(jié)構(gòu)代碼定義如下：

typedef struct CSNode{
    
    TElemType data;
    struct CSNode *firstchild, *rightsib;

}CSNode, *CSTree;

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱(chēng)：樹(shù)的存儲(chǔ)結(jié)構(gòu)-創(chuàng)新互聯(lián)
新聞來(lái)源：http://www.chinadenli.net/article10/iiigo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、外貿(mào)建站、定制網(wǎng)站、網(wǎng)站設(shè)計(jì)、App設(shè)計(jì)、ChatGPT

廣告

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