二叉树的递归创建

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  //中序和后序创建
void BinTree::createBinTree_1(BinTreeNode *&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(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  //先序和中序创建
void BinTree::createBinTree(BinTreeNode *&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(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    //引入头文件
using namespace std;

template  //声明友元类
class BinTree;

template
class BinTreeNode{      //二叉树结点的模板类
    friend class BinTree;  //可以调用其私有数据成员
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}  //默认的构造函数
    BinTreeNode(Type value, BinTreeNode *left = NULL, BinTreeNode *right = NULL) :
    data(value), leftChild(left), rightChild(right){}  //带参数的构造函数
    ~BinTreeNode(){}  //析构函数暂时什么都不做
private:
    Type data;   //数据
    BinTreeNode *leftChild; //左孩子指针
    BinTreeNode *rightChild;  //右孩子指针
};
////////////////////////////////////////////////////以上是结点类型
template
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 *&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;    //根节点(要是C语言的话，的弄一个指向根节点的指针)；
    Type               refval;  //'#'标志，创建多余空间，利用率比较低。
};
////////////////////////////////////////////////////////////以上是二叉树的类型    
template   //类外函数的定义
void BinTree::createBinTree(){
    //createBinTree(root); 
    root = createBinTree_1();  //调用内部写保护的方法实现
}

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);
}
////////////////////////////////////////////////////////////以上是类外调用保护方法
//其下就是具体的创建过程
template  //中序和后序创建
void BinTree::createBinTree_1(BinTreeNode *&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(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  //先序和中序创建
void BinTree::createBinTree(BinTreeNode *&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(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  //返回指针root接受，字符串创建
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，字符串创建
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接受, 键盘输入先序创建
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,根据先根序创建二叉树
void BinTree::createBinTree(BinTreeNode *&t){
    Type createData;
    cin>>createData;  //键盘输入创建序列

    if(refval == createData){  //与#相同，则赋空，相当于给左右孩子赋空
        t = NULL;
    }else{
        t = new BinTreeNode(createData);  //申请空间
        createBinTree(t->leftChild);  //左递归创建
        createBinTree(t->rightChild);  //右递归创建
    }
}