[데이터 구조] 이 진 트 리 옮 겨 다 니 기

재 귀적 코드 가 아 닌 순서 로 옮 겨 다 니 기:

#include <iostream>

#include <vector>

using namespace std;



typedef struct BinaryTree 

{

    int data;

    struct BinaryTree *rchild, *lchild;

}BinaryTree;



int createBinaryTree( BinaryTree * &T)  //                   

{

        int ch;

        scanf("%d", &ch);



        if(ch != 0)

        {

            T = (BinaryTree *)malloc(sizeof(BinaryTree));

            T->data = ch;

            createBinaryTree(T->lchild);

            createBinaryTree(T->rchild);

        }

        else

        {

            T = NULL;

        }

    return 0;

}



int visit(int data)

{

    printf("%d ", data);

    return 0;

}





int PreOrderTraverse(BinaryTree T) //      

{

    BinaryTree* p;

    vector<BinaryTree *> Stack;

    Stack.push_back(&T);

    while(!Stack.empty())

    {

        while((p = Stack.back()) != NULL) 

        {

            visit(p->data);

            Stack.push_back(p->lchild);

        }

        Stack.pop_back();

        if(!Stack.empty())

        {

            p = Stack.back(); 

            Stack.pop_back();

            Stack.push_back(p->rchild);

        }

    }

    return 0;

}





int InOrderTraverse(BinaryTree T) //    

{

    BinaryTree* p;

    vector<BinaryTree *> Stack;

    Stack.push_back(&T);

    while(!Stack.empty())

    {

        while((p = Stack.back()) != NULL) 

            Stack.push_back(p->lchild);

        Stack.pop_back();

        if(!Stack.empty())

        {

            p = Stack.back(); 

            Stack.pop_back();

            visit(p->data);

            Stack.push_back(p->rchild);

        }



    }

    return 0;

}



int main()

{

    BinaryTree * T = NULL;

    createBinaryTree(T);

    PreOrderTraverse(*T);

    InOrderTraverse(*T);

    return 0;

}

탄 창고 의 메커니즘 을 잘 정리 하 세 요.
---------------------------------
오늘 은 다른 사람의 생각 을 참고 하여 뒷 순 서 를 보충 하여 비 재 귀적 알고리즘 을 옮 겨 다 니 며 오른쪽 트 리 가 팝 업 될 때 부모 노드 의 방문 과 팝 업 을 어떻게 설정 하 는 지 주의 하 였 습 니 다.

int AferOrderTraverse(BinaryTree T) //    

{

    BinaryTree * p;

    vector<BinaryTree *> Stack;

    int tag[30] = {0}; // tag           0      1

    int tagnum = 0; //       

    Stack.push_back(&T);

    tag[0] = 0;

    tagnum = 1;



    while(!Stack.empty())

    {

        while((p = Stack.back())!= NULL)

        {

            Stack.push_back(p->lchild);

            tag[tagnum++] = 0;

        }

        //       ，            

        while(tag[tagnum - 1] == 1)  //                  parent  （         ）      

        {

            Stack.pop_back();

            tagnum--;

            visit(Stack.back()->data);

        }

        Stack.pop_back();

        tagnum--;

    

        if(!Stack.empty())

        {

            p = Stack.back();

            Stack.push_back(p->rchild);

            tag[tagnum++] = 1;

        }

    }

    return 0;

}