二叉树的递归创建

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);  //右递归创建
    }
}

    

          


网站标题:二叉树的递归创建
标题链接:http://pwwzsj.com/article/gdgoeo.html