二叉樹的遞歸創建

1、樹

  (1)、樹形結構本身具有遞歸的性質(在其后的編程中體現的淋漓盡致)!

  樹是一種非常重要的非線性結構。

  (2)、幾個概念：結點的度，就是分支個數(孩子個數)；

  樹的度，結點度中最大的(孩子最多的)；

  非葉子結點，度 > 0 (有孩子結點)；

  葉子結點，度為0的 (沒有孩子結點)；

  樹的高度，從1開始算；

(3)、為什么要學習二叉樹？

  原因：所有的樹形結構(包括森林)都可以轉化為二叉樹。二叉樹是樹形結構的基礎，

  只有學好了二叉樹才能學好其它的。

2、二叉樹

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

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

  (3)、每一層最多結點個數：2^(i-1)；是偶數個，i代表層數(從1開始)；

  整棵樹的最多結點個數：2^k - 1; 是奇數個(因為除了根節點只有一個，其它每層都是偶數個)，k代表層數(從1開始)；

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

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

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

  完全二叉樹有N個結點的高度：[log2^N](向下取整) + 1；

3、二叉樹的存儲形式：

  (1)、線性存儲，數組存儲，------->針對完全二叉樹好，

  (2)、鏈式存儲-------------->針對普通二叉樹；

4、二叉樹的創建：

  我認為有9種創建方式：寫出先序序列，

  從鍵盤輸入的建立方案：參數和返回值創建  2            

  根據(文件)字符串的傳入：參數和返回值創建  2          

  由先序和中序創建  2

  由中序和后序創建  2    

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

  以后我還會寫上非遞歸創建二叉樹，不在浪費多余以#代替的空間  1

5、創建二叉樹：

  均由C++實現，寫出先序序列，在進行創建

  (1)、因為樹形結構本身具有遞歸性質，所以以下均是遞歸創建，以后我會寫非遞歸創建的。

  (2)、遞歸創建符合數學思維和邏輯，但是容易造成棧溢出，并且遞歸占用系統資源，好寫但不明智的做法，我認為寫程序應該盡量避免遞歸的做法！！

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

  (4)、先序和后序一般不用于創建二叉樹，因為存在歧義：

由先序和中序，中序和后序創建二叉樹是重點：

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

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

#ifndef _BIN_TREE_H_   //預編譯條件宏
#define _BIN_TREE_H_

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

template<typename Type>  //聲明友元類
class BinTree;

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

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

template<typename Type>  //返回指針root接受，字符串創建
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，字符串創建
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接受, 鍵盤輸入先序創建
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,根據先根序創建二叉樹
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t){
    Type createData;
    cin>>createData;  //鍵盤輸入創建序列

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