聊聊二叉树的遍历（递归和非递归）
二叉树也是常用的数据结构，通过使用二叉树可以快速的对数据进行排序或者查找，在常用的堆排序算法中，堆的底层实质就是一个模拟的完全二叉树！等等，什么是完全二叉树？二叉树又是什么？有哪几类？让我们开始今天的算法课堂～
二叉数的概念和分类
二叉树是每个树节点最多有两个子树的一种特殊的树结构，其有一些内在的性质，比如，若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个节点（i>=0）,高度为k的二叉树最多有2^(k+1)-1个节点（空树的高度为-1）。其类别为以下几种：
- 满二叉树：所有的叶节点全部在底层，并且在底层全部铺满的二叉树
- 完全二叉树：叶节点只能出现在最后两层，并且最底层的叶节点都向左对齐
- 二叉搜索树：要求每个节点本身大于其左子树，而小于其右子树，对其进行中序遍历后，会得到一个有序的列表，这是我们经常用到的一种数的结构
- 平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，并且满足二叉搜索树的规则。
满二叉搜索树
二叉树的遍历
二叉树的遍历有三种方式：先序遍历，中序遍历，后序遍历。思路很简单，这里面说的顺序的序是指每个子树根节点的遍历（打印）顺序。不懂的话可以看上图，红色的点表示该节点打印，下方为遍历得到的打印顺序。
接下来我们以这个图为例进行Coding，用代码来实现这三种遍历方式：
递归版本（先、中、后序）
递归版的遍历算法很简单了，我们只需要改变打印次序就好了，也没有什么可讲的！
// 递归版// 先序遍历void printPreorder1(TreeNode* head){
if (head == nullptr){
return;
}
cout << head->value << " ";
printPreorder1(head->left);
printPreorder1(head->right);}// 中序遍历void printInorder1(TreeNode* head){
if (head == nullptr){
return;
}
printInorder1(head->left);
cout << head->value << " ";
printInorder1(head->right);}// 后序遍历void printPostorder1(TreeNode* head){
if (head == nullptr){
return;
}
printPostorder1(head->left);
printPostorder1(head->right);
cout << head->value << " ";}非递归版本（先、中、后序）
首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！
先序遍历：
我们将数的每个节点压入栈中，由于是先序遍历，首先压入的是根节点，然后弹出（弹出节点时打印信息，且一个循环弹出一个节点），接着是压入右子树节点，最后压入左子树节点。为什么要这样呢？由于堆栈是“先进后出”结构，我们想要先打印左子树，因此最后压入左子树，循环这个过程，就达到了我们的目的。
// 迭代版
void printPreorder2(TreeNode* head){
cout << "Pre Order:" << endl;
if (head != nullptr){
stack<TreeNode*> *sta = new stack<TreeNode*>;
sta->push(head);
TreeNode* cur = head;
while(!sta->empty()){
cur = sta->top();
sta->pop();
cout << cur->value << " ";
if (cur->right != nullptr){
sta->push(cur->right);
}
if (cur->left != nullptr){
sta->push(cur->left); // 先压右边节点，再压左边节点，这与栈的特性有关
}
}
}
cout << endl;
}中序遍历：
中序时，我们首先去遍历二叉树的左分支，并将节点压入栈中，只到找到最左边的叶节点，接着弹出（并打印节点），并看其有没右分支，如果没有，栈再弹出一个节点（根节点），看其有没有右分支。每次弹出，都要观察其是否有右分支，也就是说每个节点都遍历了两次！
void printInorder2(TreeNode* head){
cout << "In Order:" << endl;
if(head != nullptr){
stack<TreeNode*>* sta = new stack<TreeNode*>;
TreeNode* cur = head;
while(!sta->empty() || cur != nullptr){
if(cur != nullptr){
sta->push(cur);
cur = cur->left;
}else{
cur = sta->top();
sta->pop();
cout << cur->value << " ";
cur = cur->right;
}
}
}
cout << endl;
}后序遍历：
后序遍历在意思上和前序遍历相近，而前序遍历的压栈顺序为：根、右、左。那么如果我们使用两个堆栈，第一个压栈顺序为：根、左、右，但是在（先序遍历时）弹出根节点时将根节点压入第二个堆栈，为什么这里压栈顺序要为左右呢？很简单，在第一个堆栈中最后压入右子树，那么右子树会最先压入第二个堆栈，相应的，当第二个堆栈弹出时，右子树会在左子树的后面弹出（先进后出）。注意：根节点是最先被压入第一个栈中的，同时也是最先被压入第二个栈中的！
void printPostorder2(TreeNode* head){
cout << "Post Order:" << endl;
if (head != nullptr){
stack<TreeNode*>* sta1 = new stack<TreeNode*>;
stack<TreeNode*>* sta2 = new stack<TreeNode*>;
TreeNode* cur = head;
sta1->push(cur);
while(!sta1->empty()){
cur = sta1->top();
sta1->pop(); // 弹出的是最晚被压入栈的数据
sta2->push(cur);
if(cur->left != nullptr){
sta1->push(cur->left);
}
if(cur->right != nullptr){
sta1->push(cur->right);
}
}
while(!sta2->empty()){
cur = sta2->top();
sta2->pop();
cout << cur->value << " ";
}
}
cout << endl;
}疑问：测试文件new出的对象，没有delete.
答：由于只是刷题测试，new出的空间释放过于麻烦，只要这个进程关闭（运行结束），操作系统会自动回收不用的内存，所以不用delete也行。但工程上一定不要忘了，不然一直运行会导致内存充满，程序崩溃！