题解 | 二叉树遍历

#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;
}

全部评论

相关推荐

点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务