题解 | 二叉树遍历

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

全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
07-02 13:52
武汉大学 golang
骗你的不露头也秒
牛客87776816...:😃查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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