二叉树基础（遍历）

二叉树以数组形式的顺序存储结构

获取节点的双亲

删除二叉树

二叉树遍历

前序遍历（递归）

前序遍历（非递归）

中序遍历（递归）

中序遍历（非递归）

后序遍历（递归）

后序遍历（非递归）

模板

前序遍历迭代法

中序遍历迭代法

后序遍历迭代法

层次遍历

更新后序遍历非递归（更简便理解）

二叉树以数组形式的顺序存储结构

二叉树的数组存储及运算_zhangwang010的博客-CSDN博客_二叉树的数组存储

在整个二叉树当中，最重要的是遍历（遍历的应用）、建树（前中后序层次建树）、搜索

首先是定义二叉树

template <class T> 
struct BinTreeNode{
    T data;
    BinTreeNode<T> *leftChild,*rightChild;
    BinTreeNode():leftChild(NULL),rightChild(NULL){}
    BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL)
        :data(x),leftChild(l),rightChild(r){}
}

获取节点的双亲

template <class T>
BinTreeNode<T> *BinaryTree<T>::
Parent (BinTreeNode <T> *subTree, BinTreeNode <T> *t) {
    if (subTree == NULL) return NULL;
     if (subTree->leftChild == t || subTree->rightChild == t ) 
          return subTree;	//找到, 返回父结点地址
     BinTreeNode <T> *p;
     if ((p = Parent (subTree->leftChild, t)) != NULL)  
          return p;	         //递归在左子树中搜索
     else 
          return Parent (subTree->rightChild, t);
 				         //递归在右子树中搜索
};

删除二叉树

template<class T> 
void BinaryTree<T>::
destroy (BinTreeNode<T> * subTree) {
//私有函数: 删除根为subTree的子树
     if (subTree != NULL) {
          destroy (subTree->leftChild);     //删除左子树
 	      destroy (subTree->rightChild);   //删除右子树
 	      delete subTree; 			 //删除根结点
	 }
};

二叉树遍历

不会吧不会吧，前中后序的遍历还不知道！！？（b站有大把视频）

因为二叉树遍历非常重要，又有两种遍历方式（递归与非递归）

递归难在理解，虽然递归的代码实现很简单，但是千万不能死记硬背，要明白递归机制。

非递归难在代码实现。。。（理解也挺麻烦的），然后我找到一个大佬的博客，写的还不错，推荐看这个遍历之前点开一下这个链接二叉树的三种遍历非递归实现 - aspirant - 博客园 (cnblogs.com)

前序遍历（递归）

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

template <class T>
void BinaryTree<T>::PreOrder (BinTreeNode<T> * subTree, void (*visit) (BinTreeNode<T> *t)) {
     if (subTree != NULL) {
		visit (subTree);		//访问根结点
		PreOrder (subTree->leftChild, visit);
 		 				//遍历左子树
		PreOrder (subTree->rightChild, visit);
  						//遍历右子树
	 }
};

前序遍历（非递归）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> s;//存树节点的栈
        s.push(root);
        while(!s.empty()){
            TreeNode* r=s.top();//取节点
            s.pop();//弹出栈的节点
            if(!r) continue;//当根节点为空时，跳过
            ans.push_back(r->val);//根据栈的先进后访问，然后根据先序遍历：根-左-右
            s.push(r->right);
            s.push(r->left);     
        }
        return ans;
    }
};

图解

中序遍历（递归）

template <class T>
void BinaryTree<T>::InOrder (BinTreeNode<T> * subTree, void (*visit) (BinTreeNode<T> *t)) {
     if (subTree != NULL) {
          InOrder (subTree->leftChild, visit); 
                                                   //遍历左子树
          visit (subTree);		//访问根结点
          InOrder (subTree->rightChild, visit);
                		                    //遍历右子树
	 }
};

中序遍历（非递归）

94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* p = root;

    // 左链入栈循环
    // 这个循环你会发现和后面的的循环代码有一部分重复，你可以进行合并。
    // 但是这样你就需要在后面循环条件多加一个判断 while (p || !st.empty())，代码也会变得稍微没那么直观。你可以参考一下版本二。
    // 为了方便学习还是分开考虑为宜。优化的事情在你学习完后再考虑。
    while (p) {
        st.push(p);
        p = p->left;
    }
    while (!st.empty()) {
        TreeNode * node = st.top();
        st.pop();
        res.push_back(node->val);
        p = node->right;
        // 一旦弹出一个节点，继续做“左链入栈”操作
        while (p) {
            st.push(p);
            p = p->left;
        }
    }   
    return res;
    }
};

牢记“左链入栈”

后序遍历（递归）

145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

template <class T>
void BinaryTree<T>::PreOrder (BinTreeNode<T> * subTree, void (*visit) (BinTreeNode<T> *t)) {
     if (subTree != NULL) {
		visit (subTree);		//访问根结点
		PreOrder (subTree->leftChild, visit);
 		 				//遍历左子树
		PreOrder (subTree->rightChild, visit);
  						//遍历右子树
	 }
};

后序遍历（非递归）

根据后序遍历的：左-右-根

再由图可知

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        TreeNode* r = nullptr;//作用是保存上一次执行的节点

        while(!s.empty() || p){//遍历循环
            if(p)
            {            //走左子树下去，一直保存
                s.push(p);
                p = p->left;
            }
            else
            {
              p = s.top();
                if(p->right == nullptr || p->right == r)
                {                    //判断是否为无右子树节点或者是右子树的父节点
                  res.push_back(p->val);
                  s.pop();                   //注意弹出栈的时机（相对于前中序）
                  r = p;//保留这一次的节点，使得下一次判断新的节点是否为这个节点的父节点
                  p = nullptr;              //置空返回上一层节点
                }
                else                         //这个else要注意
                {
                    p = p->right;    //进入右子树
                }   
            }
        }
        return res;
    }
};

迭代法一般都会有模板

还是推荐理解了过后再用模板（总体思路和上面代码一样），切勿死记硬背

模板

while( 栈非空 || p 非空)
{
if( p 非空)
{

}
else
{

}
}

前序遍历迭代法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;

        while(!s.empty() || p){
            if(p){
                res.push_back(p->val);
                s.push(p);
                p = p->left;
            }else {
                p = s.top();
                s.pop();
                p = p->right;                       
            }
        }

        return res;
    }
};

中序遍历迭代法

class Solution {    
public:
    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;

        while(!s.empty() || p){
            if(p){
                s.push(p);
                p = p->left;
            }else{
                p = s.top();
                s.pop();
                res.push_back(p->val);
                p = p->right;
            }
        }

        return res;
    }
};

后序遍历迭代法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        TreeNode* r = nullptr;

        while(!s.empty() || p){
            if(p){
                s.push(p);
                p = p->left;
            }else{
                p = s.top();
                if(p->right == nullptr || p->right == r){
                    res.push_back(p->val);
                    s.pop();
                    r = p;
                    p = nullptr;
                }else 
                    p = p->right;
            }
        }
        return res;
    }
};

层次遍历

102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> Q;
        if(root!=NULL){
            Q.push(root);//Q.enqueue(root);
        }
        vector<vector<int>> a;
        while(!Q.empty()){
            vector<int> tmp;
            int len=Q.size();
            for(int i=0;i<len;i++){
                TreeNode* x=Q.front();
                Q.pop();//Q.dequeue();
                tmp.push_back(x->val);
                if(x->left!=NULL){
                    Q.push(x->left);
                }
                if(x->right!=NULL){
                    Q.push(x->right);
                }
            }
        a.push_back(tmp);
        }
        return a;
    }
};

更新后序遍历非递归（更简便理解）

发现上面的那些模板太难理解，怎么说呢，只适合记忆临时抱佛脚的

推荐这个，也是在leetcode看到的题解

双栈，其实一个栈来存储后序遍历的顺序，然后根据栈的特性进行遍历！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        vector<int> res;
        stack<TreeNode*> s;
        stack<TreeNode*> r;//存储栈
        s.push(root);
        while(!s.empty()){
            TreeNode *p=s.top();
            s.pop();

            if(!p) continue;  //节点为空就不要存入栈中了

            r.push(p);    //存入栈中！

            if(p->left!=NULL){   //根据后序遍历的遍历顺序:左-右-根
                s.push(p->left);
            }
            if(p->right!=NULL){
                s.push(p->right);
            }
        }

        while(!r.empty()){//开始输出后序遍历
            TreeNode *op=r.top();
            res.push_back(op->val);//当然这里也可以换成cout输出
            r.pop();
        }
        return res;
    }
};