二叉树及其四大遍历
二叉树及其四大遍历
后端技术指南针 后端技术指南针
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;上面定义了顺序存储的树的表示和链式存储时结点的表示，在链式存储定义结点时使用typedef定义了结点类型和结点指针类型，从而简化书写。
3.二叉树的遍历
所谓二叉树的遍历是指我们可以从某个结点出发走遍二叉树上的所有结点的过程，二叉树的遍历并非前中后、层次这四种遍历。
相反二叉树可以遍历的种类数 与结点数n有关系，中间涉及到卡特兰数等知识，但是大部分的遍历是无规律可循的，其中前序、中序、后序、层次遍历从深度和广度两个角度出发 对二叉树进行遍历，因此其中有很强的规律可以遵循，因此我们常说的二叉树的遍历多指上面的4种有规律的遍历，但是绝不是说二叉树只有4种遍历。
图为：leetcode官网搜索遍历获得的题目，可以看到还有其他多种遍历以及N叉树，因此二叉树的前中后层4种遍历只是最基本的。
由于树的定义就是递归，因此我们在遍历二叉树时多借助于递归，但是由于递归在系统实现时借助大量的堆栈操作来保留函数执行的现场，如果在数据量很大 的时候递归遍历可能或造成堆栈溢出、从时间角度来说递归遍历相比非递归遍历耗时更多，因此对于数据量较大并且时间要求较高的场合应该选择非递归实现。
以下前中后层次4种遍历的递归非递归实现代码均由笔者在leetcode运行通过，内存和耗时不算最优也还凑合。
前序遍历
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