樹(shù)(tree)

首先可以想象秋柄，現(xiàn)實(shí)中的樹(shù)是由樹(shù)根缀旁、莖干、樹(shù)枝、樹(shù)葉組成的粗俱，樹(shù)的營(yíng)養(yǎng)是由樹(shù)根出發(fā)收班、通過(guò)莖干與樹(shù)枝不斷傳遞涮帘，最終到達(dá)樹(shù)葉的帝簇。
在數(shù)據(jù)結(jié)構(gòu)中，樹(shù)則是用來(lái)概括這種傳遞關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)来庭。

定義

結(jié)點(diǎn)(node)：樹(shù)枝分叉處妒蔚、樹(shù)葉、樹(shù)根的抽象
根節(jié)點(diǎn)(root)：樹(shù)根的抽象月弛，對(duì)一棵樹(shù)來(lái)說(shuō)最多存在一個(gè)根節(jié)點(diǎn)
葉子結(jié)點(diǎn)(leaf)：樹(shù)葉的抽象肴盏，且葉子結(jié)點(diǎn)不再延申出新的結(jié)點(diǎn)
邊(edge)：把莖干和樹(shù)枝的統(tǒng)一抽象，且一條只用來(lái)鏈接兩個(gè)結(jié)點(diǎn)（一個(gè)端點(diǎn)一個(gè)）（特指二叉樹(shù)）
樹(shù)中的結(jié)點(diǎn)不能被邊連接成環(huán)帽衙。
在數(shù)據(jù)結(jié)構(gòu)中菜皂，一般把根結(jié)點(diǎn)置于最上方，然后向下延伸出若干條邊到達(dá)子結(jié)點(diǎn)(child)（從而向下形成子樹(shù)(subtree)）厉萝，而子結(jié)點(diǎn)又向下延伸出邊并連接一些結(jié)點(diǎn)......直至到達(dá)葉子結(jié)點(diǎn)恍飘，看起來(lái)就像是把現(xiàn)實(shí)中的樹(shù)顛倒過(guò)來(lái)的樣子。

常用性質(zhì)

1. 樹(shù)可以沒(méi)有結(jié)點(diǎn)谴垫，這種情況下把樹(shù)稱(chēng)為空樹(shù)(empty tree)章母。
2. 樹(shù)的層次(layer)從根結(jié)點(diǎn)開(kāi)始算起，即根結(jié)點(diǎn)為第一層翩剪，根結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)為第二層乳怎，依次類(lèi)推
3. 把結(jié)點(diǎn)的子樹(shù)棵樹(shù)稱(chēng)為結(jié)點(diǎn)的度(degree)，而樹(shù)中結(jié)點(diǎn)的最大的度稱(chēng)為樹(shù)的度（也成為樹(shù)的寬度）
4. 由于一條邊連接兩個(gè)結(jié)點(diǎn)前弯，且樹(shù)中不存在環(huán)蚪缀，因此對(duì)有n個(gè)結(jié)點(diǎn)的樹(shù)，邊數(shù)一定是n-1恕出。且滿(mǎn)足連通询枚、邊數(shù)等于頂點(diǎn)數(shù)減1的結(jié)構(gòu)一定是一棵樹(shù)。
5. 葉子結(jié)點(diǎn)被定義為度為0的結(jié)點(diǎn)剃根，因此當(dāng)樹(shù)中只有一個(gè)結(jié)點(diǎn)（即只有根結(jié)點(diǎn)）時(shí)哩盲，根結(jié)點(diǎn)也算作葉子結(jié)點(diǎn)。
6. 結(jié)點(diǎn)的深度(depth)是指從根結(jié)點(diǎn)(深度為1）開(kāi)始自頂向下逐層累加至該結(jié)點(diǎn)時(shí)的深度值狈醉；結(jié)點(diǎn)的高度(height)是指從最底層葉子結(jié)點(diǎn)（高度為1）開(kāi)始自頂向上逐層累加至該結(jié)點(diǎn)時(shí)的高度值廉油。樹(shù)的深度是指樹(shù)中結(jié)點(diǎn)的最大深度，樹(shù)的高度是指樹(shù)中結(jié)點(diǎn)的最大高度苗傅。對(duì)樹(shù)而言抒线，深度和高度是相等的，但是具體到某個(gè)結(jié)點(diǎn)來(lái)說(shuō)深度和高度就不一定相等了渣慕。
7. 多棵樹(shù)組合在一起稱(chēng)為森林（forest）嘶炭，即森林是若干棵樹(shù)的集合

二叉樹(shù)

二叉樹(shù)的遞歸定義：

1. 要么二叉樹(shù)沒(méi)有根結(jié)點(diǎn)，是一棵空樹(shù)逊桦。
2. 要么二叉樹(shù)由根結(jié)點(diǎn)眨猎、左子樹(shù)、右子樹(shù)組成强经，且左子樹(shù)和右子樹(shù)都是二叉樹(shù)睡陪。

一是遞歸邊界，二是遞歸式匿情。
二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的左子樹(shù)既可以是一棵空樹(shù)兰迫，也可以是一棵有左子樹(shù)和右子樹(shù)的二叉樹(shù)；結(jié)點(diǎn)的右子樹(shù)也既可以是一棵空樹(shù)炬称，又可以是一棵有左子樹(shù)和右子樹(shù)的二叉樹(shù)汁果，這樣直到遞歸邊界，遞歸定義結(jié)束玲躯。
注意：二叉樹(shù)與度為2的樹(shù)的區(qū)別据德。對(duì)樹(shù)來(lái)說(shuō)不區(qū)分左右順序的，因此度為2的樹(shù)只能說(shuō)明樹(shù)中每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)不超過(guò)2跷车。而二叉樹(shù)雖然也滿(mǎn)足每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)不超過(guò)2晋控，但它的左右子樹(shù)是嚴(yán)格區(qū)分的，不能隨意交換左子樹(shù)和右子樹(shù)的位置姓赤，是最主要的區(qū)別赡译。

特殊的二叉樹(shù)

1. 滿(mǎn)二叉樹(shù)：每一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了當(dāng)層能達(dá)到的最大結(jié)點(diǎn)樹(shù)。
2. 完全二叉樹(shù)：除了最下面一層之外不铆，其余層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了當(dāng)層能達(dá)到的最大結(jié)點(diǎn)樹(shù)蝌焚，且最下面一層只從左至右連續(xù)存在若干節(jié)點(diǎn)，而這些連續(xù)結(jié)點(diǎn)右邊的結(jié)點(diǎn)全部不存在誓斥。

幾個(gè)概念：層次只洒、孩子結(jié)點(diǎn)、父親結(jié)點(diǎn)劳坑、兄弟結(jié)點(diǎn)毕谴、祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與基本操作

1. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
   一般來(lái)說(shuō)，二叉樹(shù)使用鏈表來(lái)定義涝开。如果某個(gè)子樹(shù)不存在循帐，則指向NULL。又把這種鏈表叫做二叉鏈表舀武。

struct node {
    typename data;  //數(shù)據(jù)域
    node* lchild;   //指向左子樹(shù)根結(jié)點(diǎn)的指針
    node* rchild;   //指向右子樹(shù)根結(jié)點(diǎn)的指針 
}; 

由于二叉樹(shù)建樹(shù)前根節(jié)點(diǎn)不存在拄养，因此其地址一般設(shè)為NULL：

node* root = NULL;

如果需要新建結(jié)點(diǎn)（例如往二叉樹(shù)中插入結(jié)點(diǎn)的時(shí)候），就可以使用下面的函數(shù)：

node* newNode(int v) {
    node* Node = new node;  //申請(qǐng)一個(gè)node型變量的地址空間
    Node->data = v;     //結(jié)點(diǎn)權(quán)值為v
    Node->lchild = Node->rchild = NULL; //初始狀態(tài)下沒(méi)有左右孩子
    return Node;    //返回新建結(jié)點(diǎn)的地址 
} 

二叉樹(shù)常用操作

二叉樹(shù)結(jié)點(diǎn)的查找银舱、修改
查找操作是指在給定數(shù)據(jù)域的條件下瘪匿，在二叉樹(shù)中找到所有數(shù)據(jù)域?yàn)榻o定數(shù)據(jù)域的結(jié)點(diǎn)，并將它們的數(shù)據(jù)域修改為給定的數(shù)據(jù)域寻馏。
遞歸式：指對(duì)當(dāng)前結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)分別遞歸
遞歸邊界：當(dāng)前結(jié)點(diǎn)為空時(shí)到達(dá)死胡同

void search(node* root, int x, int newdata) {
    if(root == NULL) {
        return;         //空樹(shù)棋弥，死胡同（遞歸邊界） 
    }
    if(root->data == x) {   //找到數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，把它修改成newdata 
        root->data = newdata;
    } 
    search(root->lchild, x, newdata);       //往左子樹(shù)搜索x（遞歸式）
    search(root->rchild, x, newdata);       //往右子樹(shù)搜索x（遞歸式） 
} 

二叉樹(shù)結(jié)點(diǎn)的插入
二叉樹(shù)結(jié)點(diǎn)的插入位置就是數(shù)據(jù)域在二叉樹(shù)中查找失敗的位置诚欠。由于這個(gè)位置是確定的顽染，因此在遞歸查找的過(guò)程中一定是只根據(jù)二叉樹(shù)的性質(zhì)來(lái)選擇左子樹(shù)或右子樹(shù)中的一棵子樹(shù)進(jìn)行遞歸，且最后到達(dá)空樹(shù)(死胡同）的地方就是查找失敗的地方聂薪，也就是結(jié)點(diǎn)需要插入的地方家乘。

//insert函數(shù)將在二叉樹(shù)中插入一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)
//注意根結(jié)點(diǎn)指針root要使用引用，否則插入不會(huì)成功
void insert(node* &root, int x) {
    if(root == NULL) {      //空樹(shù)藏澳，說(shuō)明查找失敗仁锯，也即插入位置（遞歸邊界） 
        root = newNode(x);
        return;
    }
    if(由二叉樹(shù)的性質(zhì)，x應(yīng)該插在左子樹(shù)) {
        insert(root->lchild, x);    //往左子樹(shù)搜索(遞歸式)        
    } else {
        insert(root->rchild, y);    //往右子樹(shù)搜索(遞歸式)
    }
} 

根結(jié)點(diǎn)指針root使用了引用&翔悠，這么做是业崖，在insert函數(shù)中新建了結(jié)點(diǎn)，并把新結(jié)點(diǎn)的地址賦給了當(dāng)層的root蓄愁。不使用引用就不能把新結(jié)點(diǎn)接導(dǎo)二叉樹(shù)上面双炕。（改變r(jià)oot本身，前面search函數(shù)知識(shí)修改指針root指向的內(nèi)容）
判斷是否加引用：如果函數(shù)中需要新建結(jié)點(diǎn)撮抓，即對(duì)二叉樹(shù)的結(jié)構(gòu)做出修改妇斤，就需要加引用；如果知識(shí)修改當(dāng)前已有結(jié)點(diǎn)的內(nèi)容丹拯，或僅僅是遍歷樹(shù)站超，就不用加引用。
注意：在新建結(jié)點(diǎn)之后乖酬，務(wù)必令新結(jié)點(diǎn)的左右指針域?yàn)镹ULL死相，表示這個(gè)新結(jié)點(diǎn)暫時(shí)沒(méi)有左右子樹(shù)。

二叉樹(shù)的創(chuàng)建
二叉樹(shù)的創(chuàng)建其實(shí)就是二叉樹(shù)結(jié)點(diǎn)的插入過(guò)程咬像。
把需要插入的數(shù)據(jù)存儲(chǔ)在數(shù)組中算撮，然后再將它們使用insert函數(shù)一個(gè)個(gè)插入二叉樹(shù)中生宛，并最終返回根結(jié)點(diǎn)的指針root。熟悉后可以直接在建立二叉樹(shù)的過(guò)程中邊輸入數(shù)據(jù)邊插入肮柜。

node* Create(int data[], int n) {
    node* root = NULL;  //新建空根結(jié)點(diǎn)root
    for(int i = 0; i < n; i++) {
        insert(root, data[i]);  //將data[0]~data[n-1]插入二叉樹(shù)中 
    } 
    return root;        //返回根結(jié)點(diǎn) 
}

二叉樹(shù)存儲(chǔ)結(jié)構(gòu)
注意：遞歸邊界為root == NULL而不是 * root == NULL
原因是如果子樹(shù)是空樹(shù)陷舅，那么root一定是NULL，表示這個(gè)結(jié)點(diǎn)不存在素挽。而*root的含義是獲取地址root指向的空間的內(nèi)容蔑赘，但這無(wú)法說(shuō)明地址root是否為空狸驳，也即無(wú)法確定是否存在這個(gè)結(jié)點(diǎn)预明，因此 * root == NULL的寫(xiě)法是錯(cuò)誤的。這個(gè)區(qū)別也是結(jié)點(diǎn)地址為NULL和結(jié)點(diǎn)內(nèi)容為NULL的區(qū)別（也相當(dāng)于結(jié)點(diǎn)不存在與結(jié)點(diǎn)存在但是沒(méi)有內(nèi)容的區(qū)別）

完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
對(duì)完全二叉樹(shù)當(dāng)中的任何一個(gè)結(jié)點(diǎn)（設(shè)編號(hào)為x）耙箍，其左孩子的編號(hào)一定是2x撰糠，而右孩子的編號(hào)一定是2x+1。
完全二叉樹(shù)可以通過(guò)建立一個(gè)大小為2的k次方的數(shù)組來(lái)存放所有結(jié)點(diǎn)的信息辩昆，其中k為完全二叉樹(shù)的最大高度阅酪，且1號(hào)位存放的必須是根結(jié)點(diǎn)。
數(shù)組中元素存放的順序恰好位該完全二叉樹(shù)的層序遍歷序列汁针，而判斷某個(gè)結(jié)點(diǎn)是否為葉結(jié)點(diǎn)的標(biāo)志為：該結(jié)點(diǎn)（記下標(biāo)為root）的左子結(jié)點(diǎn)的編號(hào)root * 2大于結(jié)點(diǎn)總個(gè)數(shù)n术辐；判斷某個(gè)結(jié)點(diǎn)是否為空結(jié)點(diǎn)的標(biāo)志：該結(jié)點(diǎn)下標(biāo)root大于結(jié)點(diǎn)總個(gè)數(shù)n。