题解 | 二叉树遍历

#include <iostream>
#include <string>

using std::cout;
using std::cin;
using std::endl;
using std::string;

struct TNode {
    char data;
    TNode* lchild;
    TNode* rchild;
};

int idx = 0;	// 在用户输入的字符串的索引（下标）
string input;	// 用户输入的字符串

// 先序遍历建树
void preBulid(TNode* root) {
    if (input[idx] == '#') {	// 若当前字符是#说明自子树是空树
        root->lchild = nullptr;
        ++idx;	// 指向下一个字符串
    } else {	// 否则说明左孩子存在
        TNode* lnode = new TNode(); 
        lnode->data = input[idx];
        ++idx;
        root->lchild = lnode;
        preBulid(lnode);
    }

    if (input[idx] == '#') {	// 说明右孩子不存在
        root->rchild = nullptr;
        ++idx;
    } else {	// 右孩子存在
        TNode* rnode = new TNode();
        rnode->data = input[idx];
        ++idx;
        root->rchild = rnode;
        preBulid(rnode);
    }
}

// 中序遍历输出结果
void InOrder(TNode* root) {
    if (root->lchild)
        InOrder(root->lchild);
    cout << root->data << ' ';
    if (root->rchild)
        InOrder(root->rchild);
}

int main() {
    while (getline(cin, input)) {
        idx = 1;
        if (input.size() == 0) {
            cout << endl;
            continue;
        } else if (input.size() == 1) {
            cout << input << endl;
            continue;
        }
        TNode* root = new TNode();
        root->data = input[0];

        preBulid(root);
        InOrder(root);
        cout << endl;
    }

    return 0;
}