CentOS 7.0 环境编译thinstation

后序遍历

源码

递归

#include<iostream>
#include<stack>
#include<queue>
//节点结构体
struct Node{
    int value;
    Node * left;
    Node * right;
    Node(int value):value(value),left(NULL),right(NULL){}
};

//后序遍历递归实现
void postOrder(Node *node){
    if(node){
        postOrder(node->left);
        postOrder(node->right);
        std::cout<<node->value;
    }

}
//后序遍历非递归实现
void postOrder(Node *node){
    std::stack<Node *> nstack;
    Node* lastVisit = node;
    nstack.push(node);
    while(node != NULL || !nstack.empty()){
        while(node!=NULL){
            nstack.push(node);
            node = node->left;
        }
        node = nstack.top();
        if(node->right == NULL || node->right == lastVisit ){
            cout << node->value;
            lastVisit = node;
            node = NULL;
        }else{
            node = node->right;
        }
    }
}

算法分析

信息

1. 递归遍历顺序： 左子树->右子树->根节点
2. 非递归：使用栈，并且将先前输出的节点标记一下，while循环：先遍历左子树压栈，然后每pop一个节点判断其右节点是否为空，是否等于lastVisit，如果是则将lastVist置为当前节点，将node置为空。如果不是，则将node指向右节点

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 876208453@qq.com