이 진 트 리 의 구축 과 재 귀적, 비 재 귀적 재 귀적 작업

이 진 트 리 는 우리 가 평소에 많이 사용 하 는 데이터 구조 로 모든 노드 에 최대 두 개의 나무 가 있 는 나무 구조 이다.나무의 개념 과 성질 에 대해 더 이상 소개 하지 않 겠 습 니 다. 저 는 수의 구축 과 일부 조작 을 정리 하 겠 습 니 다.
우선 트 리 의 데이터 형식 을 정의 합 니 다:
4. 567913. 나 무 는 하나의 데이터 필드 와 두 개의 지침 도 메 인 이 있 고 체인 식 저장 구 조 를 사용한다.
우 리 는 tree 를 정의 합 니 다.node t 이후 트 리 를 만 들 고 입력 해 야 합 니 다:

typedef struct TREE_NODE
{
    char data;
    struct TREE_NODE *lchild;
    struct TREE_NODE *rchild;
}*tree_node;

트 리 를 입력 하 는 과정 에서 우 리 는 기 호 를 입력 하여 이 트 리 의 노드 가 여기 서 멈 췄 는 지 여 부 를 판단 해 야 하기 때문에 if (ch = = '\ #') 를 판단 합 니 다.
이렇게 해서 우 리 는 나 무 를 만 들 었 고 데 이 터 를 입력 했다. 우 리 는 대수 에 있어 가장 기본 적 이 고 중요 한 조작 은 바로 옮 겨 다 니 는 것 이다. 나무의 옮 겨 다 니 는 방법 에 대해 우 리 는 세 가지 방식 이 있다. 그것 이 바로 앞 순 서 를 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 뒤 순 서 를 옮 겨 다 니 는 것 이다. 우 리 는 먼저 재 귀적 으로 옮 겨 다 니 는 방법 을 살 펴 보 자.

tree_node createTree()   //    
{
    char ch;
    tree_node t;
    ch=getchar();  //       
    if(ch=='#')  //         
        t=NULL;
    else
    {
        t=(tree_node)malloc(sizeof(tree_node));  //      
        t->data=ch;
        t->lchild=createTree();
        t->rchild=createTree();
    }
    return t;
}

void preOrder(tree_node t)  //    
{
    if(t)
    {
        printf("%c",t->data);
        preOrder(t->lchild);
        preOrder(t->rchild);
    }
}

void intOrder(tree_node t)  //    
{
    if(t)
    {
        intOrder(t->lchild);
        printf("%c",t->data);
        intOrder(t->rchild);
    }
}

이것 은 우리 가 재 귀적 인 방식 으로 나 무 를 옮 겨 다 니 는 것 입 니 다. 만약 에 우리 가 재 귀적 인 방식 을 사용 하지 않 는 다 면 우 리 는 어떻게 옮 겨 다 니 는 것 입 니까?

void preOrder(tree_node t)  //    
{
    if(t)
    {
        printf("%c",t->data);
        preOrder(t->lchild);
        preOrder(t->rchild);
    }
}

void preOrder(tree_node t) //    
{
    stack<tree_node> s;
    tree_node p = t;
    while(p!=NULL || !s.empty())
    {
        while(p!=NULL)
        {
            cout << p->data;
            s.push(p);
            p = p->lchild;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
}

void intOrder(tree_node t) //    
{
    stack<tree_node> s;
    tree_node p = t;
    while(p!= NULL || !s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p = p->lchild;
        }
        if(!s.empty())
        {
            p = s.top();
            cout << p->data;
            s.pop();
            p = p->rchild;
        }
    }
}

재 귀적 이지 않 은 뒷 순 서 를 옮 겨 다 니 는 것 이 비교적 번 거 롭 습 니 다. 우 리 는 왼쪽 트 리 를 따라 계속 아래로 검색 해 야 합 니 다. 왼쪽 트 리 가 없 을 때 까지 우 리 는 스 택 에 방문 할 수 없습니다. 우 리 는 오른쪽 트 리 를 스 택 에 들 어가 라 고 말 해 야 합 니 다. 우 리 는 오른쪽 트 리 를 똑 같이 처리 한 후에 야 스 택 에 방문 할 수 있 습 니 다. 그러면 우 리 는 표 지 를 하나 더 설정 해 야 합 니 다.두 번 째 로 창고 꼭대기 에 도 착 했 을 때 만 우 리 는 창 고 를 방문 할 수 있다.
전체 코드 는 다음 과 같 습 니 다:

typedef struct node1
{
    TREE_NODE *btnode;
    bool isFirst;
}*BTNode;
void postOrder(tree_node t) //    
{
    stack<BTNode> s;
    tree_node p = t;
    BTNode q;
    while(p!=NULL || !s.empty())
    {
        while(p!=NULL)
        {
            BTNode bt = (BTNode)malloc(sizeof(BTNode));
            bt->btnode = p;
            bt->isFirst = true;
            s.push(bt);
            p = p->lchild;
        }
        if(!s.empty())
        {
            q = s.top();
            s.pop();
            if(q->isFirst ==true)
            {
                q->isFirst = false;
                s.push(q);
                p = q->btnode->rchild;
            }
            else
            {
                cout << q->btnode->data;
                p = NULL;
            }
        }
    }
}