title: 二叉樹最大的權值和
date: 2017-09-16 09:32:32
category: 默認分類
本文介紹 二叉樹最大的權值和
二叉樹最大的權值和
本文由在當?shù)剌^為英俊的男子金天大神原創(chuàng)，版權所有席噩，歡迎轉載仲墨，本文首發(fā)地址 https://jinfagang.github.io 括荡。但請保留這段版權信息，多謝合作提揍，有任何疑問歡迎通過微信聯(lián)系我交流：
jintianiloveu
二叉樹的非遞歸遍歷
二叉樹如果遞歸遍歷的話啤月，非常簡單，前序中序后序隨便選一個遍歷即可劳跃。我們來創(chuàng)建一個二叉樹看看：
#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);
}
}
}
比如我們有這么一個二叉樹：
2
/ \
3 4
/
5
這么一個簡單的二叉樹谎仲，一次輸入:
2 3 5 -1 -1 -1 4 -1 -1
注意，先輸入所有的左子樹刨仑，然后是右子樹郑诺，沒有左右孩子的用-1表示夹姥。這個時候樹就建立起來了。然后我們前序遍歷一下：
void pre_order_traverse(BiTreeNode* &tree) {
// 先序遍歷
if (tree) {
cout << tree->data << " ";
pre_order_traverse(tree->left_child);
pre_order_traverse(tree->right_child);
}
}
得到結果是：
2 3 5 4
完全沒有錯辙诞，中序遍歷一下：
void in_order_traverse(BiTreeNode* &tree) {
// 中序遍歷
if (tree) {
in_order_traverse(tree->left_child);
cout << tree->data << " ";
in_order_traverse(tree->right_child);
}
}
得到的結果是：
5 3 2 4
最重要的是辙售，我們?nèi)绾螌崿F(xiàn)非遞歸的遍歷二叉樹？
void pre_order_traverse_no_recurse(BiTreeNode* &tree) {
// 非遞歸先序遍歷二叉樹
stack<BiTreeNode*> s;
BiTreeNode *p = tree;
// 當棧非空或者p指針非空時調(diào)用循環(huán)
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;
}
}
}
非遞歸前序遍歷飞涂，非常好理解：首先我們要從根節(jié)點沿著左子樹一直遍歷旦部，這個時候每次遍歷的時候都把p入棧，方便后面左子樹遍歷完了之后繼續(xù)遍歷那些節(jié)點的右子樹较店。也就是說分為兩個階段士八，第一個階段遍歷左邊的，這是前序遍歷的基本原則泽西，跟節(jié)點優(yōu)先曹铃，接著是左子樹，最后如果棧不空捧杉，則挨個把之前的節(jié)點從棧頂取出來陕见，然后取一個拋一個，獲得右邊節(jié)點味抖，右邊節(jié)點也會執(zhí)行左子樹操作评甜，最終完成非遞歸遍歷。
非遞歸遍歷的中序遍歷實現(xiàn)也大同小異：
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, 牛逼的二叉樹遍歷算法就到此結束仔涩，其實很多時候并不會真的要你去寫一個完全正確的二叉樹或者遍歷操作忍坷，最起碼你得學習這個思想，怎么用棧去模擬遞歸熔脂，這才是最重要的佩研。
