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