[이 진 트 리] 이 진 트 리 의 앞 순서, 중간 순서, 뒤의 순서 가 아 닌 재 귀적 으로 옮 겨 다 니 는 것 을 실현 합 니 다.

이 진 트 리 의 앞 순서, 중간 순서, 뒤 순서 가 옮 겨 다 니 는 재 귀 알고리즘 이 잘 실현 되 었 으 니 쓰 지 않 겠 습 니 다.
재 귀적 이지 않 은 실현 은 반드시 스 택 을 통 해 이 루어 져 야 한다.
이전 순서 비 재 귀적 실현: 뿌리 - > 왼쪽 - > 오른쪽
1. 스 택 의 후진 을 통 해 먼저 나 가 는 사상 을 실현 하고 뿌리 노드 를 스 택 에 넣 은 다음 에 스 택 꼭대기 요소 (뿌리) 를 방문 한 다음 에 오른쪽 아 이 를 스 택 에 넣 은 다음 에 왼쪽 아 이 를 스 택 에 넣 습 니 다. 스 택 은 후진 이 먼저 나 오기 때문에 먼저 스 택 에 나 가 는 것 은 왼쪽 아이 입 니 다. 그러면 먼저 뿌리 를 방문 한 다음 에 왼쪽 아 이 를 방문 하고 마지막 에 오른쪽 아 이 를 방문 합 니 다.

void PreOreder_Nor(Node* pRoot)
{
    cout << "     "<if(pRoot == NULL)
        return ;
    stack s;
    s.push(pRoot);
    while(!s.empty())
    {
        Node *pCur = s.top();
        //     
        cout << pCur->data << " ";
        s.pop();
        //      ，      
        if(pCur->right)
            s.push(pCur->right)l; 
        if(pCur->left)
            s.push(pCur->left);     
    }
    cout << endl;
}

실현 2,

void PreOreder_Nor(Node* pRoot)
{
    if(pRoot == NULL)
        return;
    stack s;
    Node *p = pRoot;
    while(p || !s.empty())
    {
        //      ，   ,           
        while(p)
        {
            s.push(p);
            cout << p->data <<" ";
            p = p->left;
        }
        //p  ，        
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

중 서 비 재 귀적 실현: 왼쪽 - > 뿌리 - > 오른쪽 중 서 는 재 귀적 이지 않 고 왼쪽 뿌리 오른쪽 은 똑 같이 순환 입 니 다. 이번 에는 계속 왼쪽 을 눌 러 서 뿌리 와 오른쪽 을 하나씩 위로 옮 겨 다 녀 야 합 니 다.

void InOreder_Nor(Node *pRoot)
{
    if(pRoot == NULL)
        return ;
    stack s;
    Node *p = pRoot;
    while(p || !s.empty())
    {
        while(p)
        {
            s.push(p);
            p = p->left;
        }
        //           
        //       ，      
        Node *pTop = s.top();
        cout << pTop->data<< " ";
        s.pop();
        p = pTop->right;//     
    }
}

후 순 비 재 귀: 왼쪽 - > 오른쪽 - > 뿌리 는 오른쪽 아이 가 방문 하거나 오른쪽 아이 가 비어 있어 야 뿌리 노드 에 접근 할 수 있 습 니 다.

void PostOreder_Nor(Node *pRoot)
{
    if(pRoot == NULL)
        return ;
    stack s;
    Node *p = pRoot;
    Node *pre = NULL;//        
    while(p || !s.empty())
    {
        while(p)
        {
            s.push(p);
            p = p->left;
        }
        //       
        Node *pTop = s.top();
        //                 
        if(pTop->right == NULL || pTop->right == pre)
        {
            cout << pTop->data << " ";
            pre = pTop;
            s.pop();            
        }
        else//      
        {
            p = pTop->right;
        }
    }
}