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

1、樹(shù)

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

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

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

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

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

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

  樹(shù)的高度，從1開(kāi)始算；

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

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

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

2、二叉樹(shù)

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

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

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

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

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

  (5)、滿(mǎn)二叉樹(shù)和完全二叉樹(shù)：

  滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<typename Type>  //中序和后序創(chuàng)建
void BinTree<Type>::createBinTree_1(BinTreeNode<Type> *&t, const char *LVR, const char *LRV, int n){
    if(n == 0){   //字符串長(zhǎng)度為0，建立空樹(shù)
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != LRV[n-1]){  //找出根結(jié)點(diǎn)的下標(biāo)
        k++;
    }
    t = new BinTreeNode<Type>(LVR[k]);  //建立根結(jié)點(diǎn)
    
    
    createBinTree_1(t->rightChild, LVR+k+1, LRV+k, n-k-1); //先創(chuàng)建右子樹(shù)，中跨k+1個(gè)，后跨k個(gè)，到底右邊，右邊一共n-k-1個(gè)節(jié)點(diǎn)；
    createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹(shù)，從頭開(kāi)始，一共k個(gè)；
}
template<typename Type>  //先序和中序創(chuàng)建
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n){
    if(n == 0){   //要是長(zhǎng)度為0，則創(chuàng)建空樹(shù)
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != VLR[0]){  //由先序找到在中序中的位置k;
        k++;
    }
    t = new BinTreeNode<Type>(LVR[k]);  //首先創(chuàng)建根
    createBinTree(t->leftChild, VLR+1, LVR, k);  //創(chuàng)建左邊，跨過(guò)根， 中序， 根左邊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)建的，好想，畫(huà)畫(huà)圖就理解了，代碼如下：

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

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

template<typename Type>  //聲明友元類(lèi)
class BinTree;

template<typename Type>
class BinTreeNode{      //二叉樹(shù)結(jié)點(diǎn)的模板類(lèi)
    friend class BinTree<Type>;  //可以調(diào)用其私有數(shù)據(jù)成員
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}  //默認(rèn)的構(gòu)造函數(shù)
    BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *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)類(lèi)型
template<typename Type>
class BinTree{       //二叉樹(shù)的模板類(lèi)
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ù)聲明，類(lèi)外定義
    void createBinTree();  //鍵盤(pán)輸入創(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ù)方法，外部不能直接訪(fǎng)問(wèn)，供內(nèi)部函數(shù)的調(diào)用  函數(shù)聲明，類(lèi)外定義
    void createBinTree(BinTreeNode<Type> *&t);  
    BinTreeNode<Type>* createBinTree_1();
    void createBinTree(const char *&str, BinTreeNode<Type> *&t);
    BinTreeNode<Type>* createBinTree_1(const char *&str);
    void createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n);
    void createBinTree_1(BinTreeNode<Type> *&t, const char *LVR, const char *LRV, int n);
private:
    BinTreeNode<Type> *root;    //根節(jié)點(diǎn)(要是C語(yǔ)言的話(huà)，的弄一個(gè)指向根節(jié)點(diǎn)的指針)；
    Type               refval;  //'#'標(biāo)志，創(chuàng)建多余空間，利用率比較低。
};
////////////////////////////////////////////////////////////以上是二叉樹(shù)的類(lèi)型    
template<typename Type>   //類(lèi)外函數(shù)的定義
void BinTree<Type>::createBinTree(){
    //createBinTree(root); 
    root = createBinTree_1();  //調(diào)用內(nèi)部寫(xiě)保護(hù)的方法實(shí)現(xiàn)
}

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

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

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

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

    return t;
}

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

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