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<typenameType>//中序和后序创建voidBinTree<Type>::createBinTree_1(BinTreeNode<Type>*&t,constchar*LVR,constchar*LRV,intn){if(n==0){//字符串长度为0,建立空树t=NULL;return;}intk=0;while(LVR[k]!=LRV[n-1]){//找出根结点的下标k++;}t=newBinTreeNode<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<typenameType>//先序和中序创建voidBinTree<Type>::createBinTree(BinTreeNode<Type>*&t,constchar*VLR,constchar*LVR,intn){if(n==0){//要是长度为0,则创建空树t=NULL;return;}intk=0;while(LVR[k]!=VLR[0]){//由先序找到在中序中的位置k;k++;}t=newBinTreeNode<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>//引入头文件usingnamespacestd;template<typenameType>//声明友元类classBinTree;template<typenameType>classBinTreeNode{//二叉树结点的模板类friendclassBinTree<Type>;//可以调用其私有数据成员public:BinTreeNode():data(Type()),leftChild(NULL),rightChild(NULL){}//默认的构造函数BinTreeNode(Typevalue,BinTreeNode<Type>*left=NULL,BinTreeNode<Type>*right=NULL):data(value),leftChild(left),rightChild(right){}//带参数的构造函数~BinTreeNode(){}//析构函数暂时什么都不做private:Typedata;//数据BinTreeNode*leftChild;//左孩子指针BinTreeNode*rightChild;//右孩子指针};////////////////////////////////////////////////////以上是结点类型template<typenameType>classBinTree{//二叉树的模板类public:BinTree():root(NULL){}////默认的构造函数BinTree(Typeref):root(NULL),refval(ref){}//带参数的构造函数~BinTree(){}public://以下四个是供外部调用的接口函数声明,类外定义voidcreateBinTree();//键盘输入创建voidcreateBinTree(constchar*str);//主函数传字符串创建voidcreateBinTree(constchar*VLR,constchar*LVR,intn);//先序和中序创建voidcreateBinTree_1(constchar*LVR,constchar*LRV,intn);//中序和后序创建protected://以下6个是保护方法,外部不能直接访问,供内部函数的调用函数声明,类外定义voidcreateBinTree(BinTreeNode<Type>*&t);BinTreeNode<Type>*createBinTree_1();voidcreateBinTree(constchar*&str,BinTreeNode<Type>*&t);BinTreeNode<Type>*createBinTree_1(constchar*&str);voidcreateBinTree(BinTreeNode<Type>*&t,constchar*VLR,constchar*LVR,intn);voidcreateBinTree_1(BinTreeNode<Type>*&t,constchar*LVR,constchar*LRV,intn);private:BinTreeNode<Type>*root;//根节点(要是C语言的话,的弄一个指向根节点的指针);Typerefval;//'#'标志,创建多余空间,利用率比较低。};////////////////////////////////////////////////////////////以上是二叉树的类型template<typenameType>//类外函数的定义voidBinTree<Type>::createBinTree(){//createBinTree(root);root=createBinTree_1();//调用内部写保护的方法实现}template<typenameType>voidBinTree<Type>::createBinTree(constchar*str){//createBinTree(str,root);root=createBinTree_1(str);}template<typenameType>voidBinTree<Type>::createBinTree(constchar*VLR,constchar*LVR,intn){createBinTree(root,VLR,LVR,n);}template<typenameType>voidBinTree<Type>::createBinTree_1(constchar*LVR,constchar*LRV,intn){createBinTree_1(root,LVR,LRV,n);}////////////////////////////////////////////////////////////以上是类外调用保护方法//其下就是具体的创建过程template<typenameType>//中序和后序创建voidBinTree<Type>::createBinTree_1(BinTreeNode<Type>*&t,constchar*LVR,constchar*LRV,intn){if(n==0){//字符串长度为0,建立空树t=NULL;return;}intk=0;while(LVR[k]!=LRV[n-1]){//找出根结点的下标k++;}t=newBinTreeNode<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<typenameType>//先序和中序创建voidBinTree<Type>::createBinTree(BinTreeNode<Type>*&t,constchar*VLR,constchar*LVR,intn){if(n==0){//要是长度为0,则创建空树t=NULL;return;}intk=0;while(LVR[k]!=VLR[0]){//由先序找到在中序中的位置k;k++;}t=newBinTreeNode<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<typenameType>//返回指针root接受,字符串创建BinTreeNode<Type>*BinTree<Type>::createBinTree_1(constchar*&str){BinTreeNode<Type>*t;if(refval==*str){t=NULL;}else{t=newBinTreeNode<Type>(*str);t->leftChild=createBinTree_1(++str);t->rightChild=createBinTree_1(++str);}returnt;}template<typenameType>//引用直接更改root,字符串创建voidBinTree<Type>::createBinTree(constchar*&str,BinTreeNode<Type>*&t){if(*str==refval){t=NULL;}else{t=newBinTreeNode<Type>(*str);createBinTree(++str,t->leftChild);//前加,后加不一样!!!在这里,就是传引用,保证每次字符串都是往后走的createBinTree(++str,t->rightChild);}}template<typenameType>//返回指针root接受,键盘输入先序创建BinTreeNode<Type>*BinTree<Type>::createBinTree_1(){TypecreateData;cin>>createData;BinTreeNode<Type>*t;if(refval==createData){t=NULL;}else{t=newBinTreeNode<Type>(createData);t->leftChild=createBinTree_1();t->rightChild=createBinTree_1();}returnt;}template<typenameType>//引用直接更改root,根据先根序创建二叉树voidBinTree<Type>::createBinTree(BinTreeNode<Type>*&t){TypecreateData;cin>>createData;//键盘输入创建序列if(refval==createData){//与#相同,则赋空,相当于给左右孩子赋空t=NULL;}else{t=newBinTreeNode<Type>(createData);//申请空间createBinTree(t->leftChild);//左递归创建createBinTree(t->rightChild);//右递归创建}}