二叉树的遍历（C++实现）

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

定义二叉树结点类

1
2
3
4
5
6
7
struct BinaryTreeNode {
    int val;
    BnaryTreeNode* lc;
    BinaryTreeNode* rc;
    BinaryTreeNode (int cont& _val, BinaryTreeNode* _lc = nullptr, BinaryTreeNode* _rc = nullptr) : 
    val(_val), lc(_lc), rc(_rc) {}
};

先序遍历、中序遍历、后序遍历访问节点的顺序是一致的， 不同之处在于处理节点的顺序。有的遍历流程把访问到的节点暂存起来，达成某种条件后再对其进行处理（比如输出），我们约定，根节点V、左孩子L、右孩子R，那么遍历顺序可以记为：

  • 先序遍历VLR：到达一个节点后，即刻输出该节点的值，并继续遍历其左、右子树。
  • 中序遍历LVR：到达一个节点后，先将该节点暂存，遍历完其左子树后，再输出该节点的值，然后遍历其右子树。
  • 后序遍历LRV： 到达一个节点后，先将该节点暂存，遍历完其左右子树后，再输出该节点的值。

C++实现

先序遍历（VLR）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pre_traversal (BinaryTreeNode* root) {
    stack<BinaryTreeNode*> stackNode;

    while (root != nullptr || !stackNode.empty()) {
        if (root != nullptr) {
            cout << root->val << " ";
            stackNode.push(root);
            root = root->lc;
        } else {
            root = stackNode.top();
            stackNode.pop();
            root = root->rc;
        }
    }
}

中序遍历

与先序遍历类似，唯一区别是到达该节点时，并不直接输出该节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void in_traversal (BinaryTreeNode* root) {
    stack<BinaryTreeNode*> stackNode;
    while (root != nullptr || !stackNode.empty()) {
        if (root != nullptr) {
            stackNode.push(root);
            root = root->lc;
        } else {
            root = stackNode.top();
            stackNode.pop();
            cout << root->val << " ";
            root = root->rc;
        }
    } 
}

后序遍历

后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已遍历完成。 因此， 我们需要设置一个lastvisit指针，若lastvisit指向当前节点的右孩子，表示该节点的左右子树都已遍历完成，可以输出当前节点 （否则，继续探索当前节点的右子树）， 并使lastvisit指向当前节点， 将当前节点（指针）设置为空（这样，下一轮循环就可以访问栈顶元素）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void post_traversal (BinaryTreeNode* root) {
    stack<BinaryTreeNode*> stackNode;
    BinaryTreeNode* lastvisit = root;
    while (root != nullptr || !stackNode.empty()) {
        if (root != nullptr) {
            stackNode.push(root);
            root = root->lc;
        } else {
            root = stackNode.top();
            if (root->rc == nullptr || root->rc == lastvisit) {
                cout << root->val <<" ";
                stackNode.pop();
                lastvisit = root;
                root = nullptr;
            } else {
                root = root->rc;
            }
        }
    }
}
0%