課題をといてみる。

例のごとくです。
課題→ここ

課題81はスタック作ればおっけーなんで省略ー。

課題82

これはちょいとスマートな方法を思いつかんかったわ...。
とりあえず俺が思いついた方法は

// とりあえずroot積んでおく。
stack.push( root );					/* ...(甲) */
// スタックに要素がある限り
while( !empty() ) {
	// 要素をpopする
	tmp = stack.pop();				/* ...(乙) */
	if( /* tmpは既に処理したか? */ ) {
		// tmpはすでに処理したならプリントする
		printf( /* ほげほげ */ );		/* ...(丙) */
	} else {
		// tmpがまだ未処理
		if( /* 右があるか? */ ) {
			// あるならつむ。
			stack.push( tmp.right );	/* ...(丁) */
		}

		/* tmpは既に処理した、と情報を加える */
		// スタックに積む。
		stack.push( tmp );			/* ...(戊) */

		if( /* 左があるか? */ ) {
			// あるならつむ。
			stack.push( tmp.left );		/* ...(己) */
		}
	}
}

こんな感じ。

具体例で説明すると

    6
  4   8
1 5 7 9

こんなツリーを考えます。
すると(甲〜己はソースコード中のそれ、stackの"[x]"はxは処理済みであることをしめす。

手順	stack	出力
甲) とりあえずroot(=6)を積む。	6
乙) さっそくその6をpopする。
丁) 右があるので、右(=8)を積む。	8
戊) 6を処理済みにして、積む。	8 [6]
己) 左があるので、左(=4)を積む。	8 [6] 4
乙) popして4を得る。	8 [6]
丁) 右があるので、右(=5)を積む。	8 [6] 5
戊) 4を処理済みにして、積む。	8 [6] 5 [4]
己) 左があるので、左(=1)を積む。	8 [6] 5 [4] 1
乙) popして1を得る。	8 [6] 5 [4]
戊) 1を処理済みにして、積む。	8 [6] 5 [4] [1]
乙) popして[1]を得る。	8 [6] 5 [4]
丙) [1]は処理済みなので出力する。	8 [6] 5 [4]	1
乙) popして[4]を得る。	8 [6] 5	1
丙) [4]は処理済みなので出力する。	8 [6] 5	1 4
乙) popして5を得る。	8 [6]	1 4
戊) 5を処理済みにして、積む。	8 [6] [5]	1 4
乙) popして[5]を得る。	8 [6]	1 4
丙) [5]は処理済みなので出力する。	8 [6]	1 4 5
乙) popして[6]を得る。	8	1 4 5
丙) [6]は処理済みなので出力する。	8	1 4 5 6

まぁ、あとは繰り返しなので略。
ちゃんとtraverseと同じ順になってると思います。
とりあえず文章読むよりはstackの遷移を眺めるといいかも。

んー、他にいい方法ないかねぇ...。

課題83

続いてqsort。
これはキューを使えばおっけー。
前にやったqsortを理解できた人は苦ではないはず。
逆に言えばqsortを理解できなかった人はこれもきついかも。

とりあえず、「ソートする範囲」を一つの構造体にして、その構造体のキューを作るといい感じ。
「ソートする範囲」の中からピボットを拾ってきて、それをもとに、「小さいの」と「大きいの」にわけてそれぞれの範囲を構造体に打ち込んでキューにいれる。
あとは、ループ入る前に、配列の全範囲をキューに入れてあげて、ループ先頭ではキューからとる、という作業をしてやればおっけー。

あ、スタックでもいいのか。

なんか全体的に簡素なのはうちのモチベーションが低いからとか、そういうのじゃないですよ。
えぇ、そうですとも。