EvbCFfp1XB

problem and my answer.

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++
 */

public class Chapter6PrinciplesofAlgorithmAnalysis {
public static void main(String[] args) {
// problem1();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
// problem9();
problem10();
}

/**
* 1. あるアルゴリズムの実行時間がO(NlogN)であり、別のアルゴリズムの実行時間はO(N^3)であるとする.
* このことから2つのアルゴリズムの性能についてどのようなことがいえるか?
*/
static void problem1() {
System.out.println("1. 上界にすぎない。");
System.out.println("2. 最悪の場合の入力が実際には現れそうにないかもしれない。");
System.out.println("3. 定数c0はわからない。");
System.out.println("4. 定数N0はわからない。");
}

/**
* 2. あるアルゴリズムの実行時間が常に約NlogNであり、別のアルゴリズムの実行時間はO(N^3)であるとする.
* このことから2つのアルゴリズムの性能についてどのようなことがいえるか?
*/
static void problem2() {
System.out.println("1. 上界にすぎない。");
System.out.println("2. 最悪の場合の入力が実際には現れそうにないかもしれない。");
System.out.println("3. 定数c0はわからない。");
System.out.println("4. 定数N0はわからない。");
}

/**
* 3. あるアルゴリズムの実行時間が常に約NlogNであり、別のアルゴリズムの実行時間は常にN^3であるとする.
* このことから2つのアルゴリズムの性能についてどのようなことがいえるか?
*/
static void problem3() {
System.out.println("約NlogNのアルゴリズムの方が早いだろう。");
}

/**
* 4. O(1)とO(2)の差は何か.
*/
static void problem4() {
System.out.println("差はない。");
}

/**
* 5. 次の漸化式を解け.ここでNは2のべき乗の数とする. CN=C(N/2)+N^2 (N>=2) C1=0
*/
static void problem5() {
System.out.println("n=lgN");
System.out.println("CN=C(N/2)+N^2");
System.out.println("=C(N/4)+(N/2)^2+N^2");
System.out.println("...");
System.out.println("=C1+(2)^2+...+(N/2)^2+N^2");
System.out.println("=0+(2)^2+...+(N/2)^2+N^2");
System.out.println("CN + 1=1+(2)^2+...+(N/2)^2+N^2");
System.out.println("CN + 1=1+4+16+...+4^n");
System.out.println("CN + 1=(4^(n+1)-1)/3");

int N = (int) Math.pow(2, 26);
System.out.format("%f\n%f\n",
(Math.pow(4, Math.log(N) / Math.log(2) + 1) - 1) / 3,
Cproblem5(N));
}

private static double Cproblem5(double N) {
if (N == 1) {
return 0;
}
return Cproblem5(N / 2) + N * N;
}

/**
* 6. 10NlgN>2N^2になるNの値を示せ.
*/
static void problem6() {
for (int N = 0; N <= 10000; N++) {
if (10 * N * Math.log(N) / Math.log(2) > 2 * N * N) {
System.out.println(N);
}
}
}

/**
* 7. 漸化式2でCNの正確な値を計算するプログラムを書け.5章を参照のこと.その結果をlgNと比較せよ.
*/
static void problem7() {
for (int N = 1; N <= 10; N++) {
// int N = (int) Math.pow(2, n);
System.out.format("lg%d=%f, C%d=%f\n", N,
Math.log(N) / Math.log(2), N, Cproblem7(N));
}
}

private static double Cproblem7(int N) {
// System.out.format("%d : %s\n", N, Integer.toString(N, 2));
if (N == 1) {
return 0;
}
return Cproblem7(N / 2) + 1;
}

/**
* 8. 漸化式2の正確な解はlgN+O(1)であることを証明せよ.
*/
static void problem8() {
System.out.println("漸化式2ではNの2進数の最も大きい桁以外は結果に影響しない.\n"
+ "lgNは単調増加よりNの2進数の最も大きい桁以外が1であればlgNは増加する.\n"
+ "よって漸化式2==(int)lgN.\n" + "切り捨てられた値<1より 漸化式2=lgN+O(1).\n");
}

/**
* 9. log2(N)より大きくない最大の整数を計算する再帰プログラムを書け.(ヒント:N>1として、N/2に対するこの関数の値は、
* Nに対する値より1小さい.)
*/
static void problem9() {
for (int i = 1; i <= 100; i++) {
System.out.format("%d : %f, %d\n", i, Math.log(i) / Math.log(2),
fproblem9(i));
}
}

private static int fproblem9(int n) {
if (n == 1) {
return 0;
}
return fproblem9(n / 2) + 1;
}

/**
* 10. 上の問題に対する繰り返し型のプログラムを書け.
*/
static void problem10() {
for (int i = 1; i <= 100; i++) {
System.out.format("%d : %f, %d\n", i, Math.log(i) / Math.log(2),
fproblem10(i));
}
}

private static int fproblem10(int i) {
double d = Math.log(i) / Math.log(2);
for (int j = 0;; j++) {
if (j <= d) {
} else {
return j - 1;
}
}
}
}

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++
*/

import java.util.Stack;

public class Chapter5Recursion {
public static void main(String[] args) {
// problem1();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
// problem9();
problem10();
}

/**
* 1. 2分木を描くのに、まず根を頁の中心線上に描き、左部分木の根を頁の左半分の中心線上に書くというような再帰プログラムを書け.
*/
static void problem1() {
Node E = new Node("E");
{
Node O = new Node("O");
E.l = O;
{
Node _ = new Node(" ");
O.l = _;
Node A = new Node("A");
_.l = A;
Node C = new Node("C");
_.r = C;
}
{
Node P = new Node("P");
O.r = P;
Node M = new Node("M");
P.l = M;
Node L = new Node("L");
P.r = L;
}
}
{
Node T = new Node("T");
E.r = T;
{
Node E2 = new Node("E");
T.l = E2;
Node T2 = new Node("T");
E2.l = T2;
Node _ = new Node(" ");
E2.r = _;
}
{
Node E3 = new Node("E");
T.r = E3;
Node R = new Node("R");
E3.l = R;
Node E4 = new Node("E");
E3.r = E4;
}
}

drawNode(E, 0, 1);
}

private static void drawNode(Node e, double l, double r) {
if (e != null) {
double center = (l + r) / 2;
System.out.format("draw Node\"%s\" at %f\n", e.info, center);
drawNode(e.l, l, center);
drawNode(e.r, center, r);
}
}

static class Node {
public Node(String string) {
this.info = string;
}

String info;
Node l;
Node r;
int x;
int y;
}

/**
* 2. 2分木の外部道長を計算する再帰プログラムを書け.
*/
static void problem2() {
Node E = new Node("E");
{
Node O = new Node("O");
E.l = O;
{
Node _ = new Node(" ");
O.l = _;
Node A = new Node("A");
_.l = A;
Node C = new Node("C");
_.r = C;
}
{
Node P = new Node("P");
O.r = P;
Node M = new Node("M");
P.l = M;
Node L = new Node("L");
P.r = L;
}
}
{
Node T = new Node("T");
E.r = T;
{
Node E2 = new Node("E");
T.l = E2;
Node T2 = new Node("T");
E2.l = T2;
Node _ = new Node(" ");
E2.r = _;
}
{
Node E3 = new Node("E");
T.r = E3;
Node R = new Node("R");
E3.l = R;
Node E4 = new Node("E");
E3.r = E4;
}
}

System.out.println(externalPathLength(E, 0));
}

private static int externalPathLength(Node e, int level) {
if (e == null) {
return level;
}

return externalPathLength(e.l, level + 1)
+ externalPathLength(e.r, level + 1);
}

/**
* 3. 2分木で表現された木において、その外部道長を計算する再帰プログラムを書け.
*/
static void problem3() {
Node E = new Node("E");
{
Node A = new Node("A");
E.l = A;
{
Node A2 = new Node("A");
A.l = A2;
Node S = new Node("S");
A2.r = S;
}
{
Node R = new Node("R");
A.r = R;
Node E2 = new Node("E");
R.r = E2;
{
Node T = new Node("T");
R.l = T;
Node M = new Node("M");
T.l = M;
Node P = new Node("P");
M.r = P;
Node L = new Node("L");
P.r = L;
Node E3 = new Node("E");
L.r = E3;
}
}
}

System.out.println(externalPathLength(E, 0));
}

/**
* 4. 本文中の木を描く再帰手続きを図4.2の2分木に適用したとき、それで計算される座標を示せ.
*/
static void problem4() {
Node P = new Node("P");
{
Node M = new Node("M");
P.l = M;
{
Node S = new Node("S");
M.l = S;
Node A = new Node("A");
S.l = A;
Node A2 = new Node("A");
S.r = A2;
}
}
{
Node L = new Node("L");
P.r = L;
{
Node E = new Node("E");
L.r = E;
{
Node R = new Node("R");
E.r = R;
Node T = new Node("T");
R.l = T;
{
Node E2 = new Node("E");
R.r = E2;
Node E3 = new Node("E");
E2.l = E3;
}
}
}
}

traverseproblem4(P);
}

static int xproblem4 = 0;
static int yproblem4 = 0;

private static void traverseproblem4(Node e) {
if (e != null) {
yproblem4++;
traverseproblem4(e.l);
e.x = ++xproblem4;
e.y = yproblem4;
System.out.format("%s : (%d, %d)\n", e.info, e.x, e.y);
traverseproblem4(e.r);
yproblem4--;
}
}

/**
* 5. 本文中のfibonacciプログラムから再帰呼び出しを機械的に除去して、非再帰的なプログラムを実現せよ.
*/
static void problem5() {
int n = 35;
System.out.format("%d\n", fibonacci(n));
System.out.format("%d\n", fibonacciproblem5(n));
}

private static int fibonacci(int n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

private static int fibonacciproblem5(int n) {
Stack<Integer> stack2 = new Stack<Integer>();
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> v = new Stack<Integer>();
while (true) {
if (n <= 1) {
v.push(1);
while (!stack.isEmpty()) {
n = stack.pop();
int a = v.pop();
int b = v.pop();
v.push(a + b);
}
if (stack2.isEmpty()) {
return v.pop();
}
n = stack2.pop();

stack.push(n);
n = n - 2;
continue;
}

stack2.push(n);
n = n - 1;
}
}

/**
* 6. 木走査の再帰中央順のものから再帰呼び出しを機械的に除去して非再帰的なプログラムを実現せよ.
*/
static void problem6() {
Node P = new Node("P");
{
Node M = new Node("M");
P.l = M;
{
Node S = new Node("S");
M.l = S;
Node A = new Node("A");
S.l = A;
Node A2 = new Node("A");
S.r = A2;
}
}
{
Node L = new Node("L");
P.r = L;
{
Node E = new Node("E");
L.r = E;
{
Node R = new Node("R");
E.r = R;
Node T = new Node("T");
R.l = T;
{
Node E2 = new Node("E");
R.r = E2;
Node E3 = new Node("E");
E2.l = E3;
}
}
}
}

traverseInorder2(P);
System.out.println();
traverseInorder(P);
System.out.println();
}

private static void traverseInorder(Node e) {
Stack<Node> stack = new Stack<Node>();
while (e != null) {
stack.push(e);
e = e.l;
}
while (!stack.isEmpty()) {
e = stack.pop();
System.out.format("%s", e.info);
e = e.r;
while (e != null) {
stack.push(e);
e = e.l;
}
}
}

private static void traverseInorder2(Node e) {
if (e != null) {
traverseInorder2(e.l);
System.out.format("%s", e.info);
traverseInorder2(e.r);
}
}

/**
* 7. 木走査の再帰後行順のものから再帰呼び出しを機械的に除去して非再帰的なプログラムを実現せよ.
*/
static void problem7() {
Node E = new Node("E");
{
Node O = new Node("O");
E.l = O;
{
Node _ = new Node(" ");
O.l = _;
Node A = new Node("A");
_.l = A;
Node C = new Node("C");
_.r = C;
}
{
Node P = new Node("P");
O.r = P;
Node M = new Node("M");
P.l = M;
Node L = new Node("L");
P.r = L;
}
}
{
Node T = new Node("T");
E.r = T;
{
Node E2 = new Node("E");
T.l = E2;
Node T2 = new Node("T");
E2.l = T2;
Node _ = new Node(" ");
E2.r = _;
}
{
Node E3 = new Node("E");
T.r = E3;
Node R = new Node("R");
E3.l = R;
Node E4 = new Node("E");
E3.r = E4;
}
}

traversePostorder2(E);
System.out.println();
traversePostorder(E);
System.out.println();
}

private static void traversePostorder(Node e) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while (true) {
if (e == null) {
if (stack2.isEmpty()) {
break;
}
Node old = null;
while (!stack2.isEmpty()) {
e = stack2.pop();
if (e.r == old) {
System.out.format("%s", e.info);
} else {
stack2.push(e);
break;
}
old = e;
}
e = null;
} else {
while (e != null) {
stack.push(e);
e = e.l;
}
}
if (!stack.isEmpty()) {
e = stack.pop();
stack2.push(e);
e = e.r;
}
}
}

private static void traversePostorder2(Node e) {
if (e != null) {
traversePostorder2(e.l);
traversePostorder2(e.r);
System.out.format("%s", e.info);
}
}

/**
* 8. 平面上の2点(x1,y1),(x2,y2)を結ぶ線分をなるべく上手に描く分割統治の再帰プログラムを書け.ただし、
* 座標が整数値の点だけに描くことができるものとする.(ヒント:最初真ん中辺りの点を描け.)
*/
static void problem8() {
int x1 = 0;
int y1 = 0;
int x2 = 3;
int y2 = 1;
draw(x1, y1, x2, y2);
}

private static void draw(int x1, int y1, int x2, int y2) {
int x3 = (x1 + x2) / 2;
int y3 = (y1 + y2) / 2;
if (x1 == x3 && y1 == y3) {
System.out.format("draw line from (%d, %d) to (%d, %d)\n", x1, y1,
x2, y2);
return;
}
draw(x1, y1, x3, y3);
draw(x3, y3, x2, y2);
}

/**
* 9. ジョセファス問題を解く再帰プログラムを書け.
*/
static void problem9() {
// 5 1 7 4 3 6 9 2 8
int n = 9;
int m = 5;

Node2 x;
Node2 t = new Node2("1");
x = t;
for (int i = 2; i <= n; i++) {
t.next = new Node2("" + i);
t = t.next;
}
t.next = x;

// josephus(t, x, n, m);
josephusRecursive(t, x, n, m);
}

private static void josephusRecursive(Node2 t, Node2 x, int n, int m) {
if (t == t.next) {
System.out.print(t.key + "\n");
return;
}
for (int i = 1; i < m; i++) {
t = t.next;
}
System.out.print(t.next.key + " ");
x = t.next;
t.next = x.next;
josephusRecursive(t, x, n, m);
}

private static void josephus(Node2 t, Node2 x, int n, int m) {
for (; t != t.next;) {
for (int i = 1; i < m; i++) {
t = t.next;
}
System.out.print(t.next.key + " ");
x = t.next;
t.next = x.next;
}
System.out.print(t.key + "\n");
}

static class Node2 {
public Node2(String string) {
this.key = string;
}

String key;
Node2 next;
}

/**
* 10. ユークリッドのアルゴリズムを再帰的に実現せよ.
*/
static void problem10() {
System.out.format("%d\n", gcd(12345, 56789));
System.out.format("%d\n", gcdRecursive(12345, 56789));
}

private static int gcdRecursive(int x, int y) {
if (x < y) {
return gcdRecursive(y, x);
}
if (y != 0) {
return gcdRecursive(y, x % y);
}
return x;
}

private static int gcd(int x, int y) {
int t;
while (x > 0) {
if (x < y) {
t = x;
x = y;
y = t;
}
x %= y;
}
return y;
}
}

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++
 */

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Chapter4Trees {
public static void main(String[] args) {
// problem1();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
// problem9();
problem10();
}

/**
* 1. 図4.3の木について、先行順、中央順、後行順、レベル順のそれぞれによって、節点に訪れる順番を示せ。
*/
static void problem1() {
Node E = new Node("E");
{
Node O = new Node("O");
E.l = O;
{
Node _ = new Node(" ");
O.l = _;
Node A = new Node("A");
_.l = A;
Node C = new Node("C");
_.r = C;
}
{
Node P = new Node("P");
O.r = P;
Node M = new Node("M");
P.l = M;
Node L = new Node("L");
P.r = L;
}
}
{
Node T = new Node("T");
E.r = T;
{
Node E2 = new Node("E");
T.l = E2;
Node T2 = new Node("T");
E2.l = T2;
Node _ = new Node(" ");
E2.r = _;
}
{
Node E3 = new Node("E");
T.r = E3;
Node R = new Node("R");
E3.l = R;
Node E4 = new Node("E");
E3.r = E4;
}
}

traversePreorder2(E);
System.out.println();
traversePreorder(E);
System.out.println();
traverseInorder2(E);
System.out.println();
traverseInorder(E);
System.out.println();
traversePostorder2(E);
System.out.println();
traversePostorder(E);
System.out.println();
traverseLevelorder(E);
System.out.println();
}

private static void traversePreorder(Node e) {
Stack<Node> stack = new Stack<Node>();
stack.push(e);
for (; !stack.isEmpty();) {
Node pop = stack.pop();
System.out.format("%s", pop.info);
if (pop.r != null) {
stack.push(pop.r);
}
if (pop.l != null) {
stack.push(pop.l);
}
}
}

private static void traversePreorder2(Node e) {
if (e != null) {
System.out.format("%s", e.info);
traversePreorder2(e.l);
traversePreorder2(e.r);
}
}

private static void traverseInorder(Node e) {
Stack<Node> stack = new Stack<Node>();
while (e != null) {
stack.push(e);
e = e.l;
}
while (!stack.isEmpty()) {
e = stack.pop();
System.out.format("%s", e.info);
e = e.r;
while (e != null) {
stack.push(e);
e = e.l;
}
}
}

private static void traverseInorder2(Node e) {
if (e != null) {
traverseInorder2(e.l);
System.out.format("%s", e.info);
traverseInorder2(e.r);
}
}

private static void traversePostorder(Node e) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
l: while (true) {
if (e == null) {
if (stack2.isEmpty()) {
break;
}
Node old = null;
while (!stack2.isEmpty()) {
e = stack2.pop();
if (e.r == old) {
System.out.format("%s", e.info);
} else {
stack2.push(e);
break;
}
old = e;
}
e = null;
} else {
while (e != null) {
stack.push(e);
e = e.l;
}
}
while (!stack.isEmpty()) {
e = stack.pop();
stack2.push(e);
e = e.r;
continue l;
}
}
}

private static void traversePostorder2(Node e) {
if (e != null) {
traversePostorder2(e.l);
traversePostorder2(e.r);
System.out.format("%s", e.info);
}
}

private static void traverseLevelorder(Node e) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(e);
for (; !queue.isEmpty();) {
Node p = queue.poll();
System.out.format("%s", p.info);
if (p.l != null) {
queue.add(p.l);
}
if (p.r != null) {
queue.add(p.r);
}
}
}

static class Node {
public Node(String string) {
this.info = string;
}

String info;
Node l;
Node r;
}

/**
* 2. N個の節点を持つ完全4分木の高さは何か.
*/
static void problem2() {
int N = 1234;
int a = 4;
int height = height(a, N);
System.out.format("%d(N) < %d(3*N+1) <= %d(Math.pow(4, height))\n", N,
3 * N + 1, (int) Math.pow(4, height));
System.out.format("%f(log(N)) < %f(log(3*N+1)) <= %d(2*height)\n",
log2(N), log2(3 * N + 1), 2 * height);
System.out.format(
"%f(log(N) / 2) < %f(log(3*N+1) / 2) <= %d(height)\n",
log2(N) / 2d, log2(3 * N + 1) / 2d, height);
System.out.format("height は約 log(N) / 2\n");
}

private static double log2(int N) {
return Math.log(N) / Math.log(2);
}

private static int height(int a, int n) {
int height = 0;
int count = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
for (; !queue.isEmpty();) {
height = queue.poll();
count++;
if (count >= n) {
break;
}
for (int i = 0; i < a; i++) {
queue.add(height + 1);
}
}
return height;
}

/**
* 3. 式(A+B)*C+(D+E)の解析木を描け.
*/
static void problem3() {
String s = "(((A+B)*C)+(D+E))";
String postfix = infix2postfix(s);
Node n = parse(postfix);
tree(n, 0);
}

private static String infix2postfix(String s) {
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ')') {
sb.append(stack.pop());
} else if (c == '(') {
} else if (c == '+') {
stack.push(c);
} else if (c == '*') {
stack.push(c);
} else {
sb.append(c);
}
}
return sb.toString();
}

private static Node parse(String s) {
Stack<Node> stack = new Stack<Node>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '+' || c == '*') {
Node node = new Node("" + c);
node.r = stack.pop();
node.l = stack.pop();
stack.push(node);
} else {
stack.push(new Node("" + c));
}
}
return stack.pop();
}

private static void tree(Node n, int indent) {
if (n == null) {
return;
}
System.out.format("%" + (1 + indent) + "s\n", n.info);
tree(n.l, indent + 1);
tree(n.r, indent + 1);
}

/**
* 4. 図4.2の木を森とみなして、それを2分木で表現した図を描け.
*/
static void problem4() {
Node P = new Node("P");
{
Node M = new Node("M");
P.l = M;
{
Node S = new Node("S");
M.l = S;
Node A = new Node("A");
S.l = A;
Node A2 = new Node("A");
S.r = A2;
}
}
{
Node L = new Node("L");
P.r = L;
{
Node E = new Node("E");
L.r = E;
{
Node R = new Node("R");
E.r = R;
Node T = new Node("T");
R.l = T;
{
Node E2 = new Node("E");
R.r = E2;
Node E3 = new Node("E");
E2.l = E3;
}
}
}
}

traverseLevelorderproblem4(P);
}

private static void traverseLevelorderproblem4(Node e) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(e);
for (; !queue.isEmpty();) {
Node p = queue.poll();
tree(p, 0);
if (p.l != null) {
queue.add(p.l);
}
if (p.r != null) {
queue.add(p.r);
}
}
}

/**
* 5. 図4.9のに描いている先行順の走査において、節点に訪れるたびに、スタックの内容はどのように変化するか.
*/
static void problem5() {
Node P = new Node("P");
{
Node M = new Node("M");
P.l = M;
{
Node S = new Node("S");
M.l = S;
Node A = new Node("A");
S.l = A;
Node A2 = new Node("A");
S.r = A2;
}
}
{
Node L = new Node("L");
P.r = L;
{
Node E = new Node("E");
L.r = E;
{
Node R = new Node("R");
E.r = R;
Node T = new Node("T");
R.l = T;
{
Node E2 = new Node("E");
R.r = E2;
Node E3 = new Node("E");
E2.l = E3;
}
}
}
}

traversePreorderproblem5(P);
}

private static void traversePreorderproblem5(Node e) {
Stack<Node> stack = new Stack<Node>();
stack.push(e);
for (; !stack.isEmpty();) {
Node[] ns = (Node[]) stack.toArray(new Node[stack.size()]);
for (int i = 0; i < ns.length; i++) {
System.out.format("%s ", ns[i].info);
}
System.out.println();
Node pop = stack.pop();
if (pop.r != null) {
stack.push(pop.r);
}
if (pop.l != null) {
stack.push(pop.l);
}
}
}

/**
* 6. 図4.12のに描いているレベル順の走査において、節点に訪れるたびに、キューの内容はどのように変化するか.
*/
static void problem6() {
Node P = new Node("P");
{
Node M = new Node("M");
P.l = M;
{
Node S = new Node("S");
M.l = S;
Node A = new Node("A");
S.l = A;
Node A2 = new Node("A");
S.r = A2;
}
}
{
Node L = new Node("L");
P.r = L;
{
Node E = new Node("E");
L.r = E;
{
Node R = new Node("R");
E.r = R;
Node T = new Node("T");
R.l = T;
{
Node E2 = new Node("E");
R.r = E2;
Node E3 = new Node("E");
E2.l = E3;
}
}
}
}

traverseLevelorderproblem6(P);
}

private static void traverseLevelorderproblem6(Node e) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(e);
for (; !queue.isEmpty();) {
Node[] ns = (Node[]) queue.toArray(new Node[queue.size()]);
for (int i = 0; i < ns.length; i++) {
System.out.format("%s ", ns[i].info);
}
System.out.println();
Node p = queue.poll();
if (p.l != null) {
queue.add(p.l);
}
if (p.r != null) {
queue.add(p.r);
}
}
}

/**
* 7. 先行順走査のスタックがレベル順走査のキューより記憶領域を多く使うような木の例をあげよ.
*/
static void problem7() {
Node N1 = new Node("1");
{
Node N2 = new Node("2");
N1.l = N2;
Node N3 = new Node("3");
N1.r = N3;
{
Node N4 = new Node("4");
N2.l = N4;
Node N5 = new Node("5");
N2.r = N5;
{
Node N6 = new Node("6");
N4.l = N6;
Node N7 = new Node("7");
N4.r = N7;
}
}
}

traversePreorderproblem5(N1);
traverseLevelorderproblem6(N1);
}

/**
* 8. 先行順走査のスタックがレベル順走査のキューより記憶領域を少なく使うような木の例をあげよ.
*/
static void problem8() {
Node N1 = new Node("1");
{
Node N2 = new Node("2");
N1.l = N2;
{
Node N4 = new Node("4");
N2.l = N4;
Node N5 = new Node("5");
N2.r = N5;
}
Node N3 = new Node("3");
N1.r = N3;
{
Node N6 = new Node("6");
N3.l = N6;
Node N7 = new Node("7");
N3.r = N7;
}
}

traversePreorderproblem5(N1);
traverseLevelorderproblem6(N1);
}

/**
* 9. スタックを用いて2分木の後行順の走査を実現せよ.
*/
static void problem9() {
problem1();
}

/**
* 10. 森を2分木で表現したとして、森のレベル順の走査を実現するプログラムを書け.
*/
static void problem10() {
Node E = new Node("E");
{
Node A = new Node("A");
E.l = A;
{
Node A2 = new Node("A");
A.l = A2;
Node S = new Node("S");
A2.r = S;
}
{
Node R = new Node("R");
A.r = R;
Node E2 = new Node("E");
R.r = E2;
{
Node T = new Node("T");
R.l = T;
Node M = new Node("M");
T.l = M;
Node P = new Node("P");
M.r = P;
Node L = new Node("L");
P.r = L;
Node E3 = new Node("E");
L.r = E3;
}
}
}

traverseLevelorderproblem10(E);
}

private static void traverseLevelorderproblem10(Node e) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(e);
for (; !queue.isEmpty();) {
Node p = queue.poll();
System.out.format("%s", p.info);
Node n = p.r;
while (n != null) {
if (!queue.contains(n)) {
queue.add(n);
}
n = n.r;
}
n = p.l;
while (n != null) {
if (!queue.contains(n)) {
queue.add(n);
}
n = n.r;
}
}
System.out.println();
}
}

このページのトップヘ