在建立一个简单的二叉树之前，我们需要了解二叉树的特点与性质。
二叉树的特点：
????????1.二叉树不存在度大于2的结点。
????????2.二叉树是有序树，二叉树的子树有左右之分，次序不能颠倒。
????????3.空树也是二叉树，二叉树由一个根节点和两颗分别叫做左子树和右子树的二叉树构成。
对于任意二叉树，都是由以上几种情况复合而成。
?二叉树的储存结构：
????????1.顺序结构，一般比较适合完全二叉树。
????????2.链式结构，用一个链表来表示一颗二叉树，用链来表示结点之间的逻辑关系。
????????我们则选择使用较为通用的链式结构，链式结构分为二叉链和三叉链，我们选择使用较为简单的二叉链。
用二叉链表示一个二叉树：
typedef int BTDataType;
typedef struct BTNode {
struct BTNode* left;//左孩子
struct BTNode* right;//右孩子
BTDataType data;//结点的值
}BTNode;
?????????在初期，我们可以快速创建一个如图的简单二叉树，待完全掌握其结构时，再研究二叉树的真正创建方式。
BTNode* buyBtNode(BTDataType x)
{
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode==NULL)
{
assert(0);
return NULL;
}
newNode->data = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = buyNode(1);
BTNode* node2 = buyNode(2);
BTNode* node3 = buyNode(3);
BTNode* node4 = buyNode(4);
BTNode* node5 = buyNode(5);
BTNode* node6 = buyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}????????这样我们就创建了一个简单的二叉树，此后我们会在此二叉树的基础上完成一系列基本操作。
一、二叉树的遍历
????????二叉树的遍历时按照某种和规则，依次对二叉树中的结点进行处理，且每个结点只处理一次。
????????二叉树的遍历规则有：前序遍历，中序遍历和后序遍历。
????????前序遍历：访问根结点的操作发生在遍历其左右子树之前。（根>左>右）
????????中序遍历：访问根结点的操作发生在遍历其左右子树之中。（左>根>右）
????????后序遍历：访问根结点的操作发生在遍历其左右子树之后。（左>右>根）
void PreOrder(BTNode* root);//前序遍历
void InOrder(BTNode* root);//中序遍历
void PostOrder(BTNode* root);//后序遍历
????????
?????????我们可以把问题分解成：遍历根节点以及根节点的两个子树，即可以用递归的思想解决。
首先解决前序遍历：
void PreOrder(BTNode* root)
{
if (root)
{
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
}
????????中序序遍历我们只需先遍历左子树，再遍历根结点，最后遍历右子树；
????????同理，后序遍历则是先遍历左子树和右子树，最后遍历根结点。
void InOrder(BTNode* root) //中序遍历
{
if (root)
{
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right)；
}
}
void PostOrder(BTNode* root) //后序遍历
{
if (root)
{
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
}二、二叉树结点个数以及高度等
int BinaryTreeSize(BTNode* root);// 二叉树节点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树叶子节点个数
int BinaryTreeHeight(BTNode* root);//求二叉树高度
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树第k层节点个数
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树查找值为x的节点
????????经过前面对遍历算法的实现，我们发现，二叉树的问题可以使用递归思想解决。
1.二叉树结点个数：
????????二叉树的结点个数就等于根结点个数（1）加上其左右子树的节点个数。
int BinaryTreeSize(BTNode* root)
{
if (NULL==root)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}2.二叉树的叶子结点个数
????????自身下面不再链接有结点的结点叫做叶子结点，即度为0的结点；同样我们可以把问题分解成
：二叉树的叶子结点数就等于二叉树的左右子树的叶子结点数之和。
int BinaryTreeLeafSize(BTNode* root) {
if (NULL==root)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}3.求二叉树的高度；
????????相同的递归思想：二叉树的高度等于其左右子树中更高的子树的高度加1。
int BinaryTreeHeight(BTNode* root)
{
if (root==NULL)
{
return 0;
}
int leftheight = BinaryTreeHeight(root->left);
int rightheight = BinaryTreeHeight(root->right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}4.二叉树第k层结点的个数
????????首先，k不能小于等于0，其次，我们可以将问题分解为求二叉树子树的第k-1层的结点个数。
当k==1时，相当于求子树的根节点有几个，直接返回1；
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (k<=0||NULL==root)
{
return 0;
}
if (k==1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}5.寻找二叉树内值为x的结点。
????????依旧是递归思想，寻找二叉树内值为x的结点也就是看根节点是否是值为x的结点和查找子树中有无值为x的结点；
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
BTNode* ret = NULL;
if (NULL == root)
{
return NULL;
}
if(root->data==x)
{
return root;
}
//ret= BinaryTreeFind(root->left,x);
if (ret = BinaryTreeFind(root->left, x))
{
return ret;
}
return BinaryTreeFind(root->right, x);
}????????先找根结点是否值为x，再找左子树中有无值为x的结点，如果没有返回NULL；最后找右子树中有无值为x的结点。
三、二叉树的创建和销毁
????????经过前面对二叉树的各项操作，相信大家已经较为充分的理解了二叉树的结构。下面我们来看看究竟如何创建一个二叉树。
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi, int size);
//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* buyBtNode(BTDataType);//创建一个结点
void BinaryTreeDestory(BTNode** root);// 二叉树销毁
1.创建二叉树。
????????我们可以尝试按照前序遍历的顺序创建一个二叉树；首先可以让用户提供一个数组。
int a[]={1,2,3,4,5,6};
????????我们按前序遍历尝试创建二叉树，先写一个创建新结点的函数；
BTNode* buyBtNode(BTDataType x)//创建一个结点
{
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode==NULL)
{
assert(0);
return NULL;
}
newNode->data = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}????????创建一个二叉树就相当于创建一个根节点，再创建他的左右子树；
BTNode* BinaryTreeCreate(BTDataType* a,int* pi,int size)
{
if (size>*pi)
{
BTNode* newNode = buyBtNode(a[*pi]);
(*pi)++;
newNode->left = BinaryTreeCreate(a,pi,size);
(*pi)++;
newNode->right = BinaryTreeCreate(a,pi,size);
return newNode;
}
return NULL;
}此时我们发现，他会一直创建左子树，如图：
经过调试发现，我们的程序无法分辨叶子结点；此时我们可以使用一个特殊的值来表示NULL
?????????此时用户需要给程序的序列是：
int a[] = { 1,2,3,-1,-1,-1,4,5,-1,-1,6 };????????此时需要给函数多传一个参数，来告诉程序用户用哪个值代替NULL的位置；当a[*pi]==n时，返回NULL；
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi,int size)
{
if (size>*pi&&a[*pi]!=n)
{
BTNode* newNode = buyBtNode(a[*pi]);
(*pi)++;
newNode->left = BinaryTreeCreate(a, n, pi,size);
(*pi)++;
newNode->right = BinaryTreeCreate(a, n, pi,size);
return newNode;
}
return NULL;
}????????这样我们就成功创建了一个二叉树。
2.二叉树的销毁
????????我们的二叉树是使用malloc函数创建再堆上的，如果不手动释放，就会造成内存泄漏。二叉树的销毁与创建有一点不同，由于我们的二叉树是使用二叉链表创建，结点与结点之间由指针连接，如果先free根结点，我们就找不到子结点了，所以我们释放内存时，应该先释放左右子树的空间，再释放根节点的空间。
void BinaryTreeDestory(BTNode** root)
{
if (NULL==*root)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}?????????传二级指针的原因：我们创建二叉树时，创建了一个指针变量指向这个在堆上的二叉树，当释放完空间时，这个指针就变成野指针了。
测试程序：
int main()
{
int a[] = { 1,2,3,-1,-1,-1,4,5,-1,-1,6 };
int pi = 0;
BTNode* Node=BinaryTreeCreate(a,-1,&pi,sizeof(a)/sizeof(a[0]));
PreOrder(Node);//123456
printf("\n");
InOrder(Node);//321546
printf("\n");
PostOrder(Node);//325641
printf("\n");
printf("%d \n",BinaryTreeSize(Node));//6
printf("%d \n", BinaryTreeLeafSize(Node));//3
printf("%d \n", BinaryTreeLevelKSize(Node,2));//2
printf("%d\n",BinaryTreeFind(Node,6)->data);//6
BinaryTreeDestory(&Node);
return 0;
}