首页 > 代码库 > 算法导论 10.4 有根树的表示
算法导论 10.4 有根树的表示
10.4-2 给定n个结点的二叉树，写出一个O(n)时间的递归程序，将该树种每个结点的关键字输出。
伪代码：
1 TREE-PRINT(T)2 if T != NIL3 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 != NIL3 if T != NIL4 PUSH( S, T )5 VISIT( T )6 T = T->left7 else8 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] != NIL10 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 else11 T = parent[T]
10.4-6
解：对于有根树，采用二叉树存储形式，每个结点含有左、右指针和一个bool值；
设置有根树中的每个结点，若其有孩子则设置其最后一个孩子的指针指向其父亲，即该结点，并设置bool为true；
若有根树结点孩子的右指针指向兄弟结点，则设置bool值为false；
算法导论 10.4 有根树的表示
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。