目录
1.二叉树链式结构的实现
2.二叉树的遍历
前序遍历（根，左，右）
中序遍历（左，根，右）
后序遍历（左，右，根）
3.二叉树节点个数
1.遍历计数方法
2.分而治之
4.二叉树叶子节点个数
5.二叉树的高度
6.二叉树第k层节点个数
7.二叉树查找值为x的节点
1.二叉树链式结构的实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
printf("malloc fail");
return NULL;
}
node->_data = x;
node->_left = NULL;
node->_right = NULL;
return node;
}
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;
}
参照这个图写的上面的代码
2.二叉树的遍历
前序遍历（根，左，右）
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->_data);//根
PreOrder(root->_left);//左
PreOrder(root->_right);//右
}
int main()
{
BTNode* root = CreatBinaryTree();
PreOrder(root);
printf("\n");
return 0；
}中序遍历（左，根，右）
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->_left);//左
printf("%d ", root->_data);//根
InOrder(root->_right);//右
}
int main()
{
BTNode* root = CreatBinaryTree();
InOrder(root);
printf("\n");
return 0；
}后序遍历（左，右，根）
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->_left);//左
printf("%d ", root->_data);//根
PostOrder(root->_right);//右
}
int main()
{
BTNode* root = CreatBinaryTree();
PostOrder(root);
printf("\n");
return 0；
}
下面中序遍历示意图，帮助大家理解（掌握递归的思想）
递归的本质是创立栈帧，回退就是销毁栈帧
3.二叉树节点个数
这个二叉树一共有6个结点，我们应该如何求呢
1.遍历计数方法
二叉树节点个数
方法1：计数思想
int size = 0;
void BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return;
size++;
BinaryTreeSize(root->_left);
BinaryTreeSize(root->_right);
}
int main()
{
BTNode* root = CreatBinaryTree();
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", size);
//全局变量要置为0
size = 0;
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", size);
size = 0;
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", size);
return 0;
}
2.分而治之
//方法2 分而治之，左树加右数加自己
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
int main()
{
BTNode* root = CreatBinaryTree();
//第二种方法
printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
return 0;
}
4.二叉树叶子节点个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
//判断叶子结点，度为0，就返回
if (root->_left == NULL && root->_right == NULL)
{
return 1;
}
//剩下的是分支结点，度不为0的
return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
return 0;
} 
5.二叉树的高度
一种后序思想，先算左边最高的，再算右边最高的，最后算我，汇集一下
//求二叉树的高度
int BinaryTreeLeafHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftheight = BinaryTreeLeafHeight(root->_left);
int rightheight = BinaryTreeLeafHeight(root->_right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
//加一是加自己的高度
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeLeafHeight:%d\n", BinaryTreeLeafHeight(root));
return 0;
}
6.二叉树第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0); //没有第0层
if (root == NULL) //空树返回0
return 0;
if (k == 1)
return 1; //不是空树，且k为1，返回1，第一层是1个
return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);
}
int main()
{
BTNode* root = CreatBinaryTree();
//求第二层和第三层
printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root,2));
printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root,3));
return 0;
}
7.二叉树查找值为x的节点
