二叉树的遍历
二叉树的遍历有：前序/中序/后序的递归结构遍历：
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；整个树访问完毕。
图示：
手动构建链式二叉树
不难发现，上述遍历时中途总会返回上一层树，已经用到了递归思想，这里我们手动实现一个简单的链式二叉树，完成我们的前序，中序，后序的遍历。
定义
定义每个节点由数据，左子树地址和右子树地址组成
1 typedef int BTDataType;
2 typedef struct BinaryTreeNode
3 {
4 BTDataType data; //数据
5 struct BinaryTreeNode* left; //左子树地址
6 struct BinaryTreeNode* right; //右子树地址
7 }BTNode;
创建节点
将固定的数据放入创建的节点中，左右子树指针置空
1 BTNode* BuyNode(BTDataType x)
2 {
3 BTNode* root = (BTNode*)malloc(sizeof(BTNode));
4 root->data = x;
5 root->left = NULL;
6 root->right = NULL;
7 return root;
8 }
创建二叉树
手动创建节点，并将左右子树指针指向固定的位置，以上述二叉树为例：
1 //手动创建
2 BTNode* CreatBinaryTree()
3 {
4 BTNode* node1 = BuyNode(1);
5 BTNode* node2 = BuyNode(2);
6 BTNode* node3 = BuyNode(3);
7 BTNode* node4 = BuyNode(4);
8 BTNode* node5 = BuyNode(5);
9 BTNode* node6 = BuyNode(6);
10 node1->left = node2;
11 node1->right = node4;
12 node2->left = node3;
13 node4->left = node5;
14 node4->right = node6;
15 return node1;
16 }
前序遍历
依照我们对前序遍历的顺序分析：根，左子树，右子树，编写前序代码：
// 二叉树前序遍历
1 void PreOrder(BTNode* root)
2 {
3 if (root==NULL)
4 {
5 return;
6 }
7 printf("%d ",root->data);
8 PreOrder(root->left);
9 PreOrder(root->right);
10 }
中序遍历
// 二叉树中序遍历
1 void InOrder(BTNode* root)
2 {
3 if (root == NULL)
4 {
5 return;
6 }
7 InOrder(root->left);
8 printf("%d ", root->data);
9 InOrder(root->right);
10 }
后序遍历
// 二叉树后序遍历
1 void PostOrder(BTNode* root)
2 {
3 if (root == NULL)
4 {
5 return;
6 }
7 PostOrder(root->left);
8 PostOrder(root->right);
9 printf("%d ", root->data);
10
11 }
标签：左子,遍历,R1,右子,访问,二叉树,root From： https://www.cnblogs.com/suishou/p/16872928.html