# Binary tree traversal

Posted by chunyang on April 19, 2019

### 介绍

• 先序遍历：根节点，左子节点，右子节点
• 中序遍历：左子节点，根节点，右子节点（二叉搜索树中生成有序数组）
• 后续遍历：左子节点，右子节点，根节点

### Preorder

#### 基本数的定义，构造和打印

1
2

#include <deque>

#include <iostream>

#include <stack> // for  traversal

#include <string>

#include <vector>

using namespace std;

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v): val(v), left(NULL), right(NULL) {}
static TreeNode* create_tree(string str);
static string str(TreeNode* node);
static void free_node(TreeNode* node);
};

TreeNode* TreeNode::create_tree(string str) {
if (str.empty()) return NULL;
int length = str.size();
vector<TreeNode*> nodes;
for(int i = 0; i < length; ++i) {
int j = i;
if (str[j] == ' ') continue;
if (str[j] == '?') {
nodes.push_back(NULL);
continue;
}
while (j < length && str[j]>='0' && str[j] <= '9') ++j;
cout << str.substr(i, j - i) << endl;
nodes.push_back(new TreeNode(stoi(str.substr(i, j - i))));
i = j;
}
length = nodes.size();
for (int i = 0; i < length; ++i) {
if (!nodes[i]) continue;
cout << "connecting node: " << nodes[i]->val << endl;
if (2 * i + 1 < length) nodes[i]->left = nodes[2 * i + 1];
if (2 * i + 2 < length) nodes[i]->right = nodes[2 * i + 2];
}
cout << "nodes size: " << nodes.size() << endl;
return nodes[0];
}

string TreeNode::str(TreeNode* node) {
string s;
if (!node) return s;
deque<TreeNode*> cur;
deque<TreeNode*> next;
cur.push_back(node);
int count = 1;
while (!cur.empty()) {
string cur_layer;
int cur_count = 0;
while (!cur.empty()) {
TreeNode* node = cur.front(); cur.pop_front();
++cur_count;
if (node == NULL) {
cur_layer += "? ";
}
else {
cout << "stringize node: " << node->val << endl;
cur_layer += to_string(node->val);
cur_layer += " ";
if (node->left)
next.push_back(node->left);
if (node->right)
next.push_back(node->right);
}
}
int remain_q = count - cur_count;
cout << "remain ?: " << remain_q << " cur layer: " << cur_layer << endl;
while (remain_q-- > 0) s += "? ";
count <<= 1;
s += cur_layer;
cur.swap(next);
}
int j = s.size();
cout << "string s: " << s << endl;
while (j > 0 && (s[j-1] == ' ' || s[j-1] == '?')) --j;
return s.substr(0, j);
}

void TreeNode::free_node(TreeNode* node) {
if (!node) return;
if (node->left) free_node(node->left);
if (node->right) free_node(node->right);
delete node;
}

int main(int argc, char* argv[]) {

string str = "1 ? 3 ? ? ? 5 ? ? ? ? ? ? 6 70";
cout << "creating: " << str << endl;
TreeNode* node = TreeNode::create_tree(str);
cout << "string: " << TreeNode::str(node) << endl;
TreeNode::free_node(node);

return 0;
}


#### 先序遍历

vector<int> preorder(TreeNode* node) {
vector<int> result;
stack<TreeNode*> st;
st.push(node);
while (!st.empty()) {
TreeNode* top = st.top();
result.push_back(top->val);
if (top->right) st.push(top->right);
if (top->left) st.push(top->left);
}
return result;
}


### Inorder

vector<int> inorder(TreeNode* node) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = node;
while (!st.empty() || cur) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top(); st.pop();
result.push_back(cur->val);
cur = cur->right;
}

return result;
}


### Postorder

vector<int> postorder(TreeNode* node) {
vector<int> result;
stack<TreeNode*> st;
st.push(node);
TreeNode* prev = NULL;
while(!st.empty()) {
TreeNode* top = st.top();
if (prev != NULL && (prev == top->right || prev == top->left)) {
result.push_back(top->val);
st.pop();
prev = top;
} else if (top->left == NULL && top->right == NULL) {
result.push_back(top->val);
st.pop();
prev = top;
} else {
if (top->right) st.push(top->right);
if (top->left) st.push(top->left);
}
}

return result;
}


### State machine

Elements of programming 中，有另外一个非常巧妙的解法。利用状态机来完成转换。