本文主要是對(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;
}