二叉树及其四大遍历
1.树和二叉树的简介
二叉树是树中较为特殊的一种，二叉树中每个结点最多只有2个孩子结点，这种特殊性 让我们操作起来更为简单，但是二叉树在某些场景仍然无法满足要求，这时候就需要引入多叉树，但是掌握二叉树是学习多叉树的前提，所以掌握二叉树的 基本思想、常见操作、解决问题的用法是很重要的。
2.二叉树的存储
任何数据结构都是建立在物理存储和逻辑关系上的，进一步说任何数据结构根据其逻辑关系在物理内存的存储只能是顺序存储和链式存储两种形式。
顺序存储
采用顺序存储时逻辑上存在前驱/后继/兄弟关系的结点在物理内存的位置上也是连续或者索引存在确定关系的，因为我们是从物理存储的地址或者讲是下标索引来 确定其逻辑关系的。
由于结点的序号可以唯一地给出结点之间的关系，因此对于满二叉树、完全二叉树这种形式的度为2的结点数量占比较高，适合采用顺序存储；对于普通的二叉树 或者右单支树而言采用顺序存储就会很浪费空间，因为虽然二叉树没有对应的结点，为了用物理位置表示逻辑关系，还需要为空结点分配空间。
链式存储
因此我们可以在每个结点中增加父结点指针、左右孩子结点指针、兄弟结点指针来实现结点之间逻辑关系的表示。但是从实际是使用中太多的指针会造成操作上的复杂 一般对每个结点是保留了其左右孩子结点，如果需要获取其父节点或者兄弟结点时，可以在遍过程中借助于栈、队列等完成对其他结点的寻找。
结点表示
//顺序存储二叉树表示 #define MaxSize 100typedef char DataType;typedef struct SeqBTree{ DataType array[MaxSize]; int btnodecnt;}//链式存储二叉树结点表示 typedef struct BTreeNode{ DataType data; BTreeNode *left; BTreeNode *right;}BTreeNode,*BTree;3.二叉树的遍历
所谓二叉树的遍历是指我们可以从某个结点出发走遍二叉树上的所有结点的过程，二叉树的遍历并非前中后、层次这四种遍历。
前序遍历
class Solution {public: vector<int> preorderTraversal(TreeNode* root) { //递归实现 vector<int> prelist; vector<int> tmp; vector<int>::iterator it; if(root!=NULL) { prelist.push_back(root->val); tmp=preorderTraversal(root->left); for(it=tmp.begin();it!=tmp.end();it++) { prelist.push_back(*it); } tmp=preorderTraversal(root->right); for(it=tmp.begin();it!=tmp.end();it++) { prelist.push_back(*it); } } return prelist; }};
class Solution {public: vector<int> preorderTraversal(TreeNode* root) { //非递归实现 std::stack<TreeNode *> s; std::vector<int> prelist;
if(root==NULL) return prelist; s.push(root); while(!s.empty()){ root=s.top(); s.pop(); prelist.push_back(root->val); if(root!=NULL){ if(root->right!=NULL) s.push(root->right); if(root->left!=NULL) s.push(root->left); } } return prelist; }};根结点先入栈，出根结点并访问根结点的值（这里的根并非整棵树的根，而是递归意义上的树的根）;
判断其右孩子是否为空，如果不为空则右孩子入栈;
判断其左孩子是否为空，如果不为空则左孩子入栈；
重复上述操作
中序遍历
class Solution {public: //递归实现 void findnode(TreeNode *root,vector<int> &nodes){ if(!root) return; findnode(root->left,nodes); nodes.push_back(root->val); findnode(root->right,nodes); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; if(!root) return res; findnode(root,res); return res; }};
class Solution {public: //非递归解法 vector<int> inorderTraversal(TreeNode * root) { std::stack<TreeNode *> s; std::vector<int> inorderlist; if(root==NULL) return inorderlist; while(!s.empty()||root!=NULL){ while(root!=NULL){ s.push(root); root=root->left; } if(!s.empty()){ root=s.top(); s.pop(); inorderlist.push_back(root->val); root=root->right; } } }};根结点先入栈,判断根结点的左孩子是否为空，如果不为空则左孩子入栈，并不断指向左孩子，入栈，直至左孩子结点为空;
弹出栈顶元素并访问该元素，并判断弹出的结点的右孩子是否为空，如果不为空则右孩子入栈，并不断指向右孩子，直至右孩子为空;
重复上述操作
后序遍历
class Solution {public: //递归解法 std::vector<int> postlist; vector<int> postorderTraversal(TreeNode * root) { // write your code here if(root!=NULL) { postorderTraversal(root->left); postorderTraversal(root->right); postlist.push_back(root->val); } return postlist; }};
class Solution {public: vector<int> postorderTraversal(TreeNode* root) { //非递归实现 vector<int> res; if(root == NULL) return res;
TreeNode *p = root; stack<TreeNode *> sta; TreeNode *last = root; sta.push(p); while (!sta.empty()) { p = sta.top(); //p为叶子结点||p的右孩子为空且左孩子被访问过了 //||p的右孩子已经被访问了 if( (p->left == NULL && p->right == NULL) || (p->right == NULL && last == p->left) || (last == p->right) ) { res.push_back(p->val); last = p; sta.pop(); } else { if(p->right) sta.push(p->right); if(p->left) sta.push(p->left); } } return res; }};根结点先入栈
判断栈顶结点的类型，如果结点是叶子结点那么直接输出；
判断栈顶结点的类型，如果结点是有孩子结点且孩子结点没有被访问过，则按照右孩子、左孩子的顺序入栈；
判断栈顶结点的类型，如果结点有孩子且孩子均被访问了，则该结点访问输出
重复上述操作
后序遍历的其他实现
void PostOrderNoRecursion(Node *node, stack<Node *>&sta) { while (!sta.empty()) { while (node->lChild != NULL) { sta.push(node->lChild); node = node->lChild; } Node *temp = sta.top(); if (temp->rChild == NULL || temp->rChild->isVisited == true) { cout << temp->data << " "; temp->isVisited = true; sta.pop(); } else if(temp->rChild != NULL && temp->isVisited == false) { sta.push(temp->rChild); node = temp->rChild; } } }节点的结构体中再加入一个参数isVisited,表示某个节点是否被访问过；
首先根节点入栈，然后判断左孩子是否为空，若不为空，则左孩子入栈，并移动node到左孩子，直到左孩子为空；
判断栈顶元素，如果栈顶元素没有右孩子或者右孩子已经被访问过，那么就访问该栈顶元素，并出栈；
如果栈顶元素有右孩子并且右孩子没有被访问过，那么把右孩子入栈，把node指针指向右孩子。
层次遍历
class Solution {public: //非递归实现 vector<vector<int> > levelOrder(TreeNode* root) { std::vector<vector<int> > v; std::queue<TreeNode *> q; if(root==NULL) return v; q.push(root); int len =1; while(!q.empty()) { std::vector<int> s; len=q.size(); while(len--) { TreeNode* tmp = q.front(); s.push_back(tmp->val); q.pop(); if(tmp->left) q.push(tmp->left); if(tmp->right) q.push(tmp->right); } v.push_back(s); } return v; }};根结点为空直接返回；
根结点不为空，将根结点入队，判断队列是否为空，如果队列非空则队首结点出队并访问输出，与此同时判断其左右孩子结点是否为空，如果不为空按照 先左后右的顺序入队；
重复上述步骤；
4.参考资料
https://blog.csdn.net/chenyufeng1991/article/details/52727467
https://www.cnblogs.com/rain-lei/p/3705680.html
5.往期精彩
理解Redis持久化
Linux中的各种锁及其基本原理
浅析CPython的全局解释锁GIL
浅谈Linux下Socket选项设置
深入理解IO复用之epoll