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<typename Type> //中序和后序创建
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); //先创建右子树,中跨k+1个,后跨k个,到底右边,右边一共n-k-1个节点;
createBinTree_1(t->leftChild, LVR, LRV, k);//在创建左子树,从头开始,一共k个;
}
template<typename Type> //先序和中序创建
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&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<Type>(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<iostream> //引入头文件
using namespace std;
template<typename Type> //声明友元类
class BinTree;
template<typename Type>
class BinTreeNode{ //二叉树结点的模板类
friend class BinTree<Type>; //可以调用其私有数据成员
public:
BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){} //默认的构造函数
BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *right = NULL) :
data(value), leftChild(left), rightChild(right){} //带参数的构造函数
~BinTreeNode(){} //析构函数暂时什么都不做
private:
Type data; //数据
BinTreeNode *leftChild; //左孩子指针
BinTreeNode *rightChild; //右孩子指针
};
////////////////////////////////////////////////////以上是结点类型
template<typename Type>
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<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; //根节点(要是C语言的话,的弄一个指向根节点的指针);
Type refval; //'#'标志,创建多余空间,利用率比较低。
};
////////////////////////////////////////////////////////////以上是二叉树的类型
template<typename Type> //类外函数的定义
void BinTree<Type>::createBinTree(){
//createBinTree(root);
root = createBinTree_1(); //调用内部写保护的方法实现
}
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);
}
////////////////////////////////////////////////////////////以上是类外调用保护方法
//其下就是具体的创建过程
template<typename Type> //中序和后序创建
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); //先创建右子树,中跨k+1个,后跨k个,到底右边,右边一共n-k-1个节点;
createBinTree_1(t->leftChild, LVR, LRV, k);//在创建左子树,从头开始,一共k个;
}
template<typename Type> //先序和中序创建
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&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<Type>(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<typename Type> //返回指针root接受,字符串创建
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,字符串创建
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接受, 键盘输入先序创建
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,根据先根序创建二叉树
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t){
Type createData;
cin>>createData; //键盘输入创建序列
if(refval == createData){ //与#相同,则赋空,相当于给左右孩子赋空
t = NULL;
}else{
t = new BinTreeNode<Type>(createData); //申请空间
createBinTree(t->leftChild); //左递归创建
createBinTree(t->rightChild); //右递归创建
}
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。