アルゴリズム導論10.4有根樹の表現

10.4-2 n個のノードの二叉木を与え、O(n)時間の再帰プログラムを書き出し、そのツリー種の各ノードのキーワードを出力する.
疑似コード:

1 TREE-PRINT(T)
2 if T != NIL
3     print key[T]
4     TREE-PRINT( left[T] )
5     TREE-PRINT( right[T] )

c実装:

void TreePrint( Tree T )
{
    if ( T != NULL )
    {
        PrintElement( T );
        TreePrint( T->left );
        TreePrint( T->right );
    }
}

 
10.4-3
(版本一)疑似コード:

1 TREE-PRINT(T, S)
2   while T != NIL or S != NIL
3       if T != NIL
4           PUSH( S, T )
5           VISIT( T )
6           T = T->left
7       else
8           T = POP( S )
9           T = T->right

(バージョン2)疑似コード:

 1 TREE-PRINT( T, S )
 2   if T != NIL
 3       PUSH( T, S )
 4       while S != NIL
 5           Node = POP(S)
 6           VISIT( Node )
 7           if left[Node] != NIL
 8               PUSH( left[Node], S )
 9           if right[Node] != NIL
10               PUSH( right[Node], S )

 
10.4-4
解析:このルートツリーは二叉木の形で格納され、上記の方法で処理することができる.
 
10.4-5 
解析:ノードにフラグと親ノードへのポインタを追加します.これはツリー自体のストレージスペースです.このアルゴリズムでは、固定量の追加ストレージスペースが使用されます.
疑似コード:

 1 TreePrint(T)
 2   while T != NIL
 3       while left[T] != NIL and left[T].Visited != true
 4           T = left[T]
 5       if  T.Visited = false
 6           VISIT(T)
 7           T.Visited = true
 8       if right[T] != NIL and right[T].Visited != true
 9           T = right[T]
10       else
11           T = parent[T]

 
10.4-6
解:ルートツリーの場合、ツリーストレージ形式を採用し、各ノードには左、右ポインタとbool値が含まれています.
ルートツリーの各ノードを設定し、子供がいる場合は最後の子供のポインタが父親、すなわちノードを指し、boolをtrueに設定します.
ツリーノードの子供の右ポインタが兄弟ノードを指す場合、bool値をfalseに設定します.