By

文章目录
  1. 前序遍历。

思想： 首先访问根，然后把访问根的入栈，访问该根的左子树，左子树结束之后，弹出根，访问右子树，对于右子树，重复上述。知道栈为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(Node *root){
    stack<Node*>s;
    Node * p=root;
    while(p!=NULL||!s.empty()){
        while(p!=NULL){
            cout<<p->data<<endl;
            s.push(p);
            p=p->left;
        }
        if(!s.empty()){
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}
  1. 中序遍历。

思想：思想和前序遍历一样。只是访问根的是在出栈的时候。

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

void  inOrder(Node *root){
     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();
            cout<<p->data<<endl;
            s.pop();
            p=p->right;
        }
    }
}
  1. 后序遍历。

思想： 这是最难的。对于一棵树来说，我们可以把根，右孩子，左孩子一次入栈，这样出来的时候就可以是左右根了。每一次弹出栈的时候，如果该节点是没有儿子的，说明该节点可以直接访问，如果该节点是已经被访问过的，说明该节点是根，可以直接访问，否则的话，就把该节点的有孩子，左孩子一次入栈。

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

void postOrder(Node *root){
    stack<Node*>s;
    Node *pre;
    Node *p=NULL;
    s.push(root);
    while(!s.empty()){
        p=s.top();
        if((p->left==NULL&&p->right==NULL)||(pre!=NULL&&(pre==p->left||pre==p->right))){
            cout<<p->data<<endl;
            s.pop();
            pre=p;
        }
        else{
            if(p->right!=NULL)
                s.push(p->right);
            if(p->left!=NULL)
                s.push(p->left);
        }
    }
}
文章目录