(1.2.5.1)ツリーの遍歴アルゴリズム

(1)「先、中、後」遍歴アルゴリズムの統一再帰表記

void pre（BtNode * p）{//  ：     
if（p!=NULL）{
visit（p）;
pre(P->Lchild);
pre(P->Rchild);
}
}

注意:結合中先、中後、中層はいずれも二叉木の構造を確定することができる.
(2)「先、中、後」遍歴アルゴリズムの非再帰的な書き方:スタック--左圧スタック、退スタック右
先:左側は絶えずスタックを葉まで押して、空いたらスタックを返して右に行って、左側は絶えずスタックを押します.スタック時出力
日:左側は絶えず葉までスタックを押して、空いていたら右にスタックを返して、左側は絶えずスタックを押します.バックスタック時出力
後:左側は葉までスタックを押し続け、空またはスタックにアクセスし、右側は葉までスタックを押し続け、空またはスタックにアクセスし、スタックを右に返します.セカンドスタック時出力
中序遍歴非再帰実装:ルートノードはスタックに切断され、左に遍歴する.左にできない場合は、スタックを返し、出力し、右に遍歴します.
void InOrderTraverse(BiTree T)/非再帰中序遍歴{  
      
    stack Stack;  
    if(!T)  
    {  
printf(「空の木!」  
        return;  
    }  
      
    while(T || !Stack.empty())  
    {  
        while(T)  
        {  
            Stack.push(T);  
            T=T->lchild;  
        }  
        T=Stack.top();  
        Stack.pop();  
        printf("%c",T->data);  
        T=T->rchild;  
    }                                                                                                                                     
}  
  
 
先序遍歴非再帰実現:出力、ノードと絶えずスタックに入り、左に遍歴する.左に行けない場合は、スタックを返して右に行きます.
void PreOrderTraverse(BiTree T)/非再帰先順遍歴{  
      
    stack Stack;  
    if(!T)  
    {  
printf(「空の木!」  
        return;  
    }  
    while(T || !Stack.empty())  
    {  
        while(T)  
        {  
            Stack.push(T);  
            printf("%c",T->data);  
            T=T->lchild;  
        }  
        T=Stack.top();  
        Stack.pop();          
        T=T->rchild;          
    }                                                                                                                                     
}  
後序遍歴非再帰実装:ルートノードがスタックに入り、左に遍歴する.左は遍歴できない:ロールバック、右:右は遍歴できない、ロールバック、出力、ロールバック右;+1つの検証にアクセスしたかどうか
void PostOrderTraverse(BiTree T)/非再帰先順遍歴{  
      
    stack Stack;  
    if(!T)  
    {  
printf(「空の木!」  
        return;  
    }  
    while(T || !Stack.empty())  
    {  
        while(T&&NOTACC(T))  
        {  
            Stack.push(T);  
            T=T->lchild;  
        }  
        T=Stack.top();//バックスタックバックスタック        while(T&&NOTACC(T))
  {
         Stack.push(T); 
   T=T->rchild; 
        }
        T=Stack.top();  
        printf("%c",T->data); 
        Stack.pop();          
        T=Stack.top();  
        T=T->rchild;       
    }                                                                                                                                     
} 
(3)階層遍歴:キュー
void PostOrderTraverse(BiTree T)/非再帰先順遍歴{  
      
    stack Stack;  
    if(!T)  
    {  
printf(「空の木!」  
        return;  
    }  
    if(T!=null)  
    {  
       push(T);
       while(q&&front!=rear){
       q=pop(front);
       visit(q);
       if(q->lchild)  push(q->lchild);
       if(q->rchild)  push(q->rchild);
       }
      
    }                                                                                                                                     
}