数据结构——二叉树及其易记迭代遍历写法

首先二叉树有不同的遍历顺序：

• preorder（前序遍历：根-左-右）
• inorder（中序遍历：左-根-右）
• postorder（后序遍历：左-右-根）

其中的 '左' 和 '右' 是二叉树的 左子树 和 右子树 的简称。

树的3种遍历顺序都可以使用 迭代法 和 递归方式实现，两种实现方式的区别：

• 迭代：实际使用栈来模拟遍历的方式（其中使用nullptr标记法的迭代遍历写法比较通用——针对三种不同的遍历方式只需要更改3-4行的语句就可以实现）
• 递归：递归方式实现二叉树的三种遍历写法更加简洁，比较简单

二叉树的迭代方式实现，这个是参考的leetcode上这个题解：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/miao-sha-quan-chang-ba-hou-lang-by-sonp/（nullptr标记法）

/*
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    struct TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
*/

// 前序遍历
vector<int> Preorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode *> stk;
    TreeNode *cur = root;
    if (cur != nullptr) {
        stk.push(cur);
    }
    while (!stk.empty()) {
        TreeNode *temp = stk.top();
        stk.pop();
        if (temp != nullptr) {
            // 栈后进先出，因此前序遍历需要按照右-左-根-nullptr入栈
            // 右
            if (temp->right) stk.push(temp->right);
            
            // 左    
            if (temp->left) stk.push(temp->left);
            
            // 根    
            stk.push(temp);
            stk.push(nullptr);  // 入栈temp后紧跟入栈nullptr，它将作为根结点的标记，表示该结点已经被访问过了

        }
        else {
            res.push_back(stk.top()->val);  // 节点被访问过了，因此这时栈顶为前（或中、后）序遍历需要存入res的节点
            stk.pop();  // 将该结点完全弹出
        }
    } 
    return res;
}

// 中序遍历
vector<int> Inorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode *> stk;
    TreeNode *cur = root;
    if (cur != nullptr) {
        stk.push(cur);
    }
    while (!stk.empty()) {
        TreeNode *temp = stk.top();
        stk.pop();
        if (temp != nullptr) {
            // 注意这里和前序遍历的区别，只更改了入栈的顺序，
            // 中序遍历需要按照右-根-nullptr-左入栈
            // 右
            if (temp->right) stk.push(temp->right);
            
            // 根    
            stk.push(temp);
            stk.push(nullptr);

            // 左    
            if (temp->left) stk.push(temp->left);
        }
        else {
            res.push_back(stk.top()->val);
            stk.pop();
        }
    } 
    return res;
}

// 后续遍历
vector<int> Postorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode *> stk;
    TreeNode *cur = root;
    if (cur != nullptr) {
        stk.push(cur);
    }
    while (!stk.empty()) {
        TreeNode *temp = stk.top();
        stk.pop();
        if (temp != nullptr) {
            // 注意这里和前序遍历、中序遍历的区别，只更改了入栈的顺序，
            // 后遍历需要按照根-nullptr-右-左入栈
            
            // 根    
            stk.push(temp);
            stk.push(nullptr);

            // 右
            if (temp->right) stk.push(temp->right);

            // 左    
            if (temp->left) stk.push(temp->left);
        }
        else {
            res.push_back(stk.top()->val);
            stk.pop();
        }
    } 
    return res;
}

二叉树使用上面的方式迭代方式遍历时，注意要判断当前节点的左、右子树是否存在，而不是判断左右子结点！

最后

以上就是优美发卡为你收集整理的数据结构——二叉树及其易记迭代遍历写法的全部内容，希望文章能够帮你解决数据结构——二叉树及其易记迭代遍历写法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。