【メモ】二叉木遍歴

二叉木の先序遍歴、中序遍歴、後序遍歴はそれぞれ対応している
先:根左右‖中:左根右‖後:左右根の再帰出力方式
先序中序後序の非常にイメージ的な説明は根と左,右の相対位置関係である.
構造体で二叉木を貯蔵することができます
次のようになります.

struct node {
	int left, right, num;
	//left 
	//right 
	//num p[root]  
};
node p[110];

ツリーを作成した後、出力をどのように検索するかも簡単です.
順を追って繰り返します.

void dfs1 (int root)
{
	if (root == 0)
	return ;
	cout << p[root].num << " "; 
	dfs1 (p[root].left);
	dfs1 (p[root].right);
}

中間パス:

void dfs2 (int root)
{
	if (root == 0)
	return ;
	dfs2 (p[root].left);
	cout << p[root].num << " ";
	dfs2 (p[root].right);
}

後の順序:

void dfs3 (int root)
{
	if (root == 0)
	return ;
	dfs3 (p[root].left);
	dfs3 (p[root].right);
	cout << p[root].num << " ";
}

出力プログラムの位置は,左右の息子再帰関数呼び出しの相対位置と遍歴順序におけるルートと左右の順序と一致することがわかる.
それでは例題です
タイトルリンク

タイトルの説明:

すでに1本の二叉木を知っていて、それぞれその先序のカレンダーを求めて、中序のカレンダー、後序のカレンダー(結点数N<=100)
 

入力形式:

1行目の木の結点の個数、2行目から、1行ごとに3つの数、1つ目の数は結点で、2つ目の数は左の子供で、3つ目の数は右の子供で、0は左の子供あるいは右の子供が存在しないことを表します
 

出力フォーマット:

第1行先順編暦、第2行中順編暦、第3行後順編暦、数と数の間にスペースがある
 

サンプル入力:

5
1 2 3
2 4 5
3 0 0
4 0 0
5 0 0

 

サンプル出力:

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

とても裸のテンプレートの問題です
ACコードに直接接続します.

#include 
using namespace std;

struct node {
	int left, right, num;
	//left 
	//right 
	//num p[root]  
};
node p[110];

int n;

void dfs1 (int root)
{
	if (root == 0)
	return ;
	cout << p[root].num << " "; 
	dfs1 (p[root].left);
	dfs1 (p[root].right);
}

void dfs2 (int root)
{
	if (root == 0)
	return ;
	dfs2 (p[root].left);
	cout << p[root].num << " ";
	dfs2 (p[root].right);
}

void dfs3 (int root)
{
	if (root == 0)
	return ;
	dfs3 (p[root].left);
	dfs3 (p[root].right);
	cout << p[root].num << " ";
}

int main ()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		p[i].num = i;
		int a, b, c;
		cin >> a >> b >> c;
		p[a].left = b;
		p[a].right = c;
	}
	dfs1 (1);
	cout << endl;
	dfs2 (1);
	cout << endl;
	dfs3 (1);
}