建树 ，递归建树

输入为

建立树

递归

函数参数表为引用或指针

void Creat(BiTree *T){char ch;scanf("%c",&ch);if(ch=='#'){*T=NULL;}else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=ch;Creat(&(*T)->nextleft);Creat(&(*T)->nextright);}
}

void CreatBiTree(BiTree &T){char ch;cin>>ch;if(ch=='#'){T=NULL;}else if(ch!='#'){T=new BiTNode;T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}
}

求叶子节点数量

如果左右孩子为空指针，自己不为空，那么就是叶子结点；如果左右不空，就不是叶子结点。

递归解决，返回左右子树叶子结点的加和 

using namespace std;
#include<iostream>
void creat(BiTree &tree){char t;cin>>t;if(t=='#'){tree=nullptr;}else{tree=new BiTNode;tree->data=t;creat(tree->lchild);creat(tree->rchild);}
}
int countleaf(BiTree &tree){if(tree!=nullptr){if(tree->lchild!=nullptr||tree->rchild!=nullptr){return countleaf(tree->lchild)+countleaf(tree->rchild);}else{return 1;}}else{return 0;}
}

思路就是先判断当下结点是不是空结点

是，返回是的输出

不是，则接着判断是不是叶子节点

是，则返回1

不是，则递归向下

二叉树高度

#include<iostream>
using namespace std;
void creat(BiTree &tree){char t;cin>>t;if(t=='#'){tree=nullptr;}else{tree=new BiTNode;tree->data=t;creat(tree->lchild);creat(tree->rchild);}
}
int Depth(BiTree tree){if(tree==nullptr){return 0;}else{if(tree->lchild!=nullptr||tree->rchild!=nullptr){return 1+max(Depth(tree->rchild),Depth(tree->lchild));}else{return 1;}}
}

小总结 

就是先判断是不是空结点，如果是空结点就直接返回；

不是，就接着判断当下结点是不是叶子结点，判断方式为该节点的孩子指针是否都是空，只要有一个不空就不是叶子结点

如果是叶子结点就意味着递归到了底层，进行相应的操作与对应的返回值

如果不是，就是接着递归向下，返回值为相应的操作

一些性质 

求 后序是左右根，先序为根左右，中序是左根右

如果后序和中序相同，则都没有右结点

如果结点有左孩子，中序为左根右

中序前驱，就是中序遍历中该节点的前一个结点

完全二叉树有111个结点，序列在13号位置上的结点，在先序遍历序列中排在96号结点位置之前

七位2进制到128，六位二进制到64，有111个结点，说明到了第8层，还没填满

第一层1个结点，第二层2，第三层2^2,第六层2^5,

第n层一共最多能装为2^(n-1),取对数，向上取整，就是说，找底数最接近的规整指数，往上找，而不是往下找

111比64大，但是要往上找，最近的是128，即2^7,所以共有7层，

根1左1右

后序与中序遍历的序列相反，说明所有结点均无左孩子

由于第i结点的左孩子下标为2i,

对于有n个结点的二叉树，它的高度不能确定，

最高为链表型，高为n；最低为完全二叉树，为1+log2n，向上取整