新二叉树
题目描述
输入一串二叉树,输出其前序遍历。
输入格式
第一行为二叉树的节点数 $n$。($1 \leq n \leq 26$)
后面 $n$ 行,每一个字母为节点,后两个字母分别为其左右儿子。特别地,数据保证第一行读入的节点必为根节点。
空节点用 *
表示
输出格式
二叉树的前序遍历。
样例 #1
样例输入 #1
6
abc
bdi
cj*
d**
i**
j**
样例输出 #1
abdicj
思路
用一个结构体数组储存二叉树,第一个节点为根节点root,然后输出先序遍历。
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
struct Snode {
char l;
char r;
}node[30];
char root;
int i(char ch){
return ch - 'a';
}
void add(char d, char l, char r){
node[i(d)].l = l;
node[i(d)].r = r;
}
void preOrder(char d) {
if('*' != d){
cout << d;
preOrder(node[i(d)].l);
preOrder(node[i(d)].r);
}
}
int main() {
int n;
int flg = 0;
cin >> n;
while(n--) {
char d, l, r;
cin >> d >> l >> r;
if(!flg) {
root = d;
flg = 1;
}
add(d, l, r);
}
preOrder(root);
return 0;
}