二叉樹的遞歸創(chuàng)建
1、樹
站在用戶的角度思考問題，與客戶深入溝通，找到定日網(wǎng)站設(shè)計(jì)與定日網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、虛擬主機(jī)、企業(yè)郵箱。業(yè)務(wù)覆蓋定日地區(qū)。
(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<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，建立空樹
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)建右子樹，中跨k+1個(gè)，后跨k個(gè)，到底右邊，右邊一共n-k-1個(gè)節(jié)點(diǎn)；
createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共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)建空樹
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個(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<iostream> //引入頭文件
using namespace std;
template<typename Type> //聲明友元類
class BinTree;
template<typename Type>
class BinTreeNode{ //二叉樹結(jié)點(diǎn)的模板類
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)類型
template<typename Type>
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<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ǔ)言的話，的弄一個(gè)指向根節(jié)點(diǎn)的指針)；
Type refval; //'#'標(biāo)志，創(chuàng)建多余空間，利用率比較低。
};
////////////////////////////////////////////////////////////以上是二叉樹的類型
template<typename Type> //類外函數(shù)的定義
void BinTree<Type>::createBinTree(){
//createBinTree(root);
root = createBinTree_1(); //調(diào)用內(nèi)部寫保護(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);
}
////////////////////////////////////////////////////////////以上是類外調(diào)用保護(hù)方法
//其下就是具體的創(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){ //字符串長(zhǎng)度為0，建立空樹
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)建右子樹，中跨k+1個(gè)，后跨k個(gè)，到底右邊，右邊一共n-k-1個(gè)節(jié)點(diǎn)；
createBinTree_1(t->leftChild, LVR, LRV, k);//在創(chuàng)建左子樹，從頭開始，一共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)建空樹
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個(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接受, 鍵盤輸入先序創(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){ //與#相同，則賦空，相當(dāng)于給左右孩子賦空
t = NULL;
}else{
t = new BinTreeNode<Type>(createData); //申請(qǐng)空間
createBinTree(t->leftChild); //左遞歸創(chuàng)建
createBinTree(t->rightChild); //右遞歸創(chuàng)建
}
}
新聞標(biāo)題：二叉樹的遞歸創(chuàng)建
文章分享：http://chinadenli.net/article40/gdgoeo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站策劃、用戶體驗(yàn)、面包屑導(dǎo)航、App設(shè)計(jì)、建站公司
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
- 什么是外貿(mào)建站？建站前都有哪些必須了解的？ 2015-08-19
- 外貿(mào)建站中的哪些細(xì)節(jié)影響著網(wǎng)站流量？ 2015-06-11
- 外貿(mào)建站seo推廣除了內(nèi)容，頁(yè)面鏈接也很重要 2016-08-19
- 談?wù)勍赓Q(mào)建站為什么要選擇香港服務(wù)器？ 2022-10-03
- 越秀區(qū)小北路外貿(mào)建站,越秀區(qū)小北路外貿(mào)網(wǎng)站建設(shè)公司 2016-04-06
- 外貿(mào)建站要注意什么？ 2023-01-06
- 外貿(mào)建站系統(tǒng)如何選，要從不同角度去分析 2022-05-27
- 外貿(mào)建站租用香港云服務(wù)器還是美國(guó)云服務(wù)器好？ 2022-10-02
- 做外貿(mào)建站為什么要選穩(wěn)定快速安全的海外主機(jī)? 2015-04-29
- 外貿(mào)建站需要哪些東西？?? 2014-07-23
- 外貿(mào)建站選美國(guó)空間還是香港空間好？ 2022-10-10
- 外貿(mào)建站不得不說的秘密 2015-05-07