首页 > 代码库 > 算法导论 12.1-4
算法导论 12.1-4
题目:对于一棵有N个结点的树,设计在O(N)时间内完成的先序、中序与后序遍历算法
一、先序遍历
递归实现:
void InOrder( SearchTree T ){ if ( T != NULL ) { Visit( T ); InOrder( T->Left ); InOrder( T->Right ); }}
非递归实现:
版本一:栈模拟(深度优先搜索)
void PreOrder( SearchTree T ) { Stack S; while( T != NULL || !S.Empty() ) { if ( T != NULL ) { S.push( T ); Visit( T ); T = T->Left; } else { T = S.pop(); T = T->Right; } }}
版本二:栈模拟(深度优先搜索)
void PreOrder( SearchTree T ){ Stack S; if ( T != NULL ) { S.Push( T ); while ( !S.Empty() ) { SearchTree TNode = S.Pop(); Visit( TNode ); S.Push( TNode->Right ); S.Push( TNode->Left ); } }}
版本三:设置父节点回溯
void PreOrder( SearchTree T ){ while ( T != NULL ) { if( !T->Visited ) { Visit( T ); T->Visited = true; } if ( T->Left != NULL && !T->Left->Visited ) { T = T->Left; } else if( T->Right != NULL && !T->Right->Visited ) { T = T->Right; } else T = T->Parent; }}
二、中序遍历
递归版本:
void InOrder( SearchTree T ){ if ( T != NULL ) { InOrder( T->Left ); Visit( T ); InOrder( T->Right ); }}
非递归版本一:深度优先搜索
void InOrder( SearchTree T ) { Stack S; while( T != NULL || !S.Empty() ) { if ( T != NULL ) { S.push( T ); T = T->Left; } else { T = S.pop(); Visit( T ); T = T->Right; } }}
非递归版本二:深度优先搜索
void InOrder( SearchTree T ){ Stack S; if( T != NULL ) S.Push( T ); T->ChildPushed = false; while ( !S.Empty() ) { SearchTree TNode = S.Pop(); if ( TNode->ChildPushed ) { // 如果标识位为true,则表示其左右子树都已经入栈,那么现在就需要访问该节点了 Visit( TNode ); } else { // 左右子树尚未入栈,则依次将 右节点,根节点,左节点 入栈 if ( TNode->Right != NULL ) { // 左右子树均设置为false TNode->Right->ChildPushed = false; S.Push( TNode->Right ); } TNode->ChildPushed = true; // 根节点标志位为true S.Push( TNode ); if ( TNode->Left != NULL ) { TNode->Left->ChildPushed = false; S.Push( TNode->Left ); } } }}
版本三:设置父节点回溯
void InOrder( SearchTree T ){ while ( T != NULL ) { while ( T->Left != NULL && !T->Left->Visited ) T = T->Left; if ( !T->Visited ) { Visit( T ); T->Visited = true; } if ( T->Right != NULL && !T->Right->Visited ) T = T->Right; else T = T->Parent; }}
三、后序遍历
递归版本:
void PostOrder( SearchTree T ){ if ( T != NULL ) { PostOrder( T->Left ); PostOrder( T->Right ); Visit( T ); }}
非递归版本:深度优先搜索
void PostOrder( SearchTree T ){ Stack S; if( T != NULL ) S.Push( T ); T->ChildPushed = false; while ( !S.Empty() ) { SearchTree TNode = S.Pop(); if ( TNode->ChildPushed ) { // 如果标识位为true,则表示其左右子树都已经入栈,那么现在就需要访问该节点了 Visit( TNode ); } else { TNode->ChildPushed = true; // 根节点标志位为true S.Push( TNode ); // 左右子树尚未入栈,则依次将根结点,右节点,左节点入栈 if ( TNode->Right != NULL ) { // 左右子树均设置为false TNode->Right->ChildPushed = false; S.Push( TNode->Right ); } if ( TNode->Left != NULL ) { TNode->Left->ChildPushed = false; S.Push( TNode->Left ); } } }}
算法时间复杂度分析:以上算法时间复杂度均为O(N)
算法导论 12.1-4
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。