一、二叉树的遍历原理
1.1原理：
二叉树的遍历（traveing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使每个结点都被访问一次，且仅被访问一次。
这里有两个关键词：访问和次序。
1.2.1访问
访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
1.2.2次序
二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择就像你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由选择方式的不同，遍历的次序就完全不同了。
二、二叉树的前序、中序、后序遍历
2.1二叉树遍历的几种方式
二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：
前序遍历、中序遍历、后序遍历、层次遍历。
这四种遍历方式的基本顺序和在数组中存储的形式如下图所示：
2.2前序遍历
规则是若 叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图遍历的顺序为: ABDGHCEIF
步骤：1、先造一颗树
造树：
#include<stdio.h> #include<stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; malloc一块空间 BTNode* BuyBTNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; }
紧接着实现链接
BTNode* CreatBinaryTree() { BTNode* node1 = BuyBTNode(1); BTNode* node2 = BuyBTNode(2); BTNode* node3 = BuyBTNode(3); BTNode* node4 = BuyBTNode(4); BTNode* node5 = BuyBTNode(5); BTNode* node6 = BuyBTNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
2、写前序遍历和main函数
void PrevOrder(BTNode* root)//前序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left);//左子树 PrevOrder(root->right);//右子树 } int main() { BTNode* tree = CreatBinaryTree(); PrevOrder(tree); return 0; }
程序运行结果 ：（对照1、2、3、4、5、6）上图
2.3中序遍历
规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结 点) ，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树 如图所示， 遍历的顺序为GDHBAELCF.
void InOrder(BTNode* root)//中序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } InOrder(root->left);//先左子树 printf("%d ", root->data); InOrder(root->right);//再右子树 } int main() { BTNode* tree = CreatBinaryTree(); InOrder(tree); return 0; }
程序运行结果
2.4后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点 如图所示 遍历的顺序为 GHDBIEFCA。
void BackOrder(BTNode* root) { if (root == NULL)//如果根是空就return { printf("NULL "); return; } BackOrder(root->left); BackOrder(root->right); printf("%d ", root->data); } int main() { BTNode* tree = CreatBinaryTree(); BackOrder(tree); return 0; }
程序运行结果：
二叉树的遍历的几种路径 （小结）：网上找的图
2.5层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历与之前的三种遍历情况有所不同，层序遍历的实现依赖于队列，会比较麻烦一些。
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root);//先插入根节点 } while (QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q);//把队列里根节点的指针拿出来，但是指针指向的节点的值没有被销毁； printf("%d ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } printf("\n"); } QueueDestry(&q); }
三、二叉树的拓展
3.1计算树的结点的个数
low版（代码比较挫）但是容易理解
int count = 0; void BTreeSize(BTNode* root) { if (root == NULL) return; ++count; BTreeSize(root->left); BTreeSize(root->right); //后序 }
注意：
这里为什么不用static静态变量。
因为静态变量在静态区，是整个程序结束后才销毁，而且局部静态变量不能置零
所以如果再计算下一个树的结点就会和上一个树累加。
static只初始化一次，所以要么就是全局静态变量。
具体的调用方法：//更好的计数方法，既不使用全局，也不使用静态变量-
//思想遍历加计数（传地址调用）指针
void BTreeSize(BTNode* root, int* pCount) { if (root == NULL) return; ++(*pCount);//把一个变量的地址传过去 BTreeSize(root->left, pCount); BTreeSize(root->right, pCount); //后序 }
3.2计算树的叶子结点的个数
思路：叶子结点的左右结点都为空，递归+分治思想
因此：代码如下
int BTreeLaafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return BTreeLaafSize(root->left) + BTreeLaafSize(root->right); }
