View Code of Problem 703

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

struct node
{
	char ch;
	int l, r;
}nodePool[10000];

char str[100][100];
int root;
int cnt;
int flag = 1;

void init()
{
	root = 0;
	cnt = root;
	memset(nodePool, 0, sizeof nodePool);
}

int newNodeL(char ch, int par)
{
	cnt++;
	nodePool[par].l = cnt;
	nodePool[cnt].ch = ch;
	return cnt;
}

int newNodeR(char ch, int par)
{
	cnt++;
	nodePool[par].r = cnt;
	nodePool[cnt].ch = ch;
	return cnt;
}

void insert(char ch)
{
	int u = root;
	for (;;)
	{
		if (ch > nodePool[u].ch)
		{
			if (nodePool[u].r != 0)
				u = nodePool[u].r;
			else
			{
				newNodeR(ch, u);
				break;
			}
		}
		else if (ch < nodePool[u].ch)
		{
			if (nodePool[u].l != 0)
				u = nodePool[u].l;
			else
			{
				newNodeL(ch, u);
				break;
			}
		}
	}
}

int input()
{
	int i;
	for (i = 0;; i++)
	{
		scanf("%s", str[i]);
		if (strcmp(str[i], "*") == 0)
			break;
		else if (strcmp(str[i], "$") == 0)
		{
			flag = 0;
			break;
		}
	}
	return i;
}

void create(int layer)
{
	nodePool[root].ch = str[layer - 1][0];
	for (int i = layer - 2; i >= 0; i--)
	{
		for (int j = 0; str[i][j]; j++)
			insert(str[i][j]);
	}
}

void preOrder(int root)
{
	printf("%c", nodePool[root].ch);
	if (nodePool[root].l != 0)
		preOrder(nodePool[root].l);
	if (nodePool[root].r != 0)
		preOrder(nodePool[root].r);
	return;
}

int main(void)
{
	int layer;
	for (;;)
	{
		init();
		layer = input();
		create(layer);
		preOrder(root);
		printf("\n");
		if (flag == 0)
			break;
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 703