數(shù)據(jù)結(jié)構(gòu)與算法 樹
2022-04-25 22:54:29

一、樹的定義

樹(Tree)是n(n>=0)個(gè)節(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)成為空樹，在任意一棵非空樹中：

• 有且僅有一個(gè)特定的稱為根(Root)的節(jié)點(diǎn)
• 當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1 T2 T3 … Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。

二、節(jié)點(diǎn)分類

節(jié)點(diǎn)擁有的子樹數(shù)稱為節(jié)點(diǎn)的度(Degree)，樹的度取樹內(nèi)各節(jié)點(diǎn)的度的最大值。

• 度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)或終端節(jié)點(diǎn)
• 度不為0的節(jié)點(diǎn)稱為分支節(jié)點(diǎn)或非終端節(jié)點(diǎn)，除根節(jié)點(diǎn)外，分支節(jié)點(diǎn)也稱為內(nèi)部節(jié)點(diǎn)。

節(jié)點(diǎn)之間的關(guān)系

節(jié)點(diǎn)的子樹的根稱為節(jié)點(diǎn)的孩子(Child)，相應(yīng)的，該節(jié)點(diǎn)稱為孩子的雙親(Parent)，同一雙親的孩子之間互稱為兄弟(Sibling)。

節(jié)點(diǎn)的祖先是從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。

節(jié)點(diǎn)的層次

節(jié)點(diǎn)的層次(level)從根開始起，根為第一層，根的孩子為第二層。

其雙親在同一層的節(jié)點(diǎn)互為堂兄弟。

樹中節(jié)點(diǎn)的最大層次稱為樹的深度(depth)或高度。

其他概念

如果將樹中節(jié)點(diǎn)的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。

三、樹的存儲(chǔ)結(jié)構(gòu)

說到存儲(chǔ)結(jié)構(gòu)，就會(huì)想到我們前面章節(jié)講過的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種基本結(jié)構(gòu)。

對(duì)于線性表來說，很直觀就可以理解，但對(duì)于樹這種一對(duì)多的結(jié)構(gòu)，我們應(yīng)該怎么辦呢？

要存儲(chǔ)樹，簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是不能的。不過如果充分利用他們各自的特點(diǎn)，完全可以間接地來實(shí)現(xiàn)。

這里要介紹三種不同的表示法：雙親表示法、孩子表示法、孩子兄弟表示法。

雙親表示法

雙親表示法，言外之意就是以雙親作為索引的關(guān)鍵詞的一種存儲(chǔ)方式。

我們假設(shè)以一組連續(xù)空間存儲(chǔ)樹的節(jié)點(diǎn)，同時(shí)在每個(gè)節(jié)點(diǎn)中，附設(shè)一個(gè)指示其雙親節(jié)點(diǎn)在數(shù)組中位置的元素。

也就是說，每個(gè)節(jié)點(diǎn)除了知道自己是誰之外，還知道他的雙親在哪。

//樹的雙親表示節(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

這樣的存儲(chǔ)結(jié)構(gòu)，我們可以根據(jù)某節(jié)點(diǎn)的parent指針找到他的雙親節(jié)點(diǎn)，所用的時(shí)間復(fù)雜度是O(1)，索引到parent的值為-1時(shí)，表示找到了樹節(jié)點(diǎn)的根。

可是，如果我們要知道某個(gè)節(jié)點(diǎn)的孩子是什么？那么需要遍歷整個(gè)樹結(jié)構(gòu)。

這真的麻煩，能不能改進(jìn)以下呢？我們只需稍微改變以下結(jié)構(gòu)即可：

那現(xiàn)在我們又比較關(guān)心他們兄弟之間的關(guān)系呢？

孩子表示法

我們這次換個(gè)角度來考慮，由于樹中每個(gè)節(jié)點(diǎn)可能有多棵子樹，可以考慮用多重鏈表來實(shí)現(xiàn)。

雙親孩子表示法

那只找好孩子找不到雙親貌似還不夠完善，那么我們合并上一講的雙親孩子表示法：

parent_child.c

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

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

//樹結(jié)構(gòu)
typedef struct{
    CTBox node[MAX_TREE_SIZE];//節(jié)點(diǎn)數(shù)組
    int r,n;
};

四、二叉樹

因?yàn)槎鏄涫褂梅秶顝V，最具有代表意義，因此我們重點(diǎn)討論二叉樹。

二叉樹(Binery Tree)是n（n>=0）個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹），或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

二叉樹的特點(diǎn)

每個(gè)節(jié)點(diǎn)最多有兩棵子樹，所以二叉樹中不存在度大于2的節(jié)點(diǎn)。（注意：不是都需要兩棵子樹，而是最多可以是兩棵，沒有子樹或者有一棵子樹也都是可以的。）

左子樹和右子樹是由順序的，次序不能顛倒。

即使樹中某節(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹，下面是完全不同的二叉樹：

二叉樹的五種基本形態(tài)

• 空二叉樹
• 只有一個(gè)根節(jié)點(diǎn)
• 根節(jié)點(diǎn)只有左子樹
• 根節(jié)點(diǎn)只有右子樹
• 根節(jié)點(diǎn)既有左子樹又有右子樹

特殊二叉樹

• 斜樹 要么往左斜，要么往右斜
• 滿二叉樹 在一棵二叉樹中，如果所有分支節(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層，這樣的二叉樹稱為滿二叉樹。
• 完全二叉樹 對(duì)一棵具有n個(gè)節(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i(1<=i<=n)的節(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的節(jié)點(diǎn)位置完全相同，則這棵二叉樹稱為完全二叉樹。

二叉樹的性質(zhì)

在二叉樹的第i層上至多有2^(i-1)個(gè)節(jié)點(diǎn)(i>=1)

深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)

對(duì)任何一棵二叉樹T，如果其終端節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2則n0 = n2+1

具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[log2 n]+1

如果對(duì)一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹（其深度為[log2 n] +1）的節(jié)點(diǎn)按層序編號(hào)，對(duì)任一節(jié)點(diǎn)i(1<=i<=n)有以下性質(zhì)：

二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹是一種特殊的樹，由于他的特殊性，使得用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能簡(jiǎn)單實(shí)現(xiàn)。

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的各個(gè)節(jié)點(diǎn)，并且節(jié)點(diǎn)的存儲(chǔ)位置能體現(xiàn)節(jié)點(diǎn)之間的邏輯關(guān)系。

這下看出完全二叉樹的優(yōu)越性了吧，由于他的嚴(yán)格定義，在數(shù)組直接能表現(xiàn)出邏輯。

當(dāng)然對(duì)于一般的二叉樹，盡管層序編號(hào)不能反映邏輯關(guān)系，但是也可以按照完全二叉樹編號(hào)方式修改一下，把不存在的節(jié)點(diǎn)用^代替即可。

但是考慮到一種極端的情況，回顧一下斜樹，如果是一個(gè)右斜樹，那么會(huì)變成這樣

既然順序存儲(chǔ)方式的適用性不強(qiáng)，那么我們就要考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)了。二叉樹的存儲(chǔ)按照國(guó)際慣例來說一般也是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的。

二叉樹的每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTTree;

五、二叉樹的遍歷

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

二叉樹的遍歷次序不同于線性結(jié)構(gòu)，線性結(jié)構(gòu)最多也就是分為順序、循環(huán)、雙向等簡(jiǎn)單的遍歷方式。

樹的節(jié)點(diǎn)之間不存在唯一的前驅(qū)和后繼這樣的關(guān)系，在訪問一個(gè)節(jié)點(diǎn)后，下一個(gè)被訪問的節(jié)點(diǎn)面臨著不同的選擇。

二叉樹的遍歷方式可以很多，如果我們限制了從左到右的習(xí)慣方式，那么主要就分為以下四種：

• 第一種：前序遍歷
  若二叉樹為空，則空操作返回，否則先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。

• 第二種：中序遍歷
  若樹為空，則空操作返回，否則從根節(jié)點(diǎn)開始（注意并不是先訪問根節(jié)點(diǎn)），中序遍歷根節(jié)點(diǎn)的左子樹，然后是訪問根節(jié)點(diǎn)，最后中序遍歷右子樹。

• 第三種：后序遍歷
  若樹為空，則空操作返回，否則從左到右先葉子后節(jié)點(diǎn)的方式遍歷訪問左右子樹，最后訪問根節(jié)點(diǎn)。

• 第四種：層序遍歷 若樹為空，則空操作返回，否則從樹的第一層，也就是根節(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪問。

六、二叉樹的建立和遍歷算法

題目要求：建立二叉樹并輸出每個(gè)字符所在的層數(shù)。如圖：

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

typedef char ElemType;

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


//創(chuàng)建一棵二叉樹,約定用戶遵照前序遍歷的方式輸入數(shù)據(jù)
void createBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    
    if(' ' == c){//說明此子樹不存在
        *T = NULL;
    }else{
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        createBiTree(&(*T)->lchild);//左子樹
        createBiTree(&(*T)->rchild);//右子樹
    }
}

//訪問二叉樹節(jié)點(diǎn)的具體操作
void visit(ElemType c,int level){
    printf("%c位于第%d層
",c,level);
}
//遍歷二叉樹
void PreOrderTraverse(BiTree T,int level){
    if(T){
        visit(T->data,level);
        PreOrderTraverse(T->lchild,level+1);
        PreOrderTraverse(T->rchild,level+1);
    }
}

int main(){
    int level = 1;
    BiTree T = NULL;
    
    createBiTree(&T);
    
    PreOrderTraverse(T,level);
    return 0;
}

七、線索二叉樹

為什么需要線索二叉樹呢？

我想正如程序員發(fā)覺單鏈表并不總能滿足他們?cè)O(shè)計(jì)的程序某些要求的時(shí)候，發(fā)明了雙向鏈表來彌補(bǔ)一樣，線索二叉樹也是在需求中被創(chuàng)造的！

那普通二叉樹到底有什么缺陷讓我們發(fā)指呢？

主要是浪費(fèi)時(shí)間和空間

八、樹、森林及二叉樹的相互轉(zhuǎn)換

從一棵普通的樹開始介紹，在滿足樹的條件下可以是任意狀態(tài)，一個(gè)節(jié)點(diǎn)可以有任意多個(gè)孩子，這樣對(duì)樹處理顯得要復(fù)雜很多。

所以我們研究除了一些條條框框的限定，如：二叉樹，完全二叉樹，滿二叉樹等。

那么這時(shí)候你就會(huì)想，如果所有的樹都像二叉樹一樣方便處理就好了。

普通樹轉(zhuǎn)換為二叉樹

步驟如下：

1. 在樹中所有的兄弟節(jié)點(diǎn)之間加一連線
2. 對(duì)每個(gè)節(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該節(jié)點(diǎn)與其他孩子的連線

森林到二叉樹的轉(zhuǎn)換

1. 先將森林中的每一棵樹變?yōu)槎鏄洌ǚ椒ㄍ希?/li>
2. 再將各二叉樹的根節(jié)點(diǎn)視為兄弟從左至右連在一起。

二叉樹到樹、森林的轉(zhuǎn)換

• 若節(jié)點(diǎn)x是其雙親的左孩子，則把x的的右孩子，右孩子的右孩子,…，都與y用線連起來。
• 去掉所有雙親到右孩子之間的連線

樹與森林的遍歷

樹的遍歷分為兩種方式：一種是先根遍歷，另一種是后根遍歷。

先根遍歷：先訪問樹的根節(jié)點(diǎn)，然后再依次先根遍歷根的每一棵子樹。

后根遍歷：先依次遍歷每棵子樹，然后再訪問根節(jié)點(diǎn)。

森林的遍歷也分為前序遍歷和后序遍歷，其實(shí)就是按照樹的先根遍歷和后根遍歷依次訪問森林的每一個(gè)樹。

我們驚人的發(fā)現(xiàn)：樹、森林的前根（序）遍歷和二叉樹的前序遍歷結(jié)果相同，樹、森林的后根（序）遍歷和二叉樹的終須遍歷結(jié)果相同

????