樹(shù)(Tree)

本文主要是對(duì)數(shù)據(jù)結(jié)構(gòu)中非線性結(jié)構(gòu) 樹(shù) 的學(xué)習(xí)和總結(jié)咆爽。

樹(shù)的定義

專業(yè)定義:

1.有且只有一個(gè)稱為根的節(jié)點(diǎn)
2.有若干個(gè)互不相交的子樹(shù),這些子樹(shù)本身也是一棵樹(shù)

通俗的定義:

1.樹(shù)由節(jié)點(diǎn)和邊組成
2.每一個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)
3.當(dāng)有一個(gè)節(jié)點(diǎn)例外捶箱,該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn),該節(jié)點(diǎn)稱為根節(jié)點(diǎn)

專業(yè)術(shù)語(yǔ):

節(jié)點(diǎn)  父節(jié)點(diǎn)  子節(jié)點(diǎn)  子孫  堂兄弟  
深度:從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱之為深度啤咽。  根節(jié)點(diǎn)是第一層
葉子節(jié)點(diǎn):沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
非終端節(jié)點(diǎn): 實(shí)際就是非葉子節(jié)點(diǎn)
度: 子節(jié)點(diǎn)的個(gè)數(shù)稱為度  

樹(shù)的分類

  • 一般樹(shù): 任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)都不受限制讳癌。
  • 二叉樹(shù):任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)最多兩個(gè),且子節(jié)點(diǎn)的個(gè)數(shù)不可更改茴她。
    1. 一般二叉樹(shù)
    2. 滿二叉樹(shù):在不增加樹(shù)的層數(shù)的前提下寻拂,無(wú)法再添加一個(gè)節(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。
    3. 完全二叉樹(shù):如果只是刪除了滿二叉樹(shù)最低存最右邊的若干個(gè)連續(xù)節(jié)點(diǎn)丈牢,這樣形成的二叉樹(shù)就是完全二叉樹(shù)祭钉。
  • 森林:n個(gè)互不相交的樹(shù)的集合。

樹(shù)的存儲(chǔ)

二叉樹(shù)的存儲(chǔ)

連續(xù)存儲(chǔ)【完全二叉樹(shù)】
1. 優(yōu)點(diǎn): 查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)(也包括有沒(méi)有子節(jié)點(diǎn))赡麦。
2. 缺點(diǎn):耗用內(nèi)存空間過(guò)大朴皆。
鏈試存儲(chǔ)
1. 優(yōu)點(diǎn):耗用內(nèi)存空間小。

一般樹(shù)的存儲(chǔ)
1.雙親表示法: 求父節(jié)點(diǎn)方便泛粹。

樹(shù)結(jié)構(gòu).png

樹(shù)的雙親表示法.png

代碼結(jié)構(gòu)定義

//樹(shù)的雙親表示法節(jié)點(diǎn)結(jié)構(gòu)的定義
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode {
    ElemType data; //節(jié)點(diǎn)數(shù)據(jù)
    int parent; //雙親位置
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r; //根的位置
    int n; //節(jié)點(diǎn)數(shù)目
}PTree;

上面的樹(shù)存儲(chǔ)結(jié)構(gòu)圖根據(jù)某個(gè)節(jié)點(diǎn)的parent指針找到它的雙親節(jié)點(diǎn)遂铡,所用的時(shí)間復(fù)雜度為O(1),索引到parent的值為-1,表示找到了樹(shù)節(jié)點(diǎn)的根晶姊。如果我們要知道某個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)扒接,就的遍歷整個(gè)樹(shù)結(jié)構(gòu)了。
下面是改進(jìn)后的樹(shù)結(jié)構(gòu)存儲(chǔ)圖,可以比較方便的求出某個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)钾怔。

圖片.png

改進(jìn)過(guò)后的樹(shù)存儲(chǔ)結(jié)構(gòu)碱呼,沒(méi)法表示樹(shù)結(jié)構(gòu)中兄弟之間的關(guān)系?
如下是改進(jìn)過(guò)后最終的樹(shù)結(jié)構(gòu)存儲(chǔ)圖:

圖片.png

2.孩子表示法:求子節(jié)點(diǎn)方便宗侦, 求父節(jié)點(diǎn)麻煩愚臀。存儲(chǔ)結(jié)構(gòu)如下:

圖片.png

3.雙親孩子表示法:求父節(jié)點(diǎn)和子節(jié)點(diǎn)都很方便

圖片.png

代碼結(jié)構(gòu)如下:

#define MAX_TREE_SIZE 100
typedef char ElemType;
//孩子節(jié)點(diǎn)
typedef struct CTNode {
    int child; //孩子節(jié)點(diǎn)的下標(biāo)
    struct CTNode *next;//指向下一個(gè)孩子節(jié)點(diǎn)的指針
} *ChildPtr;

typedef struct {
    ElemType data; //存放在樹(shù)中的節(jié)點(diǎn)的數(shù)據(jù)
    int parent; //存放雙親的下標(biāo)
    ChildPtr firstchild; //指向第一個(gè)孩子的指針
}CTBox;
//樹(shù)結(jié)構(gòu)
typedef struct {
    CTBox nodes[MAX_TREE_SIZE]; //節(jié)點(diǎn)數(shù)組
    int r, n;
};

4.二叉樹(shù)表示法:把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)
具體轉(zhuǎn)換方法(把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)):設(shè)法保證任意一個(gè)節(jié)點(diǎn)的左指針域指向他的第一個(gè)孩子,右指針域指向他的下一個(gè)兄弟矾利,只要能滿足此條件就能把一個(gè)普通的樹(shù)轉(zhuǎn)換成二叉樹(shù)姑裂,一個(gè)普通樹(shù)轉(zhuǎn)換成二叉樹(shù)一定沒(méi)有右子樹(shù)。

森林的存儲(chǔ)

先把森林轉(zhuǎn)化為二叉樹(shù)男旗,再存儲(chǔ)二叉樹(shù)    

樹(shù)的操作

遍歷

先序遍歷【先訪問(wèn)根節(jié)點(diǎn)】: 先訪問(wèn)根節(jié)點(diǎn)舶斧,再先序訪問(wèn)左子樹(shù),再先序訪問(wèn)右子樹(shù)
中序遍歷【中間訪問(wèn)根節(jié)點(diǎn)】:中序遍歷左子樹(shù)察皇,再訪問(wèn)根節(jié)點(diǎn)茴厉,再中序遍歷右子樹(shù)
后序遍歷【最后訪問(wèn)根節(jié)點(diǎn)】:先中序遍歷左子樹(shù),中序遍歷右子樹(shù)什荣,再訪問(wèn)根節(jié)點(diǎn)

已知兩種遍歷序列求原始二叉樹(shù)

通過(guò)先序和中序或者中序和后序我們可以還原出原始二叉樹(shù)矾缓,但 `通過(guò)先序和后序是無(wú)法還原出原始的二叉樹(shù)` 
換種說(shuō)法:只有通過(guò)先序和中序,或通過(guò)中序和后序稻爬,我們才可以唯一的確定一個(gè)二叉樹(shù)而账。

應(yīng)用

1. 樹(shù)是數(shù)據(jù)庫(kù)中數(shù)據(jù)組織一種重要的形式
2. 操作系統(tǒng)子父進(jìn)程的關(guān)系本身就是一棵樹(shù)
3. 面向?qū)ο笳Z(yǔ)言中類的繼承關(guān)系
4. 赫夫曼樹(shù)      

樹(shù)的遍歷相關(guān)算法的實(shí)現(xiàn)(C語(yǔ)言)

#include <stdio.h>
#include <stdlib.h>

//定義二叉樹(shù)的節(jié)點(diǎn)
struct BTNode {
    int data; //存放二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域
    struct BTNode *pLchild; //指向左孩子結(jié)點(diǎn)的指針
    struct BTNode *pRchild; //指向右孩子結(jié)點(diǎn)的指針
};

//創(chuàng)建一顆二叉樹(shù),返回頭結(jié)點(diǎn)的指針
struct BTNode *CreateBTree(void);
//先序遍歷二叉樹(shù)
void PreTraverseBTree(struct BTNode *pT);
//中序遍歷二叉樹(shù)
void InTraverseBTee(struct BTNode *pT);
//后續(xù)遍歷二叉樹(shù)
void PostTraverseBTree(struct BTNode *pT);


struct BTNode *CreateBTree(void)
{
    struct BTNode * pA = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pB = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pC = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pD = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pE = (struct BTNode*)malloc(sizeof(struct BTNode));
    
    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';
    
    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;
    return pA;
}

void PreTraverseBTree(struct BTNode *pT) {
    //先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
    if (pT == NULL)
    {
        return;
    }
    printf("%c\n", pT->data);
    PreTraverseBTree(pT->pLchild);
    PreTraverseBTree(pT->pRchild);
}

void InTraverseBTee(struct BTNode *pT) {
    //先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
    if (pT == NULL)
    {
        return;
    }
    InTraverseBTee(pT->pLchild);
    printf("%c\n", pT->data);
    InTraverseBTee(pT->pRchild);
}

void PostTraverseBTree(struct BTNode *pT) {
    //先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
    if (pT == NULL)
    {
        return;
    }
    PostTraverseBTree(pT->pLchild);
    PostTraverseBTree(pT->pRchild);
    printf("%c\n", pT->data); 
}

int main() {
    struct BTNode *pT = CreateBTree();
    printf("先序遍歷\n");
    PreTraverseBTree(pT);
    printf("中序遍歷\n");
    InTraverseBTee(pT);
    printf("后序遍歷\n");
    PostTraverseBTree(pT);
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末因篇,一起剝皮案震驚了整個(gè)濱河市泞辐,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌竞滓,老刑警劉巖咐吼,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異商佑,居然都是意外死亡锯茄,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)茶没,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)肌幽,“玉大人,你說(shuō)我怎么就攤上這事抓半∥辜保” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵笛求,是天一觀的道長(zhǎng)廊移。 經(jīng)常有香客問(wèn)我糕簿,道長(zhǎng),這世上最難降的妖魔是什么狡孔? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任懂诗,我火速辦了婚禮,結(jié)果婚禮上苗膝,老公的妹妹穿的比我還像新娘殃恒。我一直安慰自己,他們只是感情好辱揭,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布芋类。 她就那樣靜靜地躺著,像睡著了一般界阁。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上胖喳,一...
    開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1 312
  • 那天泡躯,我揣著相機(jī)與錄音,去河邊找鬼丽焊。 笑死较剃,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的技健。 我是一名探鬼主播写穴,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼雌贱!你這毒婦竟也來(lái)了啊送?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤欣孤,失蹤者是張志新(化名)和其女友劉穎馋没,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體降传,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡篷朵,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了婆排。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片声旺。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖段只,靈堂內(nèi)的尸體忽然破棺而出腮猖,到底是詐尸還是另有隱情,我是刑警寧澤赞枕,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布缚够,位于F島的核電站幔妨,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏谍椅。R本人自食惡果不足惜误堡,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望雏吭。 院中可真熱鬧锁施,春花似錦、人聲如沸杖们。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)摘完。三九已至姥饰,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間孝治,已是汗流浹背列粪。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工纽门, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留憨愉,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓堰汉,卻偏偏與公主長(zhǎng)得像杭措,于是被迫代替她去往敵國(guó)和親费什。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 樹(shù)是n(n >= 0)個(gè)結(jié)點(diǎn)的有限集手素。n=0時(shí)稱為空樹(shù)鸳址。在任意一顆非空樹(shù)中: 1、有且僅有一個(gè)特定的稱為根(Roo...
    jtsky閱讀 912評(píng)論 0 0
  • 樹(shù)的概述 樹(shù)是一種非常常用的數(shù)據(jù)結(jié)構(gòu)泉懦,樹(shù)與前面介紹的線性表氯质,棧,隊(duì)列等線性結(jié)構(gòu)不同祠斧,樹(shù)是一種非線性結(jié)構(gòu) 1.樹(shù)的定...
    Jack921閱讀 4,462評(píng)論 1 31
  • 樹(shù)(tree)是一種抽象數(shù)據(jù)類型(ADT)或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)闻察,用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。...
    曾大穩(wěn)丶閱讀 1,008評(píng)論 0 1
  • 前面講到的順序表、棧和隊(duì)列都是一對(duì)一的線性結(jié)構(gòu)吴超,這節(jié)講一對(duì)多的線性結(jié)構(gòu)——樹(shù)钉嘹。「一對(duì)多」就是指一個(gè)元素只能有一個(gè)前...
    Alent閱讀 2,242評(píng)論 1 28
  • 二叉樹(shù)的定義#### 二叉樹(shù)是n(n>=0)個(gè)具有相同類型的元素的有限集合鲸阻,當(dāng)n=0時(shí)稱為空二叉樹(shù)跋涣,當(dāng)n>0時(shí)缨睡,數(shù)...
    kylinxiang閱讀 1,405評(píng)論 0 2