算法导论 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

(版本二)伪代码：

 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；