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:
- It may be empty.
- 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:
- Empty trees are omitted completely.
- 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:
- If the tree is empty, then the preorder traversal is empty.
- 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:
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 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
poj 1000-3000部分代码 网上收集
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3