二叉树前，中，后序遍历

-前言

树是一种常用的数据结构，用来模拟具有树状结构性质的数据集合。树里的每一个节点（结构体）有一个值和一个包含所有子节点的列表。二叉树则是更典型的树结构，每个结点最多有两个子节点。接下来记录二叉树的三种遍历方法。

-中序遍历

什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。这里先讲中序排序，是因为中序排序与后序排序的迭代法思路较为类似，相对好理解一点，而前序遍历比较不同，放在最后说。

- 以上图这个树来说，中序遍历的结果应该是DBEAFCG-

递归法

树的遍历思路显然可以用递归来实现。递归的出口为结点空，先记录当前节点的数据，再先遍历root->left后遍历root->right即可。递归较容易理解

void inorder(struct TreeNode* root, int* res, int* returnSize){
	if(root == NULL){
		return;
	}
	inorder(root->left, res, returnSize);
	res[(*returnSize)++] = root->val;
	inorder(root->right, res, returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	inorder(root, res, returnSize);
	return res;
}

迭代法

迭代法与递归的原理很相似，都是用了栈的思想（入栈出栈），递归的栈是暗含的，迭代就是直接使用一个栈帮助遍历。迭代法个人感觉较难理解，学习的时候最好能自己动手在纸上模拟一下过程。

int* inorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode** Node = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 501);
	//struct TreeNode* Node[500];
	int top;
	while(root != NULL || top != 0){
		while(root != NULL){
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		res[(*returnSize)++] = root->val;
		root = root->right;
	}
	return res;
}

​

-后序遍历

什么是二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树。

- 以上​​​​​​​图这个树来说，后序遍历的结果应该是DEBFGCA-

递归法

递归法大部分代码与中序相同，唯一不同的在于递归函数里记录数据的先后顺序

    postorder(root->left, res, returnSize);
	postorder(root->right, res, returnSize);
	res[(*returnSize)++] = root->val;

迭代法

后序遍历的迭代法与中序的迭代法思路大致相同，不同在于出栈之后要考虑右子树是否为空，不为空的话需要把出栈的数值再入栈，不记录数据，且从右子树开始继续遍历直到遇到右子树为空停止。设置prev结点的用途是在开始记录右子树的数据时标记记录过的结点，帮助后续出栈的进行。

int* postorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode* Node[500];
	struct TreeNode* prev = NULL;
	int top = 0;
	while(root != NULL || top != 0){
		while(root != NULL){
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		if(root->right == NULL || root->right == prev){
			res[(*returnSize)++] = root->val;
			prev = root;
			root = NULL;
		}
		else{
			Node[top++] = root;
			root = root->right;
		}
	}
	return res;
}

-前序遍历

什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树。

- 以上​​​​​​​图这个树来说，前序遍历的结果应该是ABDECFG-

递归法

代码大部分与中序相同，不同之处在于：

    res[(*returnSize)++] = root->val;
	preorder(root->left, res, returnSize);
	preorder(root->right, res, returnSize);

迭代法

前序排序的迭代法不同在于入栈时就存储数据，具体代码如下。

int* preorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode* Node[500];
	int top = 0;
	while(root != NULL || top != 0){
		while(root != NULL){
			res[(*returnSize)++] = root->val;
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		root = root->right;
	}
	retuen res;
}