本文介绍 二叉树最大的权值和

二叉树最大的权值和

本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：jintianiloveu

二叉树的非递归遍历

二叉树如果递归遍历的话，非常简单，前序中序后序随便选一个遍历即可。我们来创建一个二叉树看看：

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
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
struct BiTreeNode {
    int data;
    BiTreeNode *left_child;
    BiTreeNode *right_child;
};
void create_tree(BiTreeNode* &tree) {
    int data;
    cin >> data;
    if (data != '\n') {
        if (data == -1) {
            tree = nullptr;
        } else {
            tree = new BiTreeNode;
            tree->data = data;
            create_tree(tree->left_child);
            create_tree(tree->right_child);
        }
    }
}

比如我们有这么一个二叉树：

1
2
3
4
5
      2
    /   \
  3      4
  /
5

这么一个简单的二叉树，一次输入:

1
2 3 5 -1 -1 -1 4 -1 -1

注意，先输入所有的左子树，然后是右子树，没有左右孩子的用-1表示。这个时候树就建立起来了。然后我们前序遍历一下：

1
2
3
4
5
6
7
8
void pre_order_traverse(BiTreeNode* &tree) {
    // 先序遍历
    if (tree) {
        cout << tree->data << " ";
        pre_order_traverse(tree->left_child);
        pre_order_traverse(tree->right_child);
    }
}

得到结果是：

1
2 3 5 4

完全没有错，中序遍历一下：

1
2
3
4
5
6
7
8
void in_order_traverse(BiTreeNode* &tree) {
    // 中序遍历
    if (tree) {
        in_order_traverse(tree->left_child);
        cout << tree->data << " ";
        in_order_traverse(tree->right_child);
    }
}

得到的结果是：

1
5 3 2 4

最重要的是，我们如何实现非递归的遍历二叉树？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void pre_order_traverse_no_recurse(BiTreeNode* &tree) {
    // 非递归先序遍历二叉树
    stack<BiTreeNode*> s;
    BiTreeNode *p = tree;
    // 当栈非空或者p指针非空时调用循环
    while (p != nullptr || !s.empty()) {
        while ( p != nullptr) {
            cout << p->data << " ";
            s.push(p);
            p = p->left_child;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            p = p->right_child;
        }
    }
}

非递归前序遍历，非常好理解：首先我们要从根节点沿着左子树一直遍历，这个时候每次遍历的时候都把p入栈，方便后面左子树遍历完了之后继续遍历那些节点的右子树。也就是说分为两个阶段，第一个阶段遍历左边的，这是前序遍历的基本原则，跟节点优先，接着是左子树，最后如果栈不空，则挨个把之前的节点从栈顶取出来，然后取一个抛一个，获得右边节点，右边节点也会执行左子树操作，最终完成非递归遍历。
非递归遍历的中序遍历实现也大同小异：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void in_order_traverse_no_recurse(BiTreeNode* &tree) {
    stack<BiTreeNode*> s;
    BiTreeNode *p = tree;
    while (p != nullptr || !s.empty()) {
        while ( p != nullptr) {
            s.push(p);
            p = p->left_child;
        }
        if (!s.empty()) {
            p = s.top();
            cout << p->data << " ";
            s.pop();
            p = p->right_child;
        }
    }
}

OK, 牛逼的二叉树遍历算法就到此结束，其实很多时候并不会真的要你去写一个完全正确的二叉树或者遍历操作，最起码你得学习这个思想，怎么用栈去模拟递归，这才是最重要的。