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

一、樹的定義

樹(Tree)是n(n>=0)個節(jié)點的有限集。當n=0時成為空樹，在任意一棵非空樹中：

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

二、節(jié)點分類

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

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

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

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

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

節(jié)點的層次

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

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

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

其他概念

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

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

說到存儲結(jié)構(gòu)，就會想到我們前面章節(jié)講過的順序存儲和鏈式存儲兩種基本結(jié)構(gòu)。

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

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

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

雙親表示法

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

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

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

//樹的雙親表示節(jié)點結(jié)構(gòu)定義

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode{
    ElemType data;//節(jié)點數(shù)據(jù)
    int parent;//雙親位置
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r;//根的位置
    int n;//節(jié)點數(shù)目·
}PTree

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

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

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

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

孩子表示法

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

雙親孩子表示法

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

parent_child.c

#define MAX_TREE_SIZE = 100
typedef char ElemType;
//孩子節(jié)點
typedef struct CTNode{
    int child;/孩子節(jié)點的下標
    struct CTNode *next;//指向下一個孩子節(jié)點的指針
} *ChildPtr;

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

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

四、二叉樹

因為二叉樹使用范圍最廣，最具有代表意義，因此我們重點討論二叉樹。

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

二叉樹的特點

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

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

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

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

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

特殊二叉樹

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

二叉樹的性質(zhì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、二叉樹的遍歷

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

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

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

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

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

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

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

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

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

題目要求：建立二叉樹并輸出每個字符所在的層數(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é)點的具體操作
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ā)覺單鏈表并不總能滿足他們設(shè)計的程序某些要求的時候，發(fā)明了雙向鏈表來彌補一樣，線索二叉樹也是在需求中被創(chuàng)造的！

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

主要是浪費時間和空間

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

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

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

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

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

步驟如下：

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

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

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

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

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

樹與森林的遍歷

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

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

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

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

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

????