本文主要是介绍11.3递归建二叉树，二叉树函数规范化输入输出，一些二叉树性质，求叶子结点与树的高度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
建树 ，递归建树
输入为
建立树
递归
函数参数表为引用或指针
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，向上取整
这篇关于11.3递归建二叉树，二叉树函数规范化输入输出，一些二叉树性质，求叶子结点与树的高度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
