タイトル1503:二叉検索ツリーと双方向チェーンテーブル

1705 ワード

タイトルの説明:
ツリーを入力し、ツリーを並べ替えた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力された第1の動作の数n(0出力:
各テストケースに対応して,二叉探索ツリーを並べ替えた双方向チェーンテーブルに変換した後,チェーンテーブルヘッダからチェーンテーブルテールまでの遍歴結果を出力する.
サンプル入力:

1
2 1 0 0 3 0 0

サンプル出力:

1 2 3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int a[1000],cnt;

struct Node
{
	int x;
	struct Node *left;
	struct Node *right;
};

void createTree(Node *&root){
	int x;
	scanf("%d",&x);
	if(!x)
		root = NULL;
	else{
		root = new Node;
		root->x = x;
		createTree(root->left);
		createTree(root->right);
	}
}


void convert(Node *root,Node *&last){
	if(root == NULL)
		return;
	Node *p = root;
	if(p->left != NULL){
		convert(p->left,last);
	}
	p->left = last;
	if(last != NULL)
		last->right = p;
	last = p;
	if(p->right != NULL)
		convert(p->right,last);
}

int main(int argc, char const *argv[])
{
	int n;
	while(scanf("%d",&n) != EOF){
		while(n--){
			Node *root,*head,*last,*p;
			last = NULL;
			createTree(root);
			convert(root,last);
			head = last;
			while(head != NULL && head->left != NULL)
				head = head->left;
			p = head;
			while(p){
				printf("%d ",p->x);
				p = p->right;
			}
			printf("
");
		}
	}
	return 1;
}

タイトル1505:2つのチェーンテーブルの最初の共通ノード-9度

[サーバパフォーマンス向上ストレージ2]キャッシュとRedisの理解