binarytree-traversal

Posted on | In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node {
	int val;
	struct node* left;  //左孩子
	struct node* right;  //右孩子
}

// pre-order: root, left, right
Node* p = root;
std::stack<Node*> s;
while (!s.empty() || p) {
    if (p) {
    	//边遍历边打印，并存入栈中，以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
        cout << p->val << endl;
        s.push(p);
        p = p->left;
    } else {
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        p = s.top();
        s.pop();
        p = p->right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// in-order: left, root, right
Node* p = root;
std::stack<Node*> s;
while (!s.empty() || p) {
    if (p) { 	
        //代码段(i)一直遍历到左子树最下边，边遍历边保存根节点到栈中
        s.push(p);
        p = p->left;
    } else { 
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        p = s.top();
        s.pop();
        cout << s->val << endl;
        //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
        p =  p->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
29
30
31
32
33
34
35
36
37
38
39
40
// post-order
/*
 *   后序遍历递归定义：先左子树，后右子树，再根节点。后序遍历的难点在于：
 *   需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需
 *   跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访
 *   问根节点。直接看代码，代码中有详细的注释。
 *
 */
Node* cur = root;
Node* pre;
std::stack<Node*> s;

//先把cur移动到左子树最下边
while (cur) {
    s.push(cur);
    cur = cur->left;
}

while (!s.empty()) {
    //走到这里，cur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
    cur = s.top();
    s.pop();

    //一个根节点被访问的前提是：无右子树或右子树已被访问过
    if (s->right == NULL || s->right = pre) {
        cout << s->val << endl;
        //修改最近被访问的节点
        pre = cur;
    } else { 
        // 访问右子树，先把根节点再入栈
        s.push(cur); 

        //进入右子树，且可肯定右子树一定不为空
        cur = s->right;
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
    }
}