时间限制: 1 Sec 内存限制: 128 MB
题目描述
给定一颗二叉树的逻辑结构。
(先序遍历的结果,空树用字符‘#’表示,例如AB#C##D##),建立该二叉树的二叉链式存储结构,并输出该二叉树的先序遍历、中序遍历和后序遍历结果。
输入
第一行输入一个整数t,表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果,空树用字符‘#’表示,连续输入t行。
输出
输出每个二叉树的先序遍历、中序遍历和后序遍历结果。
样例输入
2 AB#C##D## AB##C##
样例输出
ABCD BCAD CBDA ABC BAC BCA
解决方案
#include <iostream>
class BiTree {
public:
BiTree() : root(nullptr) {}
void assign(std::string &string) {
int index = 0;
assign(string, index, root);
}
void print() {
preOrderTraversal(root);
std::cout << std::endl;
inOrderTraversal(root);
std::cout << std::endl;
postOrderTraversal(root);
std::cout << std::endl;
}
private:
struct Node {
char data;
Node *left;
Node *right;
Node() : data(0), left(nullptr), right(nullptr) {}
explicit Node(char data) : data(data), left(nullptr), right(nullptr) {}
Node(char data, Node &left, Node &right) : data(data), left(&left), right(&right) {}
};
Node *root;
static void assign(const std::string &string,int &index, Node *&pNode) {
char data = string[index++];
if (data != '#') {
pNode = new Node(data);
assign(string, index, pNode->left);
assign(string, index, pNode->right);
} else {
pNode = nullptr;
}
}
static void preOrderTraversal(Node *node) {
if (node) {
std::cout << node->data;
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
};
static void inOrderTraversal(Node *node) {
if (node) {
inOrderTraversal(node->left);
std::cout << node->data;
inOrderTraversal(node->right);
}
}
static void postOrderTraversal(Node *node) {
if (node) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
std::cout << node->data;
}
}
};
int main() {
size_t t;
std::cin >> t;
while (t--) {
std::string string;
std::cin >> string;
BiTree biTree;
biTree.assign(string);
biTree.print();
}
}