`
xinjiang
  • 浏览: 55478 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

POJ 1577--Falling Leaves

Go 
阅读更多

题目来源:http://poj.org/problem?id=1577

Description:


Figure 1

Figure 1 shows a graphical representation of a binary tree of letters. People familiar with binary trees can skip over the definitions of a binary tree of letters, leaves of a binary tree, and a binary search tree of letters, and go right to The problem .
A binary tree of letters may be one of two things:
  1. It may be empty.
  2. It may have a root node. A node has a letter as data and refers to a left and a right subtree. The left and right subtrees are also binary trees of letters.

In the graphical representation of a binary tree of letters:
  1. Empty trees are omitted completely.
  2. Each node is indicated by
    • Its letter data,
    • A line segment down to the left to the left subtree, if the left subtree is nonempty,
    • A line segment down to the right to the right subtree, if the right subtree is nonempty.

A leaf in a binary tree is a node whose subtrees are both empty. In the example in Figure 1, this would be the five nodes with data B, D, H, P, and Y.

The preorder traversal of a tree of letters satisfies the defining properties:
  1. If the tree is empty, then the preorder traversal is empty.
  2. If the tree is not empty, then the preorder traversal consists of the following, in order
    • The data from the root node,
    • The preorder traversal of the root's left subtree,
    • The preorder traversal of the root's right subtree.

The preorder traversal of the tree in Figure 1 is KGCBDHQMPY.

A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies:

The root's data comes later in the alphabet than all the data in the nodes in the left subtree.

The root's data comes earlier in the alphabet than all the data in the nodes in the right subtree.
The problem:

Consider the following sequence of operations on a binary search tree of letters Remove the leaves and list the data removed Repeat this procedure until the tree is empty Starting from the tree below on the left,  we produce the sequence of trees shown, and then the empty tree

by removing the leaves with data BDHPY CM GQ K Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree.

Input:

The input file will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters. The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk ('*'). The last data set is followed by a line containing only a dollar sign ('$'). There are no blanks or empty lines in the input.

Output:

For each input data set, there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree, with no blanks.

Example Input:

BDHPY 
CM 
GQ 
K 
* 
AC 
B 
$

Example Output:

KGCBDHQMPY
BAC

此题就是就是建立一颗有序二叉树,在进行前序遍历即可得到结果。对于第一组数据KGQCMBDHPY建立一颗有序二叉树,
过程如下:

#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct BiTree
{
    /*自定义二叉树*/
    char ch;
    struct BiTree *lchild;
    struct BiTree *rchild;
}BiTree;


BiTree *createBiTree(char ch)
{
    /*创建一个叶子节点*/
    BiTree *leaf = (BiTree *)malloc(sizeof(BiTree));
    leaf->ch = ch;
    leaf->lchild = NULL;
    leaf->rchild = NULL;
    return leaf;
}


BiTree *insertBiTree(BiTree *root, char ch)
{
    BiTree *leaf = root;

    if(root == NULL)
    {
        root = createBiTree(ch);
        return root;
    }

    while(leaf)
    {
        if((leaf->ch) > ch)
        {
            if(leaf->lchild == NULL)  //如果ch比该节点小且该节点的左子树为空
            {                         //就将ch放在该节点的左子树上
                leaf->lchild = createBiTree(ch);
                break;
            }
            else                     //否则继续遍历直到找到合适的位置位置
            {
                leaf = leaf->lchild;
            }
        }
        else  if((leaf->ch) < ch)
        {
            if(leaf->rchild == NULL)  //如果ch比该节点大且该节点的右子树为空
            {                         //就将ch放在该节点的右子树上
                leaf->rchild = createBiTree(ch);
                break;
            }
            else                      //否则继续遍历直到找到合适的位置位置
            {
                leaf = leaf->rchild;
            }
        }
    }

    return root;
}

void preOrderTraver(BiTree *root)
{
    /*前序遍历二叉树,并且输出结果*/
    BiTree *p, *stack[100];
    int top = 0;

    p = root;
    while(!(p == NULL && top == 0))
    {
        while(p != NULL)
        {
            stack[top] = p;   //将当前指针压入栈中
            top++;
            printf("%c", p->ch);
            p = p->lchild;
        }

        if(top <= 0)  return;   //栈空时结束
        else
        {
            top--;
            p = stack[top];
            p = p->rchild;
        }
    }

}

int main()
{
    char str[50], p[10000];
    int length;
    int i;
    BiTree *root = NULL;


    while(1)
    {
        scanf("%s", str);
        if(strcmp(str, "*") == 0 || strcmp(str, "$") == 0)
        {
            length = strlen(p);
            for(i = length-1; i >= 0; i--)
            {
               root = insertBiTree(root, p[i]);
            }
            preOrderTraver(root);
            printf("\n");
            if(strcmp(str, "$") == 0)  break;
            root = NULL;
            memset(p, '\0', sizeof(p));

        }
        else
        {
            strcat(p, str);
        }
    }

    return 0;
}
 

 

  • 大小: 57 KB
分享到:
评论

相关推荐

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ3020-Antenna Placement

    【标题】"POJ3020-Antenna Placement"是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战了参赛者在算法设计和实现上的能力。 【描述】"解题报告+AC代码"意味着这...

    poj 1000 - 2000 部分题目 官方分类

    《POJ 1000 - 2000 部分题目 官方分类》 编程竞赛,特别是在线判题系统(如POJ,即Problem Online Judge)中的题目,是提升编程技能和算法理解的重要途径。POJ 1000 - 2000 是一个涵盖广泛的题目区间,包含了大量的...

    魔兽世界终极版POJ的-测试数据

    这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q

    POJ2299-Ultra-QuickSort

    【标题】"POJ2299-Ultra-QuickSort"是北京大学在线判题系统POJ上的一道编程题目,其主要涉及的算法是快速排序(Ultra-QuickSort)。快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    POJ1258-Agri-Net【Prim】

    【标题】"POJ1258-Agri-Net【Prim】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到图论中的一个重要算法——普里姆(Prim)算法。 【描述】"北大POJ1258-...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    POJ3414-Pots

    标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...

    POJ2525-Text Formalization【TrieTree】

    《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...

    POJ2503-Babelfish

    【标题】"POJ2503-Babelfish"是一个来自北京大学在线判题系统(POJ,Problem Online Judge)的编程题目。该题目要求参赛者编写程序解决特定的算法问题,通过编程语言实现,然后提交代码以供系统自动评测。 【描述】...

    POJ1003-Hangover

    【标题】"POJ1003-Hangover"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这类题目通常要求参赛者编写程序来解决特定的算法问题,以此锻炼和测试编程技能及算法理解能力。 【描述...

    POJ1009-Edge Detection

    【标题】"POJ1009 - 边缘检测" 在计算机图形学与图像处理领域,边缘检测是一项至关重要的技术。北京大学编程平台POJ上的第1009题,"Edge Detection"(边缘检测),旨在让学生通过编程实现对图像进行边缘检测。此题...

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    POJ3122-Pie

    【标题】"POJ3122-Pie"是一道来自北京大学在线判题系统POJ(Problem Online Judge)的编程题目。这道题目通常被用于训练程序员的数据结构和算法技能,特别是解决数学问题的能力。在编程竞赛或者算法训练中,这类题目...

    POJ1002-487-3279【Hash+Qsort】

    标题中的"POJ1002-487-3279【Hash+Qsort】"是指一个编程挑战题目,通常在在线编程平台上出现,比如北京大学的Peking Online Judge (POJ)。这个题目结合了哈希表(Hash)和快速排序(Qsort)两种算法来解决问题。哈希...

    POJ1007-DNA Sorting

    【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...

    POJ3295-Tautology

    【标题】"POJ3295-Tautology"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是逻辑推理和算法实现能力。 【描述】"北大POJ3295-Tautology 解题报告+AC代码"意味...

Global site tag (gtag.js) - Google Analytics