1、樹

伊通網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),伊通網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為伊通1000+提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的伊通做網(wǎng)站的公司定做！

 (1)、樹形結(jié)構(gòu)本身具有遞歸的性質(zhì)(在其后的編程中體現(xiàn)的淋漓盡致)!

 樹是一種非常重要的非線性結(jié)構(gòu)。

 (2)、幾個(gè)概念：結(jié)點(diǎn)的度，就是分支個(gè)數(shù)(孩子個(gè)數(shù))；

 樹的度，結(jié)點(diǎn)度中大的(孩子最多的)；

 非葉子結(jié)點(diǎn)，度 > 0 (有孩子結(jié)點(diǎn))；

 葉子結(jié)點(diǎn)，度為0的 (沒有孩子結(jié)點(diǎn))；

 樹的高度，從1開始算；

(3)、為什么要學(xué)習(xí)二叉樹？

 原因：所有的樹形結(jié)構(gòu)(包括森林)都可以轉(zhuǎn)化為二叉樹。二叉樹是樹形結(jié)構(gòu)的基礎(chǔ)，

 只有學(xué)好了二叉樹才能學(xué)好其它的。

2、二叉樹

 (1)、二叉樹分左右，所以又叫做有序樹。

 (2)、二叉樹中的度 <= 2，度都為1時(shí)，就退化為鏈表了，

 (3)、每一層最多結(jié)點(diǎn)個(gè)數(shù)：2^(i-1)；是偶數(shù)個(gè)，i代表層數(shù)(從1開始)；

 整棵樹的最多結(jié)點(diǎn)個(gè)數(shù)：2^k - 1; 是奇數(shù)個(gè)(因?yàn)槌烁?jié)點(diǎn)只有一個(gè)，其它每層都是偶數(shù)個(gè))，k代表層數(shù)(從1開始)；

 (4)、n(0) = n(2) + 1;度為0的葉子結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)加1；

 (5)、滿二叉樹和完全二叉樹：

 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹；

 完全二叉樹有N個(gè)結(jié)點(diǎn)的高度：[log2^N](向下取整) + 1；

3、二叉樹的存儲(chǔ)形式：

 (1)、線性存儲(chǔ)，數(shù)組存儲(chǔ)，------->針對(duì)完全二叉樹好，

 (2)、鏈?zhǔn)酱鎯?chǔ)-------------->針對(duì)普通二叉樹；

4、二叉樹的創(chuàng)建：

 我認(rèn)為有9種創(chuàng)建方式：寫出先序序列，

 從鍵盤輸入的建立方案：參數(shù)和返回值創(chuàng)建  2

 根據(jù)(文件)字符串的傳入：參數(shù)和返回值創(chuàng)建  2

 由先序和中序創(chuàng)建  2

 由中序和后序創(chuàng)建  2

 以上的都是通過遞歸創(chuàng)建二叉樹，形式方法，大同小異！

 以后我還會(huì)寫上非遞歸創(chuàng)建二叉樹，不在浪費(fèi)多余以#代替的空間 1

5、創(chuàng)建二叉樹：

 均由C++實(shí)現(xiàn)，寫出先序序列，在進(jìn)行創(chuàng)建

 (1)、因?yàn)闃湫谓Y(jié)構(gòu)本身具有遞歸性質(zhì)，所以以下均是遞歸創(chuàng)建，以后我會(huì)寫非遞歸創(chuàng)建的。

 (2)、遞歸創(chuàng)建符合數(shù)學(xué)思維和邏輯，但是容易造成棧溢出，并且遞歸占用系統(tǒng)資源，好寫但不明智的做法，我認(rèn)為寫程序應(yīng)該盡量避免遞歸的做法??！

 (3)、這里寫出先序創(chuàng)建，例如："ABC##DE##F##G#H##"字符串創(chuàng)建，根據(jù)#判斷是否開辟空間！

 (4)、先序和后序一般不用于創(chuàng)建二叉樹，因?yàn)榇嬖谄缌x：

由先序和中序，中序和后序創(chuàng)建二叉樹是重點(diǎn)：

template  //中序和后序創(chuàng)建
void BinTree::createBinTree_1(BinTreeNode *&t, const char *LVR, const char *LRV, int n){
    if(n == 0){   //字符串長(zhǎng)度為0，建立空樹
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != LRV[n-1]){  //找出根結(jié)點(diǎn)的下標(biāo)
        k++;
    }
    t = new BinTreeNode(LVR[k]);  //建立根結(jié)點(diǎn)
    
    
    createBinTree_1(t->rightChild, LVR+k+1, LRV+k, n-k-1); //先創(chuàng)建右子樹，中跨k+1個(gè)，后跨k個(gè)，到底右邊，右邊一共n-k-1個(gè)節(jié)點(diǎn)；
    createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共k個(gè)；
}
template  //先序和中序創(chuàng)建
void BinTree::createBinTree(BinTreeNode *&t, const char *VLR, const char *LVR, int n){
    if(n == 0){   //要是長(zhǎng)度為0，則創(chuàng)建空樹
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != VLR[0]){  //由先序找到在中序中的位置k;
        k++;
    }
    t = new BinTreeNode(LVR[k]);  //首先創(chuàng)建根
    createBinTree(t->leftChild, VLR+1, LVR, k);  //創(chuàng)建左邊，跨過根， 中序， 根左邊k個(gè)節(jié)點(diǎn)；
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);//創(chuàng)建右邊，肯定都得+K+1,根右邊n-k-1個(gè)結(jié)點(diǎn)；
}

都是遞歸創(chuàng)建的，好想，畫畫圖就理解了，代碼如下：

#ifndef _BIN_TREE_H_   //預(yù)編譯條件宏
#define _BIN_TREE_H_

#include    //引入頭文件
using namespace std;

template  //聲明友元類
class BinTree;

template
class BinTreeNode{      //二叉樹結(jié)點(diǎn)的模板類
    friend class BinTree;  //可以調(diào)用其私有數(shù)據(jù)成員
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}  //默認(rèn)的構(gòu)造函數(shù)
    BinTreeNode(Type value, BinTreeNode *left = NULL, BinTreeNode *right = NULL) :
    data(value), leftChild(left), rightChild(right){}  //帶參數(shù)的構(gòu)造函數(shù)
    ~BinTreeNode(){}  //析構(gòu)函數(shù)暫時(shí)什么都不做
private:
    Type data;   //數(shù)據(jù)
    BinTreeNode *leftChild; //左孩子指針
    BinTreeNode *rightChild;  //右孩子指針
};
////////////////////////////////////////////////////以上是結(jié)點(diǎn)類型
template
class BinTree{       //二叉樹的模板類
public:
    BinTree() : root(NULL){}  ////默認(rèn)的構(gòu)造函數(shù)
    BinTree(Type ref) : root(NULL), refval(ref){} //帶參數(shù)的構(gòu)造函數(shù)
    ~BinTree(){}
public:   //以下四個(gè)是供外部調(diào)用的接口   函數(shù)聲明，類外定義
    void createBinTree();  //鍵盤輸入創(chuàng)建
    void createBinTree(const char *str);  //主函數(shù)傳字符串創(chuàng)建
    void createBinTree(const char *VLR, const char *LVR, int n); //先序和中序創(chuàng)建
    void createBinTree_1(const char *LVR, const char *LRV, int n);  //中序和后序創(chuàng)建
protected :  //以下6個(gè)是保護(hù)方法，外部不能直接訪問，供內(nèi)部函數(shù)的調(diào)用  函數(shù)聲明，類外定義
    void createBinTree(BinTreeNode *&t);  
    BinTreeNode* createBinTree_1();
    void createBinTree(const char *&str, BinTreeNode *&t);
    BinTreeNode* createBinTree_1(const char *&str);
    void createBinTree(BinTreeNode *&t, const char *VLR, const char *LVR, int n);
    void createBinTree_1(BinTreeNode *&t, const char *LVR, const char *LRV, int n);
private:
    BinTreeNode *root;    //根節(jié)點(diǎn)(要是C語言的話，的弄一個(gè)指向根節(jié)點(diǎn)的指針)；
    Type               refval;  //'#'標(biāo)志，創(chuàng)建多余空間，利用率比較低。
};
////////////////////////////////////////////////////////////以上是二叉樹的類型    
template   //類外函數(shù)的定義
void BinTree::createBinTree(){
    //createBinTree(root); 
    root = createBinTree_1();  //調(diào)用內(nèi)部寫保護(hù)的方法實(shí)現(xiàn)
}

template
void BinTree::createBinTree(const char *str){
//    createBinTree(str, root);
    root = createBinTree_1(str);
}
template
void BinTree::createBinTree(const char *VLR, const char *LVR, int n){
    createBinTree(root, VLR, LVR, n);
}
template
void BinTree::createBinTree_1(const char *LVR, const char *LRV, int n){
    createBinTree_1(root, LVR, LRV, n);
}
////////////////////////////////////////////////////////////以上是類外調(diào)用保護(hù)方法
//其下就是具體的創(chuàng)建過程
template  //中序和后序創(chuàng)建
void BinTree::createBinTree_1(BinTreeNode *&t, const char *LVR, const char *LRV, int n){
    if(n == 0){   //字符串長(zhǎng)度為0，建立空樹
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != LRV[n-1]){  //找出根結(jié)點(diǎn)的下標(biāo)
        k++;
    }
    t = new BinTreeNode(LVR[k]);  //建立根結(jié)點(diǎn)
    
    
    createBinTree_1(t->rightChild, LVR+k+1, LRV+k, n-k-1); //先創(chuàng)建右子樹，中跨k+1個(gè)，后跨k個(gè)，到底右邊，右邊一共n-k-1個(gè)節(jié)點(diǎn)；
    createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共k個(gè)；
}
template  //先序和中序創(chuàng)建
void BinTree::createBinTree(BinTreeNode *&t, const char *VLR, const char *LVR, int n){
    if(n == 0){   //要是長(zhǎng)度為0，則創(chuàng)建空樹
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != VLR[0]){  //由先序找到在中序中的位置k;
        k++;
    }
    t = new BinTreeNode(LVR[k]);  //首先創(chuàng)建根
    createBinTree(t->leftChild, VLR+1, LVR, k);  //創(chuàng)建左邊，跨過根， 中序， 根左邊k個(gè)節(jié)點(diǎn)；
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);//創(chuàng)建右邊，肯定都得+K+1,根右邊n-k-1個(gè)結(jié)點(diǎn)；
}

template  //返回指針root接受，字符串創(chuàng)建
BinTreeNode* BinTree::createBinTree_1(const char *&str){
    BinTreeNode *t;

    if(refval == *str){
        t = NULL;
    }else{
        t = new BinTreeNode(*str);
        t->leftChild = createBinTree_1(++str);
        t->rightChild = createBinTree_1(++str);
    }
    return t;
}

template  //引用直接更改root，字符串創(chuàng)建
void BinTree::createBinTree(const char *&str, BinTreeNode *&t){
    if(*str == refval){    
        t = NULL; 
    }else{
        t = new BinTreeNode(*str);
        createBinTree(++str, t->leftChild);  //前加，后加不一樣?。?！在這里，就是傳引用，保證每次字符串都是往后走的
        createBinTree(++str, t->rightChild);
    }
}
template  //返回指針root接受, 鍵盤輸入先序創(chuàng)建
BinTreeNode* BinTree::createBinTree_1(){
    Type createData;
    cin>>createData;
    BinTreeNode *t;

    if(refval == createData){
        t = NULL;
    }else{
        t = new BinTreeNode(createData);
        t->leftChild = createBinTree_1();
        t->rightChild = createBinTree_1();
    }

    return t;
}

template  //引用直接更改root,根據(jù)先根序創(chuàng)建二叉樹
void BinTree::createBinTree(BinTreeNode *&t){
    Type createData;
    cin>>createData;  //鍵盤輸入創(chuàng)建序列

    if(refval == createData){  //與#相同，則賦空，相當(dāng)于給左右孩子賦空
        t = NULL;
    }else{
        t = new BinTreeNode(createData);  //申請(qǐng)空間
        createBinTree(t->leftChild);  //左遞歸創(chuàng)建
        createBinTree(t->rightChild);  //右遞歸創(chuàng)建
    }
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱：二叉樹的遞歸創(chuàng)建-創(chuàng)新互聯(lián)
文章起源：http://weahome.cn/article/dseihd.html