97超碰人人妻,亚洲精品一二三四区

1. 概念

與線性結(jié)構(gòu)的“一對(duì)一”不同，樹(shù)是“一對(duì)多”的數(shù)據(jù)結(jié)構(gòu)。

樹(shù)是有限個(gè)結(jié)點(diǎn)n（n >= 0）的集合。

n為0時(shí)稱為空樹(shù)；

不為0時(shí)，有且只有一個(gè)結(jié)點(diǎn)作為樹(shù)的根結(jié)點(diǎn)。

n大于1時(shí)，除根結(jié)點(diǎn)外的其他結(jié)點(diǎn)可以分為m（m > 0）個(gè)互不相交的有限集合T1...Tm，每個(gè)子集合又是一棵樹(shù)，稱為子樹(shù)。

下圖即為一棵樹(shù)：

樹(shù)的概念.jpg

1.1 樹(shù)的“度”

每個(gè)結(jié)點(diǎn)包含的子結(jié)點(diǎn)的個(gè)數(shù)稱為結(jié)點(diǎn)的“度”（degree）。
度為0的結(jié)點(diǎn)為“葉子結(jié)點(diǎn)”或“終端結(jié)點(diǎn)”；度不為0的結(jié)點(diǎn)稱為“分支結(jié)點(diǎn)”或“非終端結(jié)點(diǎn)”。

我們將一棵樹(shù)中所有子結(jié)點(diǎn)的“度”中的最大值稱作樹(shù)的度。

示意圖中樹(shù)的度為3（結(jié)點(diǎn)D的度最大，是3）。

1.2 結(jié)點(diǎn)間的關(guān)系

結(jié)點(diǎn)的子樹(shù)中的根結(jié)點(diǎn)叫做該結(jié)點(diǎn)的孩子（Child）結(jié)點(diǎn)；該結(jié)點(diǎn)稱為孩子的雙親（Parent）結(jié)點(diǎn)；同一雙親結(jié)點(diǎn)的子結(jié)點(diǎn)互為兄弟（Sibling）結(jié)點(diǎn)。

例如，在示意圖中，結(jié)點(diǎn)D是B的孩子結(jié)點(diǎn)，C是B的兄弟結(jié)點(diǎn)，A是B的雙親結(jié)點(diǎn)。

注：以下將雙親結(jié)點(diǎn)簡(jiǎn)稱為“父結(jié)點(diǎn)”，孩子結(jié)點(diǎn)稱為“子結(jié)點(diǎn)”。

1.3 樹(shù)的“深度”

從根結(jié)點(diǎn)開(kāi)始，作為樹(shù)的第一層（Level）；其子結(jié)點(diǎn)作為第二層，以此類推。

樹(shù)的最大層數(shù)稱為該樹(shù)的“深度”（Depth）。

由于示意圖中的樹(shù)分為四層，故其深度為4。其中，同一層的結(jié)點(diǎn)互為堂兄弟結(jié)點(diǎn)。如第三層的D、E和F結(jié)點(diǎn)。

1.4 其他概念

若樹(shù)從左至右為有序，且各子結(jié)點(diǎn)的順序不可調(diào)換，則此樹(shù)可以稱為“有序樹(shù)”。
森林（Forest）是m（m >= 0）棵互不相交的樹(shù)的集合。

1.5 結(jié)構(gòu)對(duì)比

與線性結(jié)構(gòu)的對(duì)比如下：

線性結(jié)構(gòu)：

頭元素：無(wú)前驅(qū)結(jié)點(diǎn)

尾元素：無(wú)后繼結(jié)點(diǎn)

中間元素：一個(gè)前驅(qū)結(jié)點(diǎn)，一個(gè)后繼結(jié)點(diǎn)

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

根結(jié)點(diǎn)：無(wú)父結(jié)點(diǎn)，唯一

葉子結(jié)點(diǎn)：無(wú)子結(jié)點(diǎn)，自身可以有多個(gè)

分支結(jié)點(diǎn)：有父結(jié)點(diǎn)，存在1個(gè)或多個(gè)子結(jié)點(diǎn)

2. 存儲(chǔ)結(jié)構(gòu)

利用順序和鏈?zhǔn)酱鎯?chǔ)方式，我們可以將樹(shù)的存儲(chǔ)方式簡(jiǎn)單介紹三種：

雙親表示法
孩子表示法
孩子兄弟表示法（二叉樹(shù)）

2.1 雙親表示法

雙親表示法使用順序存儲(chǔ)結(jié)構(gòu)，將所有結(jié)點(diǎn)依次存儲(chǔ)在連續(xù)的空間中。
最簡(jiǎn)單的就是使用一個(gè)parent域來(lái)標(biāo)明自身的父結(jié)點(diǎn)。其結(jié)構(gòu)如下：

data	parent
數(shù)據(jù)域	父結(jié)點(diǎn)索引（數(shù)組下標(biāo)）

以示意圖為例，使用雙親表示法可以表示為：

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

根據(jù)此存儲(chǔ)方式，可以直接查詢出每個(gè)子結(jié)點(diǎn)的父結(jié)點(diǎn)，其時(shí)間復(fù)雜度固定為O(1)。

可以根據(jù)需要，對(duì)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展：如添加指向第一個(gè)孩子結(jié)點(diǎn)的索引域firstChild；添加指向兄弟結(jié)點(diǎn)的索引域rightSib等。這種方式可以適時(shí)通過(guò)擴(kuò)展并添加存儲(chǔ)空間來(lái)提高訪問(wèn)效率。

2.2 孩子表示法

由于每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)不確定，可以通過(guò)鏈表來(lái)表示每個(gè)結(jié)點(diǎn)下的子樹(shù)。且由于我們?cè)谛枰獣r(shí)可以方便地遍歷樹(shù)中的所有結(jié)點(diǎn)，可以考慮將所有結(jié)點(diǎn)保存在順序存儲(chǔ)結(jié)構(gòu)中。故孩子表示法的具體方法為：把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，以單鏈表為存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則此單鏈表為空表。然后，將n個(gè)頭指針又組成一個(gè)線性表，以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在一個(gè)一維數(shù)組中。

故示意圖中的樹(shù)，使用孩子表示法可以表示為：

樹(shù)--孩子表示法.jpg

其中結(jié)點(diǎn)分為兩種：

孩子鏈表中的孩子結(jié)點(diǎn)：

child	next
結(jié)點(diǎn)索引（順序數(shù)組的下標(biāo)）	兄弟結(jié)點(diǎn)索引

表頭數(shù)組的表頭結(jié)點(diǎn)

data	firstChild
數(shù)據(jù)域	頭指針域（存儲(chǔ)對(duì)應(yīng)孩子鏈表的頭指針）

對(duì)于此存儲(chǔ)結(jié)構(gòu)，要查找某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，或查找某結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，只要查找對(duì)應(yīng)的孩子結(jié)點(diǎn)單鏈表即可。

2.3 孩子兄弟表示法

任意一棵樹(shù)，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此此節(jié)點(diǎn)包括兩個(gè)指針域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和此結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。

data	firstChild	rightSib
數(shù)據(jù)域	第一個(gè)孩子結(jié)點(diǎn)的存儲(chǔ)地址	右兄弟結(jié)點(diǎn)的存儲(chǔ)地址

故示意圖中的樹(shù)，使用孩子兄弟表示法可以表示為：

樹(shù)--孩子兄弟表示法.jpg

使用此方式，可以很方便地查找某結(jié)點(diǎn)的第幾個(gè)子結(jié)點(diǎn)：只要找到該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)后，依次查找其兄弟結(jié)點(diǎn)即可。

通過(guò)此種表示方法，我們可以發(fā)現(xiàn)，標(biāo)準(zhǔn)的樹(shù)被轉(zhuǎn)換成了二叉樹(shù)表示（每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)）。

3. 二叉樹(shù)

3.1 定義

每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)（子結(jié)點(diǎn)），故二叉樹(shù)的度不超過(guò)2。
左右子樹(shù)有序，不能顛倒。
結(jié)點(diǎn)若只有一棵子樹(shù)，也要區(qū)分是左還是右子樹(shù)。

如下圖，二者是兩棵不同的二叉樹(shù)：

樹(shù)--二叉樹(shù)區(qū)分.jpg

3.2 存儲(chǔ)結(jié)構(gòu)

3.2.1 順序存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)一般只適用于完全二叉樹(shù)**。

完全二叉樹(shù)：

葉子結(jié)點(diǎn)只出現(xiàn)在二叉樹(shù)的最后兩層

最后一層的葉子結(jié)點(diǎn)都是左結(jié)點(diǎn)；倒數(shù)第二層的葉子結(jié)點(diǎn)都是右結(jié)點(diǎn)

滿二叉樹(shù)（只有最后一層存在，且全都是葉子結(jié)點(diǎn)的二叉樹(shù)）屬于完全二叉樹(shù)

樹(shù)--二叉樹(shù)的順序存儲(chǔ).jpg

如圖所示，用一維數(shù)組存儲(chǔ)二叉樹(shù)的所有結(jié)點(diǎn)，通過(guò)數(shù)組下標(biāo)來(lái)提現(xiàn)二叉樹(shù)中結(jié)點(diǎn)間的關(guān)系。
但是，當(dāng)二叉樹(shù)中有過(guò)多空余結(jié)點(diǎn)（如圖中的黃色不存在結(jié)點(diǎn)）時(shí)會(huì)導(dǎo)致空間浪費(fèi)，故一般只使用順序結(jié)構(gòu)存儲(chǔ)完全二叉樹(shù)。

3.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--二叉鏈表

二叉鏈表：每個(gè)數(shù)據(jù)節(jié)點(diǎn)包含本身的數(shù)據(jù)域和兩個(gè)指針域，分別指向兩個(gè)可能的孩子結(jié)點(diǎn)，這種結(jié)點(diǎn)組成的鏈表稱為二叉鏈表。

結(jié)點(diǎn)結(jié)構(gòu)如下：

lchild	data	rchild
左孩子結(jié)點(diǎn)的存儲(chǔ)地址	數(shù)據(jù)域	右孩子結(jié)點(diǎn)的存儲(chǔ)地址

/** 二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)體 */
typedef struct BiTNode {
    TElemType data; // 數(shù)據(jù)域
    struct BiTNode *lchild; // 左孩子結(jié)點(diǎn)指針
    struct BiTNode *rchild; // 右孩子結(jié)點(diǎn)指針
} BiTNode, *BiTree;

下圖為二叉鏈表的表述示意圖：

樹(shù)--二叉鏈表.jpg

3.3 二叉樹(shù)的遍歷

二叉樹(shù)的遍歷（traversing binary tree）是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

若以從左到右方向限定，主要的遍歷方式分為以下四種：

前序遍歷
中序遍歷
后序遍歷
層序遍歷

與定義二叉樹(shù)的方式一樣，其遍歷也是以遞歸的方式進(jìn)行。

3.3.1 前序遍歷

遍歷方式：先訪問(wèn)根節(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再前序遍歷右子樹(shù)。

void PreOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    // 訪問(wèn)根節(jié)點(diǎn)
    printf("%c", T->data);
    // 遍歷左子樹(shù)
    PreOrderTraverse(T->lchild);
    // 遍歷右子樹(shù)
    PreOrderTraverse(T->rchild);
}

3.3.2 中序遍歷

遍歷方式：先中序遍歷根節(jié)點(diǎn)的左子樹(shù)，然后是根節(jié)點(diǎn)，再中序遍歷右子樹(shù)。

void InOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    // 遍歷左子樹(shù)
    InOrderTraverse(T->lchild);
    // 訪問(wèn)根節(jié)點(diǎn)
    printf("%c", T->data);
    // 遍歷右子樹(shù)
    InOrderTraverse(T->rchild);
}

3.3.3 后續(xù)遍歷

遍歷方式：從左到右，先葉子后結(jié)點(diǎn)，全部訪問(wèn)完左右子樹(shù)后，最后訪問(wèn)根結(jié)點(diǎn)。

void PostOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    // 遍歷左子樹(shù)
    PostOrderTraverse(T->lchild);
    // 遍歷右子樹(shù)
    PostOrderTraverse(T->rchild);
    // 訪問(wèn)根節(jié)點(diǎn)
    printf("%c", T->data);
}

3.4 二叉樹(shù)的創(chuàng)建

這里以前序方式創(chuàng)建。與前序遍歷相同，創(chuàng)建時(shí)按照前序遍歷的方式依次遞歸輸入結(jié)點(diǎn)數(shù)據(jù)即可：

/** 創(chuàng)建二叉樹(shù)【前序遍歷法創(chuàng)建：根--左--右】 */
void CreateBiTree(BiTree *T) {
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL; // 代表此結(jié)點(diǎn)位置無(wú)數(shù)據(jù)（數(shù)據(jù)為空）
        return;
    } else {
        // 分配空間，創(chuàng)建新結(jié)點(diǎn)
        *T = (BiTree)malloc(sizeof(BiTNode));
        // 內(nèi)存分配失敗，退出
        if (!*T) {
            exit(OVERFLOW);
        }
        
        // 前序遍歷方式賦值
        
        // 1. 賦值根節(jié)點(diǎn)
        (*T)->data = ch;
        // 2. 左孩子結(jié)點(diǎn)遞歸
        CreateBiTree(&((*T)->lchild));
        // 3. 右孩子結(jié)點(diǎn)遞歸
        CreateBiTree(&((*T)->rchild));
    }
}

如下圖所示，依照代碼，先將給定的二叉樹(shù)轉(zhuǎn)化為擴(kuò)展二叉樹(shù)**。

擴(kuò)展二叉樹(shù)：
將給定的二叉樹(shù)的每個(gè)結(jié)點(diǎn)的空指針設(shè)置一個(gè)虛擬結(jié)點(diǎn)，并指定一個(gè)特殊值（這里定義為“#”）。

樹(shù)--二叉樹(shù)的創(chuàng)建.jpg

二叉樹(shù)的創(chuàng)建與三種遍歷方式，可查看此示例：項(xiàng)目地址

3.5 線索二叉樹(shù)

3.5.1 線索化過(guò)程

此二叉鏈表雖然功能強(qiáng)大，但弱點(diǎn)顯而易見(jiàn)：就是每次只能通過(guò)指定方式的遍歷，才可以確定每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)和后綴結(jié)點(diǎn)。而且我們可以發(fā)現(xiàn)，在下面的二叉鏈表示意圖中，有n+1（即2n個(gè)總lchild和rchild指針個(gè)數(shù) 與 n-1個(gè)連線的差）個(gè)空余指針域（存儲(chǔ)的是“^”），隨著二叉樹(shù)的增長(zhǎng)，浪費(fèi)的空間會(huì)越來(lái)越多。

樹(shù)--二叉鏈表.jpg

因此，我們可以使用這些空余空間來(lái)保存每個(gè)結(jié)點(diǎn)的前趨和后繼結(jié)點(diǎn)的信息，以解決上述問(wèn)題。而解決此問(wèn)題的過(guò)程，叫做線索化，線索化后的二叉鏈表叫做線索鏈表，對(duì)應(yīng)的樹(shù)叫做線索二叉樹(shù)。

具體做法是：在使用某種順序遍歷每個(gè)結(jié)點(diǎn)時(shí)，若沒(méi)有左孩子結(jié)點(diǎn)，其lchild保存的是前趨結(jié)點(diǎn)的指針；若沒(méi)有右孩子結(jié)點(diǎn)，其rchild保存的是后繼結(jié)點(diǎn)的指針。

如上圖中的二叉樹(shù)，其中序遍歷后的結(jié)果為HDIBJEAFCG，根據(jù)遍歷結(jié)果對(duì)該二叉鏈表進(jìn)行線索化的結(jié)果如下：

樹(shù)--線索二叉樹(shù)1.jpg

可以看到，通過(guò)線索化，不僅解決了空間浪費(fèi)問(wèn)題，還解決了前趨和后繼結(jié)點(diǎn)的記錄問(wèn)題，提高了訪問(wèn)效率。

3.5.2 區(qū)分結(jié)點(diǎn)類型

此時(shí)線索二叉樹(shù)還存在一個(gè)問(wèn)題：我們無(wú)法區(qū)分lchild指向的結(jié)點(diǎn)是前趨結(jié)點(diǎn)還是左孩子節(jié)點(diǎn)，對(duì)于rchild也是如此。

此時(shí)，需要針對(duì)每個(gè)指針域分別設(shè)置一個(gè)布爾類型的數(shù)據(jù)域，在線索化的過(guò)程中，根據(jù)實(shí)際情況進(jìn)行區(qū)分（是前趨或后繼結(jié)點(diǎn)時(shí)為1，是孩子結(jié)點(diǎn)時(shí)為0）。

結(jié)點(diǎn)結(jié)構(gòu)如下：

左孩子結(jié)點(diǎn)地址	左標(biāo)識(shí)符	數(shù)據(jù)域	右標(biāo)識(shí)符	右孩子結(jié)點(diǎn)地址
lchild	ltag	data	rtag	rchild

對(duì)應(yīng)實(shí)現(xiàn)如下：

/** 枚舉變量，用于標(biāo)識(shí)符賦值 */
typedef enum {
    /** 是孩子結(jié)點(diǎn) */
    Link,
    /** 是前趨或后綴結(jié)點(diǎn) */
    Thread
} PointerTag;

/** 線索二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu) */
typedef struct BiThrNode {
    /** 數(shù)據(jù)域 */
    TElemType data;
    /** 左結(jié)點(diǎn)指針 */
    struct BiThrNode *lchild;
    /** 左結(jié)點(diǎn)標(biāo)識(shí)符 */
    PointerTag LTag;
    /** 右結(jié)點(diǎn)指針 */
    struct BiThrNode *rchild;
    /** 右結(jié)點(diǎn)標(biāo)識(shí)符 */
    PointerTag RTag;
} BiThrNode, *BiThrTree; // 定義為線索二叉樹(shù)結(jié)點(diǎn)及線索二叉樹(shù)指針

添加結(jié)點(diǎn)類型區(qū)分后的線索二叉樹(shù)如下：

樹(shù)--線索二叉樹(shù)2.jpg

這樣在訪問(wèn)指定節(jié)點(diǎn)時(shí)，根據(jù)ltag和rtag的值即可區(qū)分相鄰結(jié)點(diǎn)是前趨后繼結(jié)點(diǎn)或是孩子結(jié)點(diǎn)了。

線索化過(guò)程的代碼如下（這里使用中序遍歷方式）：

/** 當(dāng)前訪問(wèn)節(jié)點(diǎn) */
BiThrTree currentP = NULL;

/** 中序遍歷線索化 */
void InThreading(BiThrTree p) {
    if (!p) {
        // 結(jié)點(diǎn)不存在，返回
        return;
    }
    
    if (!p->lchild && !p->rchild) {
        // 左右子結(jié)點(diǎn)均不存在，即是葉子結(jié)點(diǎn)【防止最后一個(gè)結(jié)點(diǎn)無(wú)修改RTag】
        p->LTag = Thread;
        p->RTag = Thread;
    }
    
    // 遞歸線索化左結(jié)點(diǎn)
    InThreading(p->lchild);
    
    // 自身數(shù)據(jù)線索化（由于是中序遍歷【左--中--右】，此時(shí)右結(jié)點(diǎn)還沒(méi)有訪問(wèn)到，故只處理當(dāng)前和前一個(gè)結(jié)點(diǎn)即可）
    
    if (!(p->lchild)) {
        // 左結(jié)點(diǎn)為空，即沒(méi)有左孩子，故當(dāng)前指向前趨結(jié)點(diǎn)
        p->LTag = Thread;
        p->lchild = currentP;
    } else {
        // 包含左孩子
        p->LTag = Link;
    }
    
    if (currentP) {
        if (!(currentP->rchild)) {
            // 前一個(gè)結(jié)點(diǎn)的右結(jié)點(diǎn)指針為空，即沒(méi)有右孩子，故指向后繼結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)）
            currentP->RTag = Thread;
            currentP->rchild = p;
        } else {
            // 包含右孩子
            currentP->RTag = Link;
        }
    }
    
    
    // 記錄當(dāng)前結(jié)點(diǎn)
    currentP = p;
    
    // 遞歸線索化右結(jié)點(diǎn)
    InThreading(p->rchild);
}

由上圖即可看出，如果在二叉樹(shù)的根結(jié)點(diǎn)之前再插入一個(gè)頭結(jié)點(diǎn)，此時(shí)的線索二叉樹(shù)實(shí)際上就是一個(gè)雙向鏈表結(jié)構(gòu)。其結(jié)構(gòu)示意圖如下：

樹(shù)--線索二叉樹(shù)3.jpg

插入頭結(jié)點(diǎn)的簡(jiǎn)單方法如下：

/** 向線索二叉樹(shù)中插入頭結(jié)點(diǎn) */
BiThrTree insertHeadNodeToBiThrTree(BiThrTree biTree) {
    if (biTree == NULL) {
        return NULL;
    }
    
    // 創(chuàng)建頭節(jié)點(diǎn)
    BiThrTree headNode = (BiThrTree)malloc(sizeof(BiThrNode));
    // 左孩子指向線索二叉樹(shù)的根結(jié)點(diǎn)
    headNode->lchild = biTree;
    headNode->LTag = Link;
    // 右孩子指向中序遍歷的最后一個(gè)結(jié)點(diǎn)
    BiThrTree inOrderTailNode = biTree;
    while (inOrderTailNode->RTag == Link) {
        inOrderTailNode = inOrderTailNode->rchild;
    }
    // 此時(shí)inOrderTailNode即為最后一個(gè)結(jié)點(diǎn)
    headNode->rchild = inOrderTailNode;
    headNode->RTag = Thread; // 并不是右孩子
    
    // targetNode的后繼結(jié)點(diǎn)指向頭結(jié)點(diǎn)
    inOrderTailNode->rchild = headNode;
    
    // 中序遍歷的第一個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)指向頭結(jié)點(diǎn)
    BiThrTree inOrderFirstNode = biTree;
    while (inOrderFirstNode->LTag == Link) {
        inOrderFirstNode = inOrderFirstNode->lchild;
    }
    // 此時(shí)inOrderFirstNode即為第一個(gè)結(jié)點(diǎn)
    inOrderFirstNode->lchild = headNode;
    
    return headNode;
}

最終，通過(guò)訪問(wèn)雙向鏈表的方式，中序遍歷輸出此二叉樹(shù)的方式如下：

/** 中序遍歷【掃描二叉鏈表方式】 */
void InOrderTraverse_Thr(BiThrTree T) {
    // 中序遍歷，即從頭結(jié)點(diǎn)開(kāi)始掃描，
    // 1. 首先找到最左邊的結(jié)點(diǎn)（沒(méi)有左孩子的），
    // 2. 然后找其后繼結(jié)點(diǎn)（子樹(shù)的根），
    // 3. 最后是其右結(jié)點(diǎn)（右孩子或后繼）
    // 直到掃描到的結(jié)點(diǎn)是頭結(jié)點(diǎn)，結(jié)束
    
    // 指向根結(jié)點(diǎn)（從根結(jié)點(diǎn)開(kāi)始）
    BiThrTree currentNode = T->lchild;
    
    // 遍歷結(jié)束時(shí)，指向頭結(jié)點(diǎn)
    while (currentNode != T) {
        // 1. 找到當(dāng)前子樹(shù)最左邊的結(jié)點(diǎn)（沒(méi)有左孩子的）
        while (currentNode->LTag == Link) {
            // 有左孩子，繼續(xù)查找
            currentNode = currentNode->lchild;
        }
        // 找到了最左邊的結(jié)點(diǎn)，輸出
        printf("%hhd ", currentNode->data);
        
        // 2. 一直向后找到所有后繼結(jié)點(diǎn)（即對(duì)應(yīng)子樹(shù)的根）
        while (currentNode->RTag == Thread && currentNode->rchild != T) {
            currentNode = currentNode->rchild;
            // 找到了后繼結(jié)點(diǎn)，輸出
            printf("%hhd ", currentNode->data);
        }
        
        // 3. 指向右結(jié)點(diǎn)（下一個(gè)結(jié)點(diǎn)，不管結(jié)點(diǎn)類型，準(zhǔn)備下次循環(huán)）
        currentNode = currentNode->rchild;
    }
}

線索化及遍歷的完整過(guò)程，可查看此示例：項(xiàng)目地址

3.6 樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)

由于二叉樹(shù)的結(jié)構(gòu)穩(wěn)定（每個(gè)結(jié)點(diǎn)只有左右兩個(gè)孩子），其性質(zhì)也容易研究，故在某些情況下，將普通的樹(shù)甚至森林轉(zhuǎn)換為二叉樹(shù)即可對(duì)它們進(jìn)行問(wèn)題的研究（如遍歷等）。

3.6.1 樹(shù) => 二叉樹(shù)

轉(zhuǎn)換規(guī)則：

在兄弟結(jié)點(diǎn)與其左方的結(jié)點(diǎn)之間添加連接線。
在結(jié)點(diǎn)的所有子孩子中，除了左邊第一個(gè)孩子結(jié)點(diǎn)外，其他所有兄弟孩子結(jié)點(diǎn)與父結(jié)點(diǎn)間的連線去除。
調(diào)整層次，結(jié)點(diǎn)的第一個(gè)子孩子作為二叉的左孩子，兄弟孩子作為“前一個(gè)”結(jié)點(diǎn)的右孩子。

示例：

樹(shù)--樹(shù)轉(zhuǎn)換二叉樹(shù).jpg

轉(zhuǎn)換過(guò)程：

樹(shù)--樹(shù)轉(zhuǎn)換二叉樹(shù)2.jpg

樹(shù)--樹(shù)轉(zhuǎn)換二叉樹(shù)3.jpg

樹(shù)--樹(shù)轉(zhuǎn)換二叉樹(shù)4.jpg

3.6.2 森林 => 二叉樹(shù)

可以將森林中的每一棵樹(shù)看做是兄弟，利用兄弟結(jié)點(diǎn)的合并方式（作為前一個(gè)結(jié)點(diǎn)的右孩子）進(jìn)行合并，最終合成一棵二叉樹(shù)：

把每一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)。
依次將后一棵樹(shù)的根結(jié)點(diǎn)作為前一棵樹(shù)的根結(jié)點(diǎn)的右孩子。連線完成后，即可得到合成的二叉樹(shù)。

示例：

樹(shù)--森林轉(zhuǎn)二叉樹(shù).jpg

轉(zhuǎn)換過(guò)程：

樹(shù)--森林轉(zhuǎn)二叉樹(shù)2.jpg

樹(shù)--森林轉(zhuǎn)二叉樹(shù)3.jpg

3.7 赫夫曼樹(shù)及霍夫曼編碼

3.7.1 概念介紹

赫夫曼樹(shù)是在二叉樹(shù)的基礎(chǔ)上設(shè)計(jì)而來(lái)。赫夫曼樹(shù)的每個(gè)葉子結(jié)點(diǎn)都包含對(duì)應(yīng)的權(quán)值（Weight）。兩個(gè)結(jié)點(diǎn)之間經(jīng)過(guò)的所有分支叫做路徑，路徑上分支的個(gè)數(shù)叫做路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度就是從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度的總和**。

樹(shù)--赫夫曼樹(shù).jpg

圖中的二叉樹(shù)的路徑長(zhǎng)度為（以A-E的順序）：3 + 3 + 2 + 2 + 2 = 12。

霍夫曼樹(shù)需要引入權(quán)的概念，故我們得到了帶權(quán)路徑的算法：
結(jié)點(diǎn)的帶權(quán)路徑 = 結(jié)點(diǎn)從根到自身的路徑長(zhǎng)度 * 自身權(quán)重

因此樹(shù)的帶權(quán)路徑長(zhǎng)度即為所有葉子結(jié)點(diǎn)帶權(quán)路徑的總和，稱作WPL。

圖中二叉樹(shù)的WPL為：3 * 5 + 3 * 15 + 2 * 40 + 2 * 30 + 2 * 10 = 220。

在帶有權(quán)重的一組葉子結(jié)點(diǎn)所組成的二叉樹(shù)中，WPL最小的可稱作霍夫曼樹(shù)。

3.7.2 生成方法

將所有結(jié)點(diǎn)按照權(quán)值升序排列，生成有序樹(shù)集合（每棵樹(shù)即為單獨(dú)的葉子結(jié)點(diǎn)）。
取前兩棵樹(shù)（權(quán)值最小）作為左右子樹(shù)，生成新二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值為原兩樹(shù)權(quán)值之和。
在集合中使用新的二叉樹(shù)替換原始的兩棵樹(shù)并重新排序。
重復(fù)步驟2和3，直到序列只剩下一棵樹(shù)為止，此樹(shù)即為霍夫曼樹(shù)。

示例：

結(jié)點(diǎn)	A	B	C	D	E
權(quán)值	5	15	40	30	10

樹(shù)--生成霍夫曼樹(shù).jpg

3.7.3 霍夫曼編碼

將霍夫曼樹(shù)中所有結(jié)點(diǎn)（包括合成結(jié)點(diǎn)）的權(quán)值改為0和1（左分支權(quán)值為0，右分支權(quán)值為1），這樣從根結(jié)點(diǎn)到指定葉子結(jié)點(diǎn)所生成的0和1序列即為霍夫曼編碼。

上面的霍夫曼樹(shù)轉(zhuǎn)換后的結(jié)果為：

樹(shù)--轉(zhuǎn)化后的霍夫曼樹(shù).jpg

因此，圖中每個(gè)字符所生成的霍夫曼編碼如下：

字符	A	B	C	D	E
霍夫曼編碼	1000	101	0	11	1001

霍夫曼編碼可以用來(lái)壓縮數(shù)據(jù)，進(jìn)而提高了傳輸效率。

假設(shè)傳輸”BADBEC“這個(gè)字符串，使用傳統(tǒng)的等長(zhǎng)編碼，可能會(huì)使用如下方式：

字符	A	B	C	D	E
等長(zhǎng)編碼	100	101	010	011	110

故在此方式下，編碼后的數(shù)據(jù)為”101100011101110010“，長(zhǎng)度為18位；而使用霍夫曼編碼，編碼后的數(shù)據(jù)為”1011000101101110“，長(zhǎng)度僅為16位，故數(shù)據(jù)得到了壓縮。且隨著編碼字符的增多，霍夫曼編碼的數(shù)據(jù)優(yōu)勢(shì)會(huì)越來(lái)越大。

像霍夫曼編碼這樣長(zhǎng)短不一的編碼方式，由于容易混淆，故必須設(shè)計(jì)成任一字符的編碼都不是其他字符編碼的前綴（否則解碼時(shí)無(wú)法區(qū)分），這種編碼方式叫做前綴編碼。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

《大話數(shù)據(jù)結(jié)構(gòu)》之樹(shù)

《大話數(shù)據(jù)結(jié)構(gòu)》之樹(shù)

1. 概念

1.1 樹(shù)的“度”

1.2 結(jié)點(diǎn)間的關(guān)系

1.3 樹(shù)的“深度”

1.4 其他概念

1.5 結(jié)構(gòu)對(duì)比

2. 存儲(chǔ)結(jié)構(gòu)

2.1 雙親表示法

2.2 孩子表示法

2.3 孩子兄弟表示法

3. 二叉樹(shù)

3.1 定義

3.2 存儲(chǔ)結(jié)構(gòu)

3.2.1 順序存儲(chǔ)結(jié)構(gòu)

3.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--二叉鏈表

3.3 二叉樹(shù)的遍歷

3.3.1 前序遍歷

3.3.2 中序遍歷

3.3.3 后續(xù)遍歷

3.4 二叉樹(shù)的創(chuàng)建

3.5 線索二叉樹(shù)

3.5.1 線索化過(guò)程

3.5.2 區(qū)分結(jié)點(diǎn)類型

3.6 樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)

3.6.1 樹(shù) => 二叉樹(shù)

3.6.2 森林 => 二叉樹(shù)

3.7 赫夫曼樹(shù)及霍夫曼編碼

3.7.1 概念介紹

3.7.2 生成方法

3.7.3 霍夫曼編碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

《大話數(shù)據(jù)結(jié)構(gòu)》之樹(shù)

1. 概念

1.1 樹(shù)的“度”

1.2 結(jié)點(diǎn)間的關(guān)系

1.3 樹(shù)的“深度”

1.4 其他概念

1.5 結(jié)構(gòu)對(duì)比

2. 存儲(chǔ)結(jié)構(gòu)

2.1 雙親表示法

2.2 孩子表示法

2.3 孩子兄弟表示法

3. 二叉樹(shù)

3.1 定義

3.2 存儲(chǔ)結(jié)構(gòu)

3.2.1 順序存儲(chǔ)結(jié)構(gòu)

3.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--二叉鏈表

3.3 二叉樹(shù)的遍歷

3.3.1 前序遍歷

3.3.2 中序遍歷

3.3.3 后續(xù)遍歷

3.4 二叉樹(shù)的創(chuàng)建

3.5 線索二叉樹(shù)

3.5.1 線索化過(guò)程

3.5.2 區(qū)分結(jié)點(diǎn)類型

3.6 樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)

3.6.1 樹(shù) => 二叉樹(shù)

3.6.2 森林 => 二叉樹(shù)

3.7 赫夫曼樹(shù)及霍夫曼編碼

3.7.1 概念介紹

3.7.2 生成方法

3.7.3 霍夫曼編碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av