二叉树的遍历

此题考察最基本的二叉树的构造和中序遍历。

// runtime: 3ms
// space: 488K
#include <iostream>
#include <string>
using namespace std;
// 二叉树结构体
struct BTree {
    char data;
    BTree* leftChild;
    BTree* rightChild;
    BTree(char c) : data(c), leftChild(NULL), rightChild(NULL) {}
};
// 构造二叉树
BTree* BuildTree(int& position, string str) { // 这里position是int型的引用，可以达到“记住”position的效果
    char c = str[position++];
    if (c == '#') {
        return NULL;
    }

    BTree* root = new BTree(c);
    root->leftChild = BuildTree(position, str);
    root->rightChild = BuildTree(position, str);
    return root;
}
// 中序遍历
void InOrder(BTree* root) {
    if (root == NULL) {
        return ;
    }

    InOrder(root->leftChild);
    cout<<root->data <<" ";
    InOrder(root->rightChild);
    return ;
}

int main() {
    string s;
    while (cin>> s) {
        int pos = 0;
        BTree* root = BuildTree(pos, s);
        InOrder(root);
        cout<< endl;
    }
    return 0;
}

由于前、中、后序遍历的代码只是调整了一下打印data的顺序，所以再给出一段常用的层序遍历的代码

void LevelOrder(BTree* root) {
    queue<BTree*> q;
    if (root != NULL) {
        q.push(root);
    }

    while (!q.empty()) {
        BTree* current = q.front();
        q.pop();
        cout<< current->data << " ";
        if (current->leftChild != NULL)
            q.push(current->leftChild);
        if (current->rightChild != NULL)
            q.push(current->rightChild);
    }
    return ;
}