二叉树的DFS遍历(非递归)

前言

递归是利用函数压栈实现，如果我们要将递归的写法转化为非递归写法，自然需要利用栈来实现。

二叉树的实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;
struct treeNode {
    int val;
    int position;
    treeNode* left;
    treeNode* right;
    treeNode(int val,int position){
        this->val = val;
        this->position = position;
        this->left = nullptr;
        this->right = nullptr;
    }
};


class BinaryTree {

public:
  treeNode* root = nullptr;
  BinartTree(){
      root = nullptr;
  }
  void pre_order();
  void mid_order();
  void back_order()
};

前序遍历非递归写法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 *前序遍历
 **/
void BinaryTree::pre_order(){
    treeNode* currentNode = root;
    std::stack<treeNode*> stack;
    while (currentNode||!stack.empty()) {
        if (currentNode) {
            std::cout<<currentNode->val<<std::endl;
            stack.push(currentNode);
            currentNode = currentNode->left;
        }else{
            currentNode = stack.top();
            stack.pop();
            currentNode = currentNode->right;
        }
    }


}

中序遍历非递归写法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 *中序遍历
 **/
void BinaryTree::mid_order(){
    treeNode* currentNode = root;
    std::stack<treeNode*> stack;
    while (!stack.empty()||currentNode) {
        if (currentNode) {
            stack.push(currentNode);
            currentNode = currentNode->left;
        }else{
            currentNode = stack.top();
            stack.pop();
            std::cout<<currentNode->val<<std::endl;
            currentNode = currentNode->right;
        }
    }

}

后序遍历非递归写法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 *后序遍历
 **/
void BinaryTree::back_order(){
    treeNode* currentNode = root;
    treeNode* lastVisitNode = nullptr;
    std::stack<treeNode*> stack;

    while (currentNode) {
        stack.push(currentNode);
        currentNode = currentNode->left;
    }
    while (!stack.empty()) {
        currentNode = stack.top();
        stack.pop();
        if (currentNode->right==nullptr||currentNode->right==lastVisitNode) {
            std::cout<<currentNode->val<<std::endl;
            lastVisitNode = currentNode;
        }else{
            stack.push(currentNode);
            currentNode = currentNode->right;
            while (currentNode) {
                stack.push(currentNode);
                currentNode = currentNode->left;
            }
        }
    }
}

Comments