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

1、樹

站在用戶的角度思考問題，與客戶深入溝通，找到定日網(wǎng)站設計與定日網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設計與互聯(lián)網(wǎng)技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都網(wǎng)站建設、網(wǎng)站建設、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名與空間、虛擬主機、企業(yè)郵箱。業(yè)務覆蓋定日地區(qū)。

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

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

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

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

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

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

樹的高度，從1開始算；

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

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

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

2、二叉樹

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

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

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

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

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

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

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

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

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

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

3、二叉樹的存儲形式：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<typename Type>  //中序和后序創(chuàng)建
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); //先創(chuàng)建右子樹，中跨k+1個，后跨k個，到底右邊，右邊一共n-k-1個節(jié)點；
    createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共k個；
}
template<typename Type>  //先序和中序創(chuàng)建
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n){
    if(n == 0){   //要是長度為0，則創(chuàng)建空樹
        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)建左邊，跨過根， 中序， 根左邊k個節(jié)點；
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);//創(chuàng)建右邊，肯定都得+K+1,根右邊n-k-1個結點；
}

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

#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>;  //可以調(diào)用其私有數(shù)據(jù)成員
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}  //默認的構造函數(shù)
    BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *right = NULL) :
    data(value), leftChild(left), rightChild(right){}  //帶參數(shù)的構造函數(shù)
    ~BinTreeNode(){}  //析構函數(shù)暫時什么都不做
private:
    Type data;   //數(shù)據(jù)
    BinTreeNode *leftChild; //左孩子指針
    BinTreeNode *rightChild;  //右孩子指針
};
////////////////////////////////////////////////////以上是結點類型
template<typename Type>
class BinTree{       //二叉樹的模板類
public:
    BinTree() : root(NULL){}  ////默認的構造函數(shù)
    BinTree(Type ref) : root(NULL), refval(ref){} //帶參數(shù)的構造函數(shù)
    ~BinTree(){}
public:   //以下四個是供外部調(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個是保護方法，外部不能直接訪問，供內(nèi)部函數(shù)的調(diào)用  函數(shù)聲明，類外定義
    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é)點(要是C語言的話，的弄一個指向根節(jié)點的指針)；
    Type               refval;  //'#'標志，創(chuàng)建多余空間，利用率比較低。
};
////////////////////////////////////////////////////////////以上是二叉樹的類型    
template<typename Type>   //類外函數(shù)的定義
void BinTree<Type>::createBinTree(){
    //createBinTree(root); 
    root = createBinTree_1();  //調(diào)用內(nèi)部寫保護的方法實現(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);
}
////////////////////////////////////////////////////////////以上是類外調(diào)用保護方法
//其下就是具體的創(chuàng)建過程
template<typename Type>  //中序和后序創(chuàng)建
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); //先創(chuàng)建右子樹，中跨k+1個，后跨k個，到底右邊，右邊一共n-k-1個節(jié)點；
    createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共k個；
}
template<typename Type>  //先序和中序創(chuàng)建
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n){
    if(n == 0){   //要是長度為0，則創(chuàng)建空樹
        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)建左邊，跨過根， 中序， 根左邊k個節(jié)點；
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);//創(chuàng)建右邊，肯定都得+K+1,根右邊n-k-1個結點；
}

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接受, 鍵盤輸入先序創(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)建二叉樹
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t){
    Type createData;
    cin>>createData;  //鍵盤輸入創(chuàng)建序列

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

新聞標題：二叉樹的遞歸創(chuàng)建
文章分享：http://www.muchs.cn/article40/gdgoeo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站策劃、用戶體驗、面包屑導航、App設計、建站公司

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容