目录
二叉树的遍历：
1.前序遍历：根->左子树->右子树
前序遍历就是按照上述的根->左子树->右子树的方法进行遍历的。（注意：我们在遍历过程中可以写出已经访问到的空的节点以便我们去理解）（下面我们用N来表示空）
上述二叉树的前序遍历顺序为：1->2->3->N->N->N->4->5->N->N->6->N->N
举个例子：当你前序遍历到2时，2本身是根。2的左子树就是3所对应的树，2的右子树就是N，先遍历2，再遍历3所在的子树（按照同样的前序遍历方法进行遍历），回到2这个节点时，再去遍历2的右子树N，遍历完2这个节点后，就回到1这个节点去遍历1这个节点所对应的右子树（因为此时1所对应的左子树已经遍历完了，1自身节点在刚开始时就已经遍历过了）。
2.中序遍历：左子树->根->右子树
上述二叉树的中序遍历顺序为：N->3->N->2->N->1->N->5->N->4->N->6->N
3.后序遍历：左子树->右子树->根
上述二叉树的后序遍历顺序为：N->N->3->N->2->N->N->5->N->N->6->4->1
4.层序遍历：从第一层到最后一层，一层一层地遍历
上述二叉树的层序遍历顺序为：1->2->4->3->5->6
二叉树的基本结构：
#pragma once
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;//左孩子
struct BinaryTreeNode* right;//右孩子
}BTNode;二叉树中的常用接口：
//构造一个节点
BTNode* buynode(int x);
// 构建二叉树
BTNode* BinaryTreeCreate();
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);构造一个节点：
//构造一个节点
BTNode* buynode(int x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
构建二叉树：
我们构建的树以这个树为例。
// 构建二叉树
BTNode* BinaryTreeCreate()
{
BTNode* node1 = buynode(1);
BTNode* node2 = buynode(2);
BTNode* node4 = buynode(4);
BTNode* node3 = buynode(3);
BTNode* node5 = buynode(5);
BTNode* node6 = buynode(6);
node1->left = node2;
node2->left = node3;
node1->right = node4;
node4->left = node5;
node4->right = node6;
return node1;
}二叉树销毁：
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if ((*root)==NULL)
{
return;
}
BinaryTreeDestory((*root)->left);
BinaryTreeDestory((*root)->right);
free(*root);
*root = NULL;
}销毁二叉树，我们可以用递归实现。当根节点为NULL时返回即可，不需要free了，这里我们递归选择先销毁左子树再销毁右子树，最后销毁根节点的原因是，如果先free根节点，就会导致找不到左右子树。
二叉树节点个数：
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}如果此树为空树，则节点个数故为0，返回0即可。（递归的归的条件）
如果此树不为空树，那么此树的节点个数=左子树节点个数+右子树节点个数+1。
二叉树叶子节点个数：
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}如果此树为空树，则叶子节点个数故为0，返回0即可。
接下来判断此节点是否为叶子节点，如果是则返回叶子结点个数1。
如果此节点不是叶子节点，则此树的叶子结点个数=左子树的叶子结点+右子树的叶子结点个数。
二叉树的高度：
//二叉树的高度
int BinaryTreehigh(BTNode* root)
{
if (root == NULL)
return 0;
int high1 = BinaryTreehigh(root->left);
int high2 = BinaryTreehigh(root->right);
return high1 > high2 ? high1+1 : high2 + 1;
}如果此树为空树，故树的高度为0，返回0即可。
如果此树不是空树，则此树的高度=max(左子树高度，右子树高度)+1。
二叉树第k层节点个数：
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}如果此树为空树，故则第k层节点个数一定为0，返回0即可。
如果k=1，则返回的是第一层的节点个数，故返回1。
如果k>1，则需要拆解为子问题，第k层节点个数=左子树的第k-1层节点个数+右子树的第k-1层节点个数
二叉树查找值为x的节点：
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}如果此树为空树，故查找不到值为x的节点，返回NULL即可。
如果根节点数值==x，则返回根节点。
接下来，如果在左子树找到了值为x的节点，则返回此节点。
然后，如果在右子树找到了值为x的节点，则返回此节点。
来到最后，就是找不到值为x的节点了，故返回NULL。
二叉树前序遍历：
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%c->",root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}二叉树中序遍历：
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
printf("%c->", root->data);
BinaryTreeInOrder(root->right);
}二叉树后序遍历：
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c->", root->data);
}层序遍历：
层序遍历我们需要借助队列这个数据结构。
例如：我们先将根节点1入队列，出队列的过程中，出1，就入2和4，出2，就入3，出4，就入5和6......循环往复，直到队列为空即可完成层序遍历。
队列：
typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;为什么队列中要存储二叉树的节点指针？
因为所占空间小。
层序遍历代码如图：
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
QueueBack(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c->", front->data);
if(root->left)
QueueBack(&q, front->left);
if (root->right)
QueueBack(&q, front->right);
}
}判断二叉树是否是完全二叉树：
判断二叉树是否为完全二叉树，我们可以用层序遍历的方法，只不过这次NULL也要入队列，如果非空和空不是连续的，则此树就不是完全二叉树。
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
QueueBack(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
break;
QueueBack(&q, front->left);
QueueBack(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
return 0;
}
return 1;
}