首页 > 代码库 > 算法导论 12.1-4

算法导论 12.1-4

2024-07-27 21:23:34   213人阅读

题目：对于一棵有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


联系
我们