1. 二叉树的遍历
前面的章节中，我们学习了二叉树的顺序结构，二叉树除了顺序结构，还有链式结构，在学链式结构之前，要求深入掌握二叉树的结构，下面我们先来手动快速的创建一个简单的二叉树，方便学习，后面再来研究二叉树的真正创建的方式。
#include<stdio.h> #include<stdlib.h> #include<assert.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) { perror("malloc fail\n"); return NULL; } node->left = NULL; node->right = NULL; node->data = x; 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; }
下图就是我们上述代码创建的二叉树，从今天开始，我们看到二叉树要将其分为三个部分：根、左子树、右子树。
图中每个子树也能再分为根和左子树、右子树，直到不能再分为止。
而二叉树的遍历分为：前序、中序、后序、层序。今天先来学习前中后序，层序后面再学。
1.1 前序
前序要求的访问次序：根、左子树、右子树。
按照前序的访问规则，对上述代码的节点的访问次序依次是: 1 2 3 null null null 4 5 null null 6 null null。
先访问根节点1，然后访问它的左子树，左子树中先访问根节点2，然后访问2的左子树3，3的左右子树是null null，然后继续访问2的右子树为null，接着访问1的右子树，右子树中先访问根节点4，然后访问4的左子树5，再访问5的左右子树null null，接着访问4的右子树6,6的左右子树是null null，所以最终的访问次序是：1 2 3 null null null 4 5 null null 6 null null
前序的代码实现：
//前序 void PrevOrder(BTNode* root) { if (root==NULL) { printf("null "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } int main() { BTNode* root = CreatBinaryTree(); PrevOrder(root); printf("\n"); return 0; }
打印结果：
递归过程如下：
递归调用的过程实际就是函数栈帧的创建与销毁的过程，每次调用完左子树，它的栈帧就销毁了，调用右子树时会共用左子树的栈帧。
1.2 中序
中序要求的访问次序：左子树、根、右子树。
按照中序的访问规则，对上述代码中的节点的访问次序依次是：null 3 null 2 null 1 null 5 null 4 null 6 null。
因为每个子树都可以被拆成左子树、根和右子树，而且在访问时左子树的优先级高，左子树可以一直分到3，所以从3的左子树开始访问：null 3 null，然后把null 3 null作为2的左子树，再访问2和2的右子树：null 3 null 2 null，接着把 null 3 null 2 null 作为1的左子树，访问1和1的右子树......，最终访问的次序应该是：null 3 null 2 null 1 null 5 null 4 null 6 null。
中序代码实现：
//中序 void InOrder(BTNode* root) { if (root == NULL) { printf("null "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } int main() { BTNode* root = CreatBinaryTree(); //前序 PrevOrder(root); printf("\n"); //中序 InOrder(root); printf("\n"); return 0; }
运行结果：
1.3 后序
后序要求的访问次序：左子树、右子树、根。
按照后序的访问规则，对上述代码中的节点的访问次序依次是：null null 3 null 2 null null 5 null null 6 4 1。 与分析前序和中序一样，这里不再详解。
后序代码实现:
//后序 void PostOrder(BTNode* root) { if (root == NULL) { printf("null "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } int main() { BTNode* root = CreatBinaryTree(); //前序 PrevOrder(root); printf("\n"); //中序 InOrder(root); printf("\n"); //后序 PostOrder(root); printf("\n"); return 0; }
运行结果：
以上就是二叉树的前、中、后序遍历了，这几种方式其实就是对根的访问的先后问题，如果上述内容还不是很明白，最好画一下递归调用图，这样就很清楚了。
1.4 遍历的复杂度
时间复杂度：O(N)，因为二叉树一共有N个节点，递归一共调用N次，所以时间复杂度是O(N)。
空间复杂度：O(h),h的范围是：[ logN, N ]
为什么空间复杂度是这样的呢？
我们前面的章节中讲过，时间是一去不复返的，所以时间要累加计算，而空间是可以共用的，所以空间不能累加计算。我们在调用函数时，左子树调用完，它的栈帧会销毁，而调用右子树时，它会共用左子树的栈帧，而假设二叉树有N个节点，当它是满二叉树时，由于左右子树共用一个空间，只需创建空间logN次，而如果二叉树像下图中的情况，它就要创建空间N次，所以空间复杂度是:O(logN~N)
2.二叉树节点个数及高度的计算
2.1 二叉树节点个数
法一：
要计算二叉树节点个数，我们只需要将二叉树遍历一遍(前、中、后序都可以），每次调用时使size++即可，注意size要定义为全局变量，防止每次调用的时候size被置为0
代码如下：
//二叉树节点个数 int size = 0; int BTreeSize(BTNode* root) { if (root == NULL) { return; } size++; BTreeSize(root->left); BTreeSize(root->right); } int main() { BTNode* root = CreatBinaryTree(); BTreeSize(root); printf("BTreeSize:%d\n", size); return 0; }
法二：
把计算节点个数分为，左子树节点个数+右子树节点个数+根节点个数，而每个子树还能分为左子树、右子树和根，所以我们使用递归的思想，如果根节点不为空，就分别计算它的左右子树节点个数+它自身，如果为空，就返回0。
代码如下：
//二叉树节点个数 int BTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BTreeSize(root->left) + BTreeSize(root->right)+1; } int main() { BTNode* root = CreatBinaryTree(); printf("BTreeSize:%d\n", BTreeSize(root)); return 0; }
运行结果：
2.2 二叉树叶子节点的个数
要计算叶子节点，也可以使用上述分开计算的方法，分别计算左子树和右子树的叶子节点个数，然后相加，递归的条件是：如果左子树和右子树的节点都是NULL，那说明是叶子节点，返回1，否则，说明是分支节点，继续往下递归。
代码如下：
//二叉树叶子节点 int BLeafNum(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1 ; } return BLeafNum(root->left) + BLeafNum(root->right); } int main() { BTNode* root = CreatBinaryTree(); printf("BLeafNum:%d\n", BLeafNum(root)); return 0; }
运行结果：
2.3 二叉树高度
求二叉树高度，也可以分别求左子树和右子树的高度，然后比较大小，返回大的值，并将该值加一就是二叉树的高度，加一是因为左右子树距离根节点还有一层。
求左右子树的高度可以再分解为上面的步骤，所以使用递归解决问题。
代码如下：
//二叉树高度 int BTreeHeight(BTNode* root) { if (root == NULL) { return 0; } int LeftNum = BTreeHeight(root->left); int RightNum = BTreeHeight(root->right); return LeftNum > RightNum ? LeftNum + 1 : RightNum + 1; } int main() { BTNode* root = CreatBinaryTree(); printf(" BTreeHeight:%d\n", BTreeHeight(root)); return 0; }
运行结果：
2.4 二叉树第k层节点个数
该问题可以转换成：分别求左子树的第k-1层和右子树的第k-1层，然后返回它们的和。
结束条件是：k==1 且k不为空。
比如我们要求1的第三层，就是求2和4的第二层，也就是求3 5 6的第一层
代码如下：
//二叉树第k层节点的个数 int BTreekNum(BTNode* root,int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BTreekNum(root->left, k - 1) + BTreekNum(root->right, k - 1); } int main() { BTNode* root = CreatBinaryTree(); printf("BTreekNum:%d\n", BTreekNum(root,3)); printf("BTreekNum:%d\n", BTreekNum(root, 2)); return 0; }
运行结果：
递归过程如下：
通过以上计算，相信我们对二叉树的遍历有了更深的理解，同时也加深了对递归的理解，其实当我们熟练运用递归之后，递归问题都可以分两步解决：1. 找出子问题 2. 递归条件。
以上就是今天学习的所有内容了，未完待续。。。
