C++实现二叉树的先序、中序、后序遍历（递归和非递归方法）

Tags: 数据结构 c++ 树

1.二叉树的基本结构

struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int val):
        val(val), left(nullptr), right(nullptr){}
};

2.遍历方式

2.1 递归方式

基于二叉树的构建思想，二叉树的结构本身就是一种递归结构，因此 递归 可以作为解决二叉树的基本解法。
一般递归方法的时间复杂度为，空间复杂度为，因为需要遍历所有节点。

2.2 非递归方式

主要是利用 stack 的结构使用 __迭代==的方式遍历，大致的实现步骤（以先序遍历为例）为：建立一个空栈，将 节点压入栈中，然后以“栈不为空”的条件进行迭代：

• 取出栈顶元素，进行相应操作
• 再将 和 压入栈中
• 下一次迭代，直到栈为空

后序遍历实现：

• 两个栈，第一个作为中间栈，按照先 后 的遍历顺序，然后依次取出该栈的元素，放入第二个栈中

3 代码实现

递归

相对比较简单，网上代码比较多，可以查考：https://blog.csdn.net/u010558281/article/details/74276577

非递归

//先序遍历
void preOrder(Node* head){
    if(head == nullptr) return;
    std::stack<Node*> nstack;
    Node* p = head;
    nstack.push(p);
    while(!nstack.empty()){
        p = nstack.top();
        cout<<p->val<<endl;
        nstack.pop();
        
        if(p->right) 
            nstack.push(p->right);
        
        if(p->left)
            nstack.push(p->left);
    }
}

//中序遍历
void inOrder(Node* head) {
    if (head == nullptr) {
        return;
    }
    std::stack<Node*> nstack;
    while (!nstack.empty() || head != nullptr) {
        if (head != nullptr) {
            nstack.push(head);
            head = head->left;
        } else {
            head = nstack.top();
            std::cout << head->value << ",";
            nstack.pop();
            head = head->right;
        }
    }
}

//后序遍历
void posOrder(Node* head) {
    if (head == nullptr) {
        return;
    }
    std::stack<Node*> nstack1, nstack2; //两个栈，
    nstack1.push(head);
    while (!nstack1.empty()) {
        Node* head = nstack1.top();
        nstack2.push(head);
        nstack1.pop();
        if (head->left != nullptr) {
            nstack1.push(head->left);
        }
        if (head->right != nullptr) {
            nstack1.push(head->right);
        }
    }

    while (!nstack2.empty()) {
        std::cout << nstack2.top()->value << ",";
        nstack2.pop();
    }
}

参考链接：https://blog.csdn.net/alxe_made/java/article/details/94721195