题目描述

输入一串二叉树，输出其前序遍历。

输入格式

第一行为二叉树的节点数 n。(1≤n≤26)

后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用 * 表示

输出格式

二叉树的前序遍历。

输入样例

6
abc
bdi
cj*
d**
i**
j**

输出样例

abdicj

解法

误区

一开始想写一个递归查找算法，利用递归查找算法进行插入，再写一个递归遍历算法，但是后来发现它可能是不按顺序给出的节点，也就是可能按顺序读取会产生若干棵树，到最后才连起来

思路

因为根节点肯定不会是其他节点的子节点，所以可以先读取所有的节点信息，找到根节点，再递归建立整棵树

代码

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct node{
        char data;
        node* left;
        node* right; 
        }node;
        
int n=0;        
char nodeInfo[27][3]={};

void build(node* root){
     int i=0;
     for(i=1;i<=n;i++){
             if(nodeInfo[i][0]==root->data)
                break;
             }
     root->left=NULL;
     root->right=NULL;
     if(nodeInfo[i][1]!='*'){
             node * templeft=(node*)malloc(sizeof(node));
             templeft->data=nodeInfo[i][1];
             root->left=templeft;
             build(templeft);
             }
     if(nodeInfo[i][2]!='*'){
             node * tempright=(node*)malloc(sizeof(node));
             tempright->data=nodeInfo[i][2];
             root->right=tempright;
             build(tempright);
             }
     }

void preOrder(node* root){
     if(root==NULL)
         return;
     cout<<root->data;
     preOrder(root->left);
     preOrder(root->right); 
     }

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
            cin>>nodeInfo[i][0]>>nodeInfo[i][1]>>nodeInfo[i][2];
            }
    node* root=(node*)malloc(sizeof(node));
    for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                    if(nodeInfo[i][0]==nodeInfo[j][1]||nodeInfo[i][0]==nodeInfo[j][2])
                          break;
                    if(j==n)
                          root->data=nodeInfo[i][0];
                    } 
            }
    build(root); 
    preOrder(root);
    return 0;
    }