데이터 구조 - 앞 순서 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤 순서 옮 겨 다 니 기, 등급 옮 겨 다 니 기 (재 귀, 비 재 귀)

이 진 트 리 의 역 사 는 매우 기본 적 이 고 중요 한 내용 이다.옮 겨 다 니 는 것 은 이 진 트 리 의 모든 노드 를 방문 하고 모든 노드 는 한 번 만 방문 하 는 것 이다.이 진 트 리 의 달력 은 앞 순 서 를 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 뒤 순 서 를 옮 겨 다 니 고 층 차 를 옮 겨 다 니 는 것 으로 나 뉜 다.
앞 순 서 를 편력 하 다.
앞 순 서 는 뿌리 노드 - > 왼쪽 노드 - > 오른쪽 노드 입 니 다.
위의 두 갈래 트 리 의 앞 순 서 를 옮 겨 다 니 는 결 과 는: ABCDEFGH 입 니 다.
순환 실현
앞 순서 로 옮 겨 다 니 는 순서에 따라 재 귀적 실현 을 매우 빨리 쓸 수 있다.

void PreOrderTraverseRec (Node* root) {

    if (root != NULL) {
        printf("%d ", root->val);
        PreOrderTraverseRec (root->left);
        PreOrderTraverseRec (root->right);
    }
}

비 귀속 실현
앞 순 서 를 옮 겨 다 니 는 비 재 귀적 실현 은 스 택 시 뮬 레이 션 을 사용 할 수 있 습 니 다.
버 전 1
사실은 앞 순 서 를 옮 겨 다 니 는 내부 에서 이 루어 집 니 다. 매번 에 한 노드 를 옮 겨 다 닌 후에 이 노드 의 왼쪽 노드 를 옮 겨 다 니 고 이 왼쪽 노드 를 뿌리 노드 로 보고 왼쪽 노드 를 옮 겨 다 니 며 잎 노드 에 접근 할 때 까지 반복 합 니 다.잎 노드 를 창고 에 던 져 아버지 노드 를 얻 습 니 다.부모 노드 와 부모 노드 의 왼쪽 부분 노드 를 방 문 했 기 때문에 다음 에 상기 방법 에 따라 부모 노드 의 오른쪽 부분 나 무 를 방문 해 야 합 니 다.

void PreOrderTraverseNonRec (Node* root) {

    if (root == NULL) {
        printf("empty tree!
");
        return;
    } else {

        //method 1
        stack s;
        Node* p = root;

        while ( p != NULL || !s.empty()) {

            while (p != NULL) {
                printf("%d ", p->val);
                s.push (p);
                p = p->left;
            }

            if (!s.empty()) {
                p = s.top ();
                s.pop ();
                p = p->right;
            }
        }
    }
}

판본
스 택 으로 더 간결 하 게 시 뮬 레이 션 하 는 방법 도 있다.앞 순 서 는 뿌리 노드 - > 왼쪽 노드 - > 오른쪽 노드 를 옮 겨 다 니 는 순서 입 니 다.창고 의 후진 선 출 특징 에 따라 뿌리 노드 - > 오른쪽 노드 - > 왼쪽 노드 의 순서에 따라 노드 를 창고 에 눌 러 넣 을 수 있다.이렇게 매번 스 택 을 누 르 기 전에 루트 노드 를 방문 하고 스 택 에서 먼저 왼쪽 노드 를 방문 한 다음 에 오른쪽 노드 로 갑 니 다.

void PreOrderTraverseNonRec (Node* root) {

        stack s;
        Node* cur = NULL;
        s.push (root);

        while (!s.empty()) {

            cur = s.top ();
            printf("%d ", cur->val);
            s.pop (cur);

            if (cur->right)
                s.push (cur->right);
            if (cur->left)
                s.push (cur->left);
        }
    }
}

중간 순서 로 옮 겨 다 닌 다.
중간 순 서 는 뿌리 노드 의 왼쪽 부분 노드 - > 뿌리 노드 - > 뿌리 노드 의 오른쪽 부분 노드 입 니 다.
순환 실현

void InOrderTraverseRec (Node* root) {

    if (root != NULL) {
        InOrderTraverseRec (root->left);
        printf("%d ", root->val);
        InOrderTraverseRec (root->right);
    }
}

비 귀속 실현
중간 순서 로 옮 겨 다 니 는 비 재 귀적 실현 은 이전 순서 로 옮 겨 다 니 는 비 재 귀적 실현 버 전 1 과 비슷 하지만 출력 루트 노드 의 선후 순서 가 다 를 뿐이다.

void InOrderTraverseNonRec (Node* root) {

    if (root == NULL) {
        printf("empty tree!
");
        return;
    } else {

        stack s;
        Node* p = root;

        while (p != NULL || !s.empty()) {

            while (p != NULL) {
                s.push (p);
                p = p->left;
            }

            if (!s.empty()) {
                p = s.top ();
                s.pop ();
                printf("%d ", p->val);
                p = p->right;
            }
        }
    }
}

뒤 순 서 를 옮 겨 다 닌 다.
다음 에 옮 겨 다 니 는 순 서 는 왼쪽 노드 - > 오른쪽 노드 - > 뿌리 노드 입 니 다.
순환 실현

void PostOrderTraverseRec (Node* root) {

    if (root != NULL) {
        PostOrderTraverseRec (root->left);
        PostOrderTraverseRec (root->right);
        printf("%d ", root->val);
    }
}

비 귀속 실현
버 전 1
후속 적 으로 옮 겨 다 니 는 과정 에서 왼쪽, 오른쪽 노드 를 방문 하고 뿌리 노드 를 방문 해 야 하기 때문에 재 귀적 으로 실현 하지 않 으 면 뿌리 노드 를 방문 한 다음 에 왼쪽 노드 를 계속 방문 해 야 한다. 잎 노드 에 방문 할 때 까지 이 잎 노드 를 스 택 에 방문 할 수 없다. 왜냐하면 오른쪽 노드 가 아직 방문 되 지 않 았 기 때문이다.따라서 상기 방법 에 따라 잎 노드 의 오른쪽 자 수 를 방문 하고 잎 노드 를 방문 해 야 한다.두 번 의 방문 순 서 를 구별 하기 위해 서 하나의 변 수 를 사용 하여 루트 노드 가 이미 방문 되 었 는 지 기록 할 수 있 습 니 다.

void PostOrderTraverseNonRec2 (Node* root)
{
    if (root == NULL) return;

    stack  s;
    Node *p = root;

    while (p != NULL || !s.empty()) {

        while (p != NULL) {
            p->isFirstVisited = true;
            s.push(p);
            p = p->left;
        }

        while ( !s.empty()) {
            p = s.top();
            if (p->isFirstVisited) {
                p->isFirstVisited = false;
                p = p->right;
            } else {
                printf("%d ", p->val);
                s.pop();
                p = NULL;
            }
        }

    }
}

판본
첫 번 째 방법 은 추가 적 인 공간 저장 노드 가 방문 되 었 는 지, 공간 을 낭비 해 야 한다.현재 방문 한 노드 의 이전 방문 한 노드 를 직접 포인터 로 기록 할 수 있 습 니 다. 만약 에 이전 방문 한 노드 가 현재 노드 의 오른쪽 부분 노드 라면 오른쪽 부분 이 이미 방문 되 었 고 현재 노드 를 직접 출력 하면 됩 니 다.

void PostOrderTraverseNonRec (Node* root) {

    stack s;
    Node *cur = root, *pre = NULL;

    while (cur != NULL || !s.empty()) {

        while (cur != NULL) {
            s.push (cur);
            cur = cur->left;
        }

        if (!s.empty()) {
            cur = s.top ();
            if (cur->right == NULL || cur->right == pre) {
                printf("%d ", cur->val);
                pre = cur;
                s.pop ();
                cur == NULL;
            } else {
                cur = cur->right;
            }
        }
    }
}

여러 단계 로 편력 하 다.
층 차 를 옮 겨 다 니 는 것 은 바로 층 차 를 따라 위 에서 아래로 두 갈래 나 무 를 옮 겨 다 니 는 것 이다.
순환 실현
이 진 트 리 를 한 층 씩 옮 겨 다 닐 수 있 도록 이 진 트 리 의 높이 를 알 아야 한 층 씩 옮 겨 다 닐 수 있다.각 층 에서 뿌리 노드 의 왼쪽 노드 를 옮 겨 다 니 고 오른쪽 노드 를 옮 겨 다 닌 다.

int GetHeight (Node* root) {
    if(root == NULL)
        return 0;
    else
        return max(GetHeight(root->left) + 1, GetHeight(root->right) + 1);
}

void PrintLevel (Node* root, int level) {

    if (root == NULL)
        return;

    if (level == 1) {
        printf("%d ", root->val);
        return;
    }

    return ( PrintLevel(root->left, level-1) + PrintLevel( root->right, level-1));

}

void LevelTraverseRec (Node* root) {

    int height = GetHeight (root);
    for (int i = 1; i <= height; ++i)
    {
        PrintLevel (root, i);
    }
}

비 귀속 실현
층 차 를 옮 겨 다 니 면 대기 열 을 사용 하여 시 뮬 레이 션 할 수 있 습 니 다. 매번 루트 노드 R 에 방문 한 다음 에 루트 노드 의 좌우 부분 L, R 에 방문 한 다음 에 L, R 의 좌우 부분 노드 를 계속 방문 합 니 다.이것 은 대열 의 선진 선발 의 특정 에 부합된다.

void LevelTraverseNonRec (Node* root) {

    if (root == NULL) return;

    Node* cur = root;
    queue q;
    q.push (root);

    while (!q.empty()) {
        cur = q.front ();
        printf("%d ", cur->val);
        q.pop ();

        if (cur->left)
            p.push (p->left);
        if (cur->right)
            p.push (p->right);
    }
}