首页 > 代码库 > 算法导论 12.1-3
算法导论 12.1-3
题目：设计一个执行中序遍历的非递归算法
解答：
分析：
1、使用栈模拟递归调用的过程，即可以实现中序遍历
2、在结点中增加指针域，使该指针域指向父节点，通过迭代即可实现中序遍历
非递归算法：
栈模拟算法版本一：
// InOrder Traveraslvoid 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; } }}
注：该算法使用深度优先搜索技巧来实现，回溯时Visit。
栈模拟算法版本二：
// InOrder Traverasl version2.0void 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 ); } } }}
注：该算法使用宽度优先搜索技巧，在通过标志ChildPushed标记是否可以Visit。
父节点实现版本：
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; }}
注：使用该方法需要增加一个指向父节点的指针域，在建树时会存在一定困难
算法时间复杂度分析：O(N)
算法导论 12.1-3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。