二叉树的遍历

思路

大家对于遍历二叉树应该很熟悉了，重点就是构建二叉树，构建二叉树和遍历二叉树是类似的，因为都是走的一个路径，所以我们就可以模拟先序遍历来进行构建。

#include<iostream>
#include<stack>

using namespace std;

class TreeNode{
public:
    char val;
    TreeNode* left;
    TreeNode* right;
public:
    TreeNode(char val) : val(val), left(NULL), right(NULL) {}
};
// 递归构建二叉树
int pos = 0;
TreeNode* createTree(string s){
    char c = s[pos ++];
    if(c =='#')//若是‘#’，说明该节点为空返回上一级节点
        return NULL;
    TreeNode* root = new TreeNode(c);//若不为‘#’，则创建该节点，并为本节点赋值
    root->left = createTree(s);//创建左子树
    root->right = createTree(s);//创建右子树
    return root;
}

void inOrder(TreeNode* root){
    if(root == NULL) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

int main(){
    string s;
    while(cin >> s){
        inOrder(createTree(s));
    }
    return 0;
}