openjudge 트리의 변환

관례대로 먼저 제목을 올리다

7: 트리 변환

보기제출 통계질문총 시간 제한:
5000ms 
메모리 제한:
65536kB
묘사
우리는 모두 왼쪽 아들 오른쪽 형제의 방법으로 일반적인 나무 한 그루를 두 갈래 나무로 바꿀 수 있다는 것을 안다. 예를 들어

    0                             0
  / | \                          /
 1  2  3       ===>             1
   / \                           \
  4   5                           2
                                 / \
                                4   3
                                 \
                                  5

이제 일반적인 나무를 이런 방법으로 두 갈래 나무로 바꾸고 전환 전과 전환 후 나무의 높이를 출력해 주십시오.
입력
입력은 여러 줄을 포함하고 마지막 줄은 하나의 #로 끝납니다.
각 줄은 "u"와 "d"로 구성된 문자열로 나무의 깊이가 정보를 우선적으로 검색하는 것을 나타낸다.예를 들어 dudduuudu는 위의 왼쪽 트리를 표시할 수 있습니다. 검색 과정은 0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0이기 때문입니다.
너는 나무마다 결점이 적어도 2이고 10000을 넘지 않는다고 생각할 수 있다.
출력
각 트리의 경우 변환 전과 변환 후 트리 높이를 다음 형식으로 내보냅니다.
Tree t: h1 => h2
그 중에서 t는 나무의 번호(1부터), h1은 전환 전 나무의 높이, h2는 전환 후 나무의 높이이다.
샘플 입력

dudduduudu
ddddduuuuu
dddduduuuu
dddduuduuu
#

샘플 출력

Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4

제목이 나무 한 그루를 묘사하는 방식은 먼저 뿌리를 두루 훑어보는 것이다.아버지의 결점을 저장하고 나무 전체의 뿌리 결점을 눌러 넣는 창고를 설정합니다.스택의 맨 위 끝점은 항상 현재 상위 끝점입니다.입력 문자열을 스캔하여'd'를 만나 창고 꼭대기에서 부결점 FA를 꺼내고 새 결점 SON을 FA의 아들로 연결하여 SON을 창고에 눌러 새로운 부결점으로 준비한다.'u'를 만나 탄창 작업을 실행하고 이전 부결점으로 거슬러 올라갑니다.이 과정에서 창고가 도달할 수 있는 최대 사이즈-1은 나무의 높이이다.

'좌자우형(left child right sibling)'의 규칙에 따라 FA를 위해 아들을 추가할 때 FA->lchild가 비어 있으면 이때 SON은 FA의 첫 아들, FA->lchild=SON, FA->lchild가 비어 있지 않으면 SON은 FA->lchild의 동생으로 FA->lchild 오른쪽 사슬의 맨 끝에 추가해야 한다.

변환된 두 갈래 나무의 높이를 귀속적으로 계산한다.

코드 목록

#include <iostream>
using namespace std;

#include <stack>

#define MAXN 20010

typedef struct _tnode
{
	int info;
	struct _tnode *lmchild;
	struct _tnode *rsibling;
} tnode;

stack<tnode *> rootstack;

tnode *build_bin_tree(char inputseq[], tnode *root, int *max_stack_sz)
{
	char *p=inputseq;
	int val=1;
	tnode *father, *temp, *current;

	while( *p != '\0' )
	{
		if (*p == 'd')	// 
		{
			temp=new tnode;
			temp->info=(val++);
			temp->lmchild=NULL;
			temp->rsibling=NULL;

			father=rootstack.top();

			//temp father ， ， father left-most-child(lmc) ， lmc right sibling ？
			if(father->lmchild == NULL)	// father lmc
			{
				father->lmchild=temp;
			}
			else	// lmc right sibling
			{
				current=father->lmchild;
				while (current->rsibling != NULL)	current=current->rsibling;
				current->rsibling=temp;
			}
			rootstack.push(temp);

			if(rootstack.size() > (*max_stack_sz))	(*max_stack_sz)=rootstack.size();	// 
		}
		else
		{
			rootstack.pop();
		}

		++p;
	}

	return root;
}

int bin_tree_layer(tnode *root)	// 
{
	int left_h, right_h;

	if(root==NULL) return 0;
	else
	{
		left_h = 1 + bin_tree_layer(root->lmchild);
		right_h = 1 + bin_tree_layer(root->rsibling);
		if (left_h > right_h)	return left_h;
		else return right_h;
	}
}

void delete_bin_tree(tnode *root)
{
	if (root != NULL)
	{
		delete_bin_tree(root->lmchild);
		delete_bin_tree(root->rsibling);
		delete root;
		root=NULL;
	}
}

int main()
{
	//freopen("D:\\in.txt", "r", stdin);
	//freopen("D:\\out.txt", "w", stdout);

	tnode *root;
	int max_stack_sz, bt_layers, serial=0;
	char inputseq[MAXN];

	while (1)
	{
		cin.getline(inputseq, MAXN, '
');

		if(inputseq[0] == '#') break;
			
		// 
		++serial;

		root=new tnode;
		root->info=0;
		root->lmchild=NULL;
		root->rsibling=NULL;

		while(!rootstack.empty())	rootstack.pop();
		rootstack.push(root);

		max_stack_sz=1;

		// 
		root = build_bin_tree(inputseq, root, &max_stack_sz);
		bt_layers = bin_tree_layer(root);

		cout<<"Tree "<<serial<<": "<<(max_stack_sz-1)<<" => "<<(bt_layers-1)<<endl;

		// 
		delete_bin_tree(root);
	}

	return 0;
}