樹的存儲結構-創(chuàng)新互聯(lián)

提到存儲結構，可以很自然的想到順序存儲結構和鏈式存儲結構兩種。樹這種數(shù)據(jù)結構類型，它是由結點和聯(lián)接結點的邊構成。這些邊，聯(lián)接了樹中的任意兩個結點，從計算機內存中的存儲方式來看，其實，就是通過指針保存了地址，從而實現(xiàn)了兩個結點間的聯(lián)接。

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

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

#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;

因為，根節(jié)點就是祖先，所以它沒有父類，所以，約定,根節(jié)點的位置域設置為-1。

樹的存儲結構

如上圖所示，結點A就是根結點。

下標    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

因為B的父親是A，所以B中存放了A的下標0，C和D的父親都是A，所以都存放了下標0，E、F和G的父親是B，所以它們存放了B的下標1；H的父親是C，所以H存放了下標2；I和J的父親是D，所以它們存放了D的下標3。這種方式可以知道哪個結點是哪個結點的父親，哪個結點是哪個結點的兒子，但是卻無法確定順序，也就是說，一個結點可能擁有多個子節(jié)點，但是卻無法確定這些子節(jié)點哪個在前哪個在后。雙親表示法求父節(jié)點方便，因為每個結點中都保存了其父節(jié)點的下標。

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

樹的存儲結構

孩子表示法結構代碼如下：

#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ù)
    
}CTree;

  第三種方式。父親孩子表示法。顧名思義，就是將前兩種方式結合了。也就是說，一個結點不止存放數(shù)據(jù)，還存放該該節(jié)點的父節(jié)點的下標，還存放該節(jié)點子節(jié)點的指針，那為什么父節(jié)點可以存放下標，存放子節(jié)點就只能存放子節(jié)點的指針？因為，一個結點只有一個父節(jié)點，卻有多個子節(jié)點，或者是沒有子節(jié)點，所以沒有辦法確定子節(jié)點的個數(shù)，于是，就只能通過鏈式存儲了。

樹的存儲結構

        二叉樹法（孩子兄第表示法）就是將一般樹轉化為二叉樹。具體轉化方式為：左指針指向它的第一個孩子結點，右指針指向它的第一個兄弟結點。

二叉樹法結構代碼定義如下：

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

}CSNode, *CSTree;

樹的存儲結構

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

新聞名稱：樹的存儲結構-創(chuàng)新互聯(lián)
新聞來源：http://bm7419.com/article10/iiigo.html

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

廣告

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

成都做網(wǎng)站