#头歌 算法 应用经典二叉树编程-Falling Leaves（中文版）

第1关：Falling Leaves（中文版）

背景

图1显示了字母二叉树的图形表示。熟悉二叉树的人可以跳过字母二叉树、二叉树叶子和字母二叉搜索树的定义，直接进入问题。

字母二叉树可能是以下两种情况之一:

1. 它可能是空的。
2. 它可能有一个根节点。节点以字母作为数据，并指向左子树和右子树。左子树和右子树也是字母二叉树。

在字母二叉树的图形表示中:

1. 空树被完全省略。
2. 每个节点由—1)它的字母数据，2)一条往左到左子树的线段，如果左子树非空，3)如果右子树非空，则往右到右子树的线段。

二叉树中的叶子是子树都为空的节点。在图 1 的示例中，这将是具有数据 B、D、H、P 和 Y 的五个节点。

字母树的前序遍历满足以下定义性质:

1. 如果树为空，则预序遍历为空。
2. 如果树不为空，则预序遍历按顺序由以下内容组成—1)来自根节点的数据，2)对根的左子树进行前序遍历，3)根的右子树的前序遍历。

图 1 中树的预序遍历是 KGCBDHQMPY。

图1所示的树也是字母的二叉搜索树。字母二叉搜索树是一个字母二叉树，其中每个节点满足:

1. 根节点的数据在字母表中的位置比左子树节点中的所有数据都要晚。

2. 根节点的数据比右子树中所有节点的数据更早出现。

题目描述

考虑以下字母二叉搜索树的操作序列

1. 删除叶子并列出删除的数据。
2. 重复此过程，直到树为空。

从下面左边的树开始，我们生成所示的树序列，然后通过删除带有数据的叶子来生成空树。

1. BDHPY
2. CM
3. GQ
4. K

您的问题是从字母二叉搜索树中的这样一行叶子序列开始，并输出树的前序遍历。

输入格式

输入将包含一个或多个数据集。每个数据集都是由一行或多行大写字母组成的序列。 这些行包含在上面描述的阶段中从二叉搜索树中移除的叶子。一行中的字母将按字母顺序递增排列。数据集由仅包含星号(*)的行分隔。 最后一个数据集后面的行只包含一个美元符号($)。输入中没有空格或空行。

输出格式

对于每个输入数据集，都有一个唯一的二叉搜索树，它将产生叶序列。输出是一行，只包含该树的预序遍历，没有空格。

输入输出样例

输入

1. BDHPY
2. CM
3. GQ
4. K
5. *
6. AC
7. B
8. $

输出

1. KGCBDHQMPY
2. BAC

截止后通关代码：

#include<iostream>

#include<cstring>

#include<string>

using namespace std;

struct data{

   

    int l , r;

    char c;

}tree[110];

int cnt = 1;

void insert(int t , char ch){

   

    if(!tree[t].c){

        tree[t].c = ch;

        return;

    }

   

    if(ch < tree[t].c){

       

        if(!tree[t].l){

            tree[++cnt].c = ch;

            tree[t].l = cnt;

        }

        else{

            insert(tree[t].l , ch);

        }

    }

    if(ch > tree[t].c){

       

        if(!tree[t].r){

            tree[++cnt].c = ch;

            tree[t].r = cnt;

        }

        else{

            insert(tree[t].r , ch);

        }

    }

}

void preorder(int t){

   

    if(!tree[t].c){

       

        return;

    }

    cout << tree[t].c;

    preorder(tree[t].l);

    preorder(tree[t].r);

}

int main(){

   

    string s1 , s;

    while(1){

       

        s = "";

        memset(tree , 0 ,sizeof(tree));

        while(cin >> s1 && s1[0] != '*' && s1[0] != '$'){

           

            s += s1;

        }

       

        for(int i = s.length() - 1; i >= 0 ; i --){

           

            insert(1, s[i]);

        }

        preorder(1);

       

        cout << endl;

        if(s1[0] == '$'){

           

            break;

        }

    }

   

}