二叉树的遍历
二叉树的遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历(preorder traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(inorder traversal)——访问根结点的操作发生在遍历其左右子树之间。
3. 后序遍历(postorder traversal)——访问根结点的操作发生在遍历其左右子树之后。
以下面二叉树为例，进行先序，中序，后序遍历：
先序
分析：从根节点开始，先访问根，再访问左子树（左子树中先访问根节点，在访问左子树和右子 树），最后访问右子树（先访问根节点，在访问左子树和右子树）
访问顺序：
先访问树tree根1，再访问tree左子树l1:
访问l1根2，再访问其左子树ll2:
访问ll2根3，再访问其左子树：左子树为空，访问其右子树，右子树为空，返回上一个子树l1；
此时l1左子树访问完毕，访问l1右子树null，为空返回上一个树tree;
此时tree根和左子树访问完毕，访问tree右子树r1:
访问r1根4，再访问r1左子树rl1:
访问rl1根5，再访问rl1左子树和右子树null，返回上一个树r1；
此时，r1左子树rl1访问完毕，接着访问r1右子树rr1：
访问rr1根6，再访问rr1左右子树null，返回上一个树r1；
此时r1根和左右子树访问完毕，返回上一个树tree；
此时tree的根和左子树访问完毕，及整个树访问完毕。
图示：
中序
分析：即先访问左子树，左子树访问完毕后再访问根节点，根节点访问完后，最后访问右子树。左子树和右子树中也是先访问左子树，再根，最后右子树。
访问顺序：
从tree根开始，先访问其左子树l1：
左子树l1不为空，访问l1左子树ll2：
左子树ll2不为空，访问ll2左子树：
左子树为空，访问ll2根3，再访问ll2的右节点，右节点为空，返回子树l1；
子树l1的左子树访问完毕，访问l1的根2，再访问l1的右子树，为空，返回树tree；
tree的左子树访问完毕，访问tree根1，接着访问tree右子树r1：
右子树r1不为空，访问r1左子树rl1：
rl1不为空，访问rl1左子树，左子树为空，访问rl1根5，再访问其右子树：
右子树为空，返回上一个树r1；
r1左子树访问完毕，访问其根4，接着访问其右子树rr1：
rr1不为空，访问其左子树，左子树为空，访问rr1根6，再访问其右子树为空，返回r1；
此时tree的左子树，根，和右子树都访问完毕。
图示：
后序
分析：先访问左子树（左子树中也是左子树，右子树，根），再访问右子树（右子树中也是左子树，右子树，根），最后访问根节点。
访问顺序：
先访问tree，不为空，访问其左子树l1，l1不为空，访问其左子树ll2；
ll2不为空，访问其左子树，为空；访问其右子树，为空；访问其根3，返回上一个树l1；
l1左子树访问完毕，访问其右子树，为空；访问其根2，返回上一个树tree；
tree的左子树访问完毕，访问其右子树r1，r1不为空，访问其左子树rl1；
rl1不为空，访问其左子树，为空；访问其右子树，为空，访问其根5，返回上一个树r1；
r1左子树访问完毕，访问其右子树rr1，rr1不为空，访问其左子树；
rr1左子树为空，访问其右子树，为空，访问其根6，返回上一个树r1；
此时r1左子树右子树访问完毕，访问其根4，放回上一个树tree；
此时tree的左右子树访问完毕，访问其根1；整个树访问完毕。
图示：
不难发现，上述遍历时中途总会返回上一层树，已经用到了递归思想，这里我们手动实现一个简单的链式二叉树，完成我们的前序，中序，后序的遍历。
定义
定义每个节点由数据，左子树地址和右子树地址组成
typedef int btdatatype;
typedef struct binarytreenode
{
btdatatype data; //数据
struct binarytreenode* left; //左子树地址
struct binarytreenode* right; //右子树地址
}btnode;创建节点
将固定的数据放入创建的节点中，左右子树指针置空
btnode* buynode(btdatatype x)
{
btnode* root = (btnode*)malloc(sizeof(btnode));
root->data = x;
root->left = null;
root->right = null;
return root;
}创建二叉树
手动创建节点，并将左右子树指针指向固定的位置，以上述二叉树为例：
//手动创建
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)
{
if (root==null)
{
return;
}
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}中序遍历
// 二叉树中序遍历
void inorder(btnode* root)
{
if (root == null)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}后序遍历
// 二叉树后序遍历
void postorder(btnode* root)
{
if (root == null)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}求二叉树节点树
方法一：前序中序后序时添加一个计数变量（变量为全局或者静态，防止递归时计数重置）
缺点：重复调用时计数会累加，每次调用时须将count重新置0；
//定义全局或者静态变量 //多次调用会累加 int count = 0; int btreesize(btnode* root) { if (root == null) return; count; btreesize(root->left); btreesize(root->right); return count; }方法二：遍历 计数（遍历时将遍历地址传过去）
//遍历 计数 //将变量地址传过去，计数---思想最优 void btreesize(btnode* root,int* count) { if (root == null) return; (*count); btreesize(root->left,count); btreesize(root->right,count); }方法三：递归--分治思想
当根为空时，返回0，左子树节点个数 右子树节点个数 1（根节点本身）
//递归--分治思想--节点个数 int btreesize(btnode* root) { return root == null ? 0 : btreesize(root->left) btreesize(root->right) 1; }
求二叉树叶子节点个数
二叉树叶子节点数 = 左子树叶子节点数 右子树节点数
叶子节点：左子树和右子树为空的节点
//叶子节点个数 int btreeleafsize(btnode* root) { if (root==null) { return 0; } if (root->left == null&&root->right==null) { return 1; } return btreeleafsize(root->left) btreeleafsize(root->right); }
第k层节点数
求tree的第三层节点数
即l1和r1的第二层节点数之和
即ll1、rl1和rr1第一层节点数之和
当k=1时，返回1即可
//第k层节点个数 int btreelevesize(btnode* root,int k) { assert(k>=1); if (root==null) { return 0; } if (k == 1) { return 1; } return btreelevesize(root->left, k - 1) btreelevesize(root->right, k - 1);
二叉树深度
二叉树的深度 = 左子树和右子树中最大深度度 1
需要比较左右子树高度，判断返回哪一个
//二叉树深度 int btreedepth(btnode* root) { if (root==null) { return 0; } int leftdepth = btreedepth(root->left); int rightdepth = btreedepth(root->right); return leftdepth >rightdepth ? leftdepth 1 : rightdepth 1; }
二叉树查找值为x的节点
判断根是否为要找的节点，是则返回节点地址
不是则进左子树中去找，找到返回节点地址，找不到返回空
再进右子树取找，找到返回节点地址，找不到返回空
// 二叉树查找值为x的节点 btnode* binarytreefind(btnode* root, btdatatype x) { if (root==null) { return null; } if (root->data == x) return root; if (binarytreefind(root->left, x)) return binarytreefind(root->left,x); if (binarytreefind(root->right, x)) return binarytreefind(root->right, x); return null; }