目录
1.二叉树的半自动创建
题目是以前序序列输进的数组，那我们就需要用前序的思想来创建节点。
若读到#，就返回一个空指针，让这个节点成为空节点，在之后的中序遍历中不会访问到。
但是不要忘了让数组的下标++（传址调用），这样才能在接下来的递归子问题中访问数组后面的值。
若数组中的数值满足条件，就以该值为树节点的val创建新节点，然后在其左右两子代节点以
新的数值为val再创建新节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct BTNode {
struct BTNode* left;
struct BTNode* right;
char val;
}BTNode;
BTNode* CreatTree(char* arr, int* pi) {
if (arr[*pi] == '#') {
(*pi)++;
return NULL;
}
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->val = arr[(*pi)++];
newnode->left = CreatTree(arr, pi);
newnode->right = CreatTree(arr, pi);
return newnode;
}
void Inorder(BTNode* tree, char* arr) {//中序是左子树 根 右子树
if (tree == NULL) {
return;
}
Inorder(tree->left, arr);
printf("%c ", tree->val);
Inorder(tree->right, arr);
}
int main() {
char arr[100];
scanf("%s", arr);
int i = 0;
BTNode* tree = CreatTree(arr, &i);
Inorder(tree, arr);
return 0;
}2.二叉树的销毁
想要销毁一棵树，由于每个节点都是由malloc得来的，所以我们需要使用free函数来逐 个释放节点。目前为止，我们有三种方法“逐个”遍历：前序、中序、后序。
若使用前序（我们以上图二叉树为例），先删除节点1，那就必须使用两个变量来记录他的左右子树；若使用后序，先删除每一个根的左右子树，再删除自己，会更简介一些，所以我们采用后序遍历的删除方法。
后序更佳：
void TreeDestroy(BTNode* root) {
if (root == NULL) {
return;//空几乎都是二叉树的最小子问题
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}3.层序遍历
先创建一个队列。
从根节点开始，将根节点的指针，作为队列的元素放入队列。利用队列的特性“先入先出”
每一次拿出来元素，都将该元素的左右子代压入队列。这样就能做到每拿出一层，都能将下一排的元素一次压入队列。
以下图为例：先将1压入，再将1拿出，压入1->left和1->right，也就是2和4，再将2拿出，压入3和"NULL"(3和NULL由于队列的特点，会被压在4的后面，但是NULL作为最小子问题是不会被压入的）紧接着再在队列的队顶Pop，出队列的依然是4,又压入了5和6,由此前两层已经被成功层序遍历。
当队列为空的时候，表示已经没有元素被压入（NULL不算被压入），此时就算全部遍历完成
前序+队列（利用队列的先进先出）
代码实现：
我们直接复用前文中造好的队列接口
注意Queue.c和Queue.h文件必须被复制进二叉树项目文件的目录，因为文件编译时自己写的头文件只会在相同目录下查找
tips:注意将声明和定义相分离，若是头文件中即声明也定义，.c文件也定义，由于头文件在编译时会被完全打开，就会发生定义冲突。
//层序遍历
void TreeLevelOrder(BTNode* root) {
Queue q;
QueueInit(&q);
if (root) {
QueuePush(&q, root);
}
while (!QueueEmpty(&q)) {
BTNode* tree = QueueFront(&q);
QueuePop(&q);
printf("%d ", tree->val);
//压入子代
if (tree->left) {
QueuePush(&q, tree->left);
}
if (tree->right) {
QueuePush(&q, tree->right);
}
}
QueueDestroy(&q);
}请注意，在while循环中到底pop的是谁？
我们是将已经存在的二叉树的节点指针作为队列元素中的val存入队列，pop删除的是队列元素，而在pop之前我们已经拿出了该队列元素中的值到tree变量中（QueueFront）。
4. 判断完全二叉树
个数只能用于计算满二叉树，因为个数不能判断满二叉树的最后一层是否是连续的
用层序遍历判断：
非完全二叉树：非空节点不连续
完全二叉树：非空节点连续
沿用层序遍历的思想，当我们拿出的数为NULL时就跳出循环，但是不销毁队列。
再在队列中一个一个front和pop，如果又出来一个非空，说明非空节点不连续，返回false
//利用层序遍历来判断二叉树是否连续
bool isContinuousTree(BTNode* root) {
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front==NULL) {
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL) {
return false;
}
}
QueueDestroy(&q);
return true;
}5. 二叉树的性质
1. 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有 2^(i - 1) 个结点.2. 若规定根节点的层数为 1 ，则 深度为 h 的二叉树的最大结点数是(2^h)-1.3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为 a , 度为 2 的分支结点个数为b , 则有a ＝b ＋ 1
具体证明在二叉树的篇章一有 写文章-CSDN创作中心。199个度为2的，就说明有200个叶子，故选B4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h=log(n+1)5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对 于序号为i 的结点有：1. 若 i>0 ， i 位置节点的双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号，无双亲节点2. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子3. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子
利用以上规律可以有效解决下题：
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
12.已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为：
欢迎将答案写在评论区！