数据结构-前序遍历、中序遍历、后序遍历、层级遍历(递归、非递归)

短命女 2022-07-24 05:01 262阅读 0赞

二叉树的遍历是一个非常基础又重要的内容。遍历就是访问二叉树中的每一个节点，并且每个节点只访问一次。二叉树的遍历分为前序遍历、中序遍历、后序遍历和层级遍历。

# 前序遍历 #

前序遍历的顺序是：根节点 -> 左子节点 -> 右子节点。

![这里写图片描述][E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_89_8D_E5_BA_8F_E9_81_8D_E5_8E_86.png]

上图二叉树的前序遍历结果是： ABCDEFGH

## 递归实现 ##

按照前序遍历的顺序，可以非常快写出其递归实现

void PreOrderTraverseRec (Node* root) {
    
        if (root != NULL) {
            printf("%d ", root->val);
            PreOrderTraverseRec (root->left);
            PreOrderTraverseRec (root->right);
        }
    }

## 非递归实现 ##

前序遍历的非递归实现可以使用栈模拟。

### 版本1 ###

其实在前序遍历的内部实现，每次遍历一个节点后，接下来先遍历这个节点的左子节点，对这个左子节点将其看成根节点，又递归遍历其左子节点，直到访问到叶节点。将叶节点弹栈，得到其父节点。因为已经访问过父节点，以及父节点的左子节点，所以接下来应该按照上述方法递归访问父节点的右子树。

void PreOrderTraverseNonRec (Node* root) {
    
        if (root == NULL) {
            printf("empty tree!\n");
            return;
        } else {
    
            //method 1
            stack<Node*> s;
            Node* p = root;
    
            while ( p != NULL || !s.empty()) {
    
                while (p != NULL) {
                    printf("%d ", p->val);
                    s.push (p);
                    p = p->left;
                }
    
                if (!s.empty()) {
                    p = s.top ();
                    s.pop ();
                    p = p->right;
                }
            }
        }
    }

### 版本2 ###

还有另外一种更加简洁的用栈模拟的方法。前序遍历的顺序是遍历根节点 -> 左子节点 -> 右子节点。根据栈的后进先出的特点，可以按照根节点 -> 右节点 -> 左子节点的顺序将节点压入栈中。这样每次压栈之前访问根节点，在弹栈先访问左子节点，再到右子节点。

void PreOrderTraverseNonRec (Node* root) {
    
            stack<Node*> s;
            Node* cur = NULL;
            s.push (root);
    
            while (!s.empty()) {
    
                cur = s.top ();
                printf("%d ", cur->val);
                s.pop (cur);
    
                if (cur->right)
                    s.push (cur->right);
                if (cur->left)
                    s.push (cur->left);
            }
        }
    }

# 中序遍历 #

中序遍历的顺序是： 根节点的左子节点 -> 根节点 -> 根节点的右子节点

## 递归实现 ##

void InOrderTraverseRec (Node* root) {
    
        if (root != NULL) {
            InOrderTraverseRec (root->left);
            printf("%d ", root->val);
            InOrderTraverseRec (root->right);
        }
    }

## 非递归实现 ##

![这里写图片描述][E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E4_B8_AD_E5_BA_8F_E9_81_8D_E5_8E_86.png]

中序遍历的非递归实现与前序遍历非递归实现的版本1很相似，只不过输出根节点的先后顺序不同。

void InOrderTraverseNonRec (Node* root) {
    
        if (root == NULL) {
            printf("empty tree!\n");
            return;
        } else {
    
            stack<Node*> s;
            Node* p = root;
    
            while (p != NULL || !s.empty()) {
    
                while (p != NULL) {
                    s.push (p);
                    p = p->left;
                }
    
                if (!s.empty()) {
                    p = s.top ();
                    s.pop ();
                    printf("%d ", p->val);
                    p = p->right;
                }
            }
        }
    }

# 后序遍历 #

后续遍历的顺序为： 左子节点 -> 右子节点 -> 根节点

## 递归实现 ##

void PostOrderTraverseRec (Node* root) {
    
        if (root != NULL) {
            PostOrderTraverseRec (root->left);
            PostOrderTraverseRec (root->right);
            printf("%d ", root->val);
        }
    }

## 非递归实现 ##

![后序遍历][E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_90_8E_E5_BA_8F_E9_81_8D_E5_8E_86.png]

### 版本1 ###

由于后续遍历中需要先访问左、右子节点，再来访问根节点，因此非递归实现应该为：访问根节点，再向左不断访问左子节点，直到访问到叶子节点，这时不能将这个叶子节点弹栈，因为其右子节点还没有被访问。所以，应该按照上述方法访问完叶节点的右子树，再来访问叶节点。为了区别出两次访问顺序，可以使用一个变量记录根节点是否已经被访问过。

void PostOrderTraverseNonRec2 (Node* root)
    {
        if (root == NULL) return;
    
        stack <Node*> s;
        Node *p = root;
    
        while (p != NULL || !s.empty()) {
    
            while (p != NULL) {
                p->isFirstVisited = true;
                s.push(p);
                p = p->left;
            }
    
            while ( !s.empty()) {
                p = s.top();
                if (p->isFirstVisited) {
                    p->isFirstVisited = false;
                    p = p->right;
                } else {
                    printf("%d ", p->val);
                    s.pop();
                    p = NULL;
                }
            }
    
        }
    }

### 版本2 ###

第一种方法需要额外的空间存储节点是否被访问过，浪费空间。可以直接使用一个指针记录当前访问的节点的前一个被访问的节点，如果前一个被访问的节点正好是当前节点的右子节点，则说明右子节点已经被访问过，直接输出当前节点即可。

void PostOrderTraverseNonRec (Node* root) {
    
        stack<Node*> s;
        Node *cur = root, *pre = NULL;
    
        while (cur != NULL || !s.empty()) {
    
            while (cur != NULL) {
                s.push (cur);
                cur = cur->left;
            }
    
            if (!s.empty()) {
                cur = s.top ();
                if (cur->right == NULL || cur->right == pre) {
                    printf("%d ", cur->val);
                    pre = cur;
                    s.pop ();
                    cur == NULL;
                } else {
                    cur = cur->right;
                }
            }
        }
    }

# 层级遍历 #

![层级遍历][E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_B1_82_E5_BA_8F_E9_81_8D_E5_8E_86.png]

层级遍历就是按照层次的顺序，从上往下一层一层遍历二叉树。

## 递归实现 ##

为了能够逐层遍历二叉树，必须知道二叉树的高度，然后才能逐层遍历。而在每一层中，先遍历根节点的左子节点，再遍历右子节点。

int GetHeight (Node* root) {
        if(root == NULL)
            return 0;
        else
            return max(GetHeight(root->left) + 1, GetHeight(root->right) + 1);
    }
    
    void PrintLevel (Node* root, int level) {
    
        if (root == NULL)
            return;
    
        if (level == 1) {
            printf("%d ", root->val);
            return;
        }
    
        return ( PrintLevel(root->left, level-1) + PrintLevel( root->right, level-1));
    
    }
    
    void LevelTraverseRec (Node* root) {
    
        int height = GetHeight (root);
        for (int i = 1; i <= height; ++i)
        {
            PrintLevel (root, i);
        }
    }

## 非递归实现 ##

层级遍历可以使用队列来模拟：每次访问根节点R，再分别访问根节点的左右子节点L、R，再继续访问L、R的左右子节点。这就符合队列的先进先出的特定。

void LevelTraverseNonRec (Node* root) {
    
        if (root == NULL) return;
    
        Node* cur = root;
        queue<Node*> q;
        q.push (root);
    
        while (!q.empty()) {
            cur = q.front ();
            printf("%d ", cur->val);
            q.pop ();
    
            if (cur->left)
                p.push (p->left);
            if (cur->right)
                p.push (p->right);
        }
    }

[E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_89_8D_E5_BA_8F_E9_81_8D_E5_8E_86.png]: http://7xi5kq.com1.z0.glb.clouddn.com/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86.png
[E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E4_B8_AD_E5_BA_8F_E9_81_8D_E5_8E_86.png]: http://7xi5kq.com1.z0.glb.clouddn.com/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86.png
[E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_90_8E_E5_BA_8F_E9_81_8D_E5_8E_86.png]: http://7xi5kq.com1.z0.glb.clouddn.com/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86.png
[E5_A4_A7_E8_AF_9D_E6_95_B0_E6_8D_AE_E7_BB_93_E6_9E_84_E5_B1_82_E5_BA_8F_E9_81_8D_E5_8E_86.png]: http://7xi5kq.com1.z0.glb.clouddn.com/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.png