二叉树的递归创建
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://scyanting.com/article/gdgoeo.html