이진 트리의 반복적 인 순서 순회

난이도 중급
이진 트리 트리 순회조회수 34

“이진 트리의 반복적 인 순서 순회”문제에서 우리는 이진 트리. 순서대로 통과해야합니다 "반복적으로", 재귀없이.

예

                 2

              /     \

            1         3

          /   \

        4       5                


4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7


4 2 1 3 6 7

암호알고리즘

  1. 변수 초기화 "curNode" 이진 트리의 루트로
  2. 빈 스택을 초기화합니다. 노드 포함 그들이 횡단 할 때
  3. 스택이 비어 있지 않거나 커노드 되지 않았다 없는:
    • DaVinci에는 커노드 is 지원 없는:
      1. 푸시 커노드 스택에
      2. 현재 노드를 다음과 같이 변경하여 가장 왼쪽 자식으로 계속 이동하십시오. curNode = curNode-> 왼쪽
    • 이제 스택의 최상위 노드는 현재 하위 트리의 가장 왼쪽 노드이므로 스택의 최상위 노드 값을 인쇄합니다.
    • 양수인 커노드 스택에서 최상위 노드의 오른쪽 자식으로 curNode = stack.top ()-> 오른쪽 
    • 현재 노드를 다음과 같이 변경하여 가장 왼쪽 자식으로 계속 이동하십시오. curNode = curNode-> 왼쪽 이 가장 왼쪽 노드의 오른쪽 하위 트리를 처리하려면
    • 스택에서 요소 팝

설명

프로그램은 스택이 가장 최근에 추가 된 요소를 튀어 나오는 아이디어를 사용합니다. 위에서 설명한 알고리즘에서 우리는 현재 노드 (처음에는 나무)에 왼쪽 자식이있는 경우 남은 자식이 더 이상 남지 않을 때까지 왼쪽 자식을 스택에 계속 밀어 넣습니다.

현재 노드에 왼쪽 자식이없는 경우가 발생하면 스택의 최상위 노드가 "가장 최근에 가장 왼쪽에있는 노드" 추가되었습니다. 따라서 나머지 순회 순서에서 첫 번째가되어야합니다. 그래서 우리는 그것을 주문 목록에 인쇄 / 추가하기 시작하고 그것을 스택에서 꺼냅니다. 일단 완료되면 이제 우리는 Left-curNode-Right (순서 순서), Left 및 노드 부품이 횡단됩니다. 따라서 노드의 오른쪽 하위 트리가 프로세스에 있습니다!

직관적으로 현재 노드의 오른쪽 하위 트리에 동일한 프로세스를 적용하기를 원하므로 다음과 같이 일반화 할 수 있습니다. curNode = curNode-> right.

이진 트리의 반복적 인 순서 순회핀

실시

이진 트리의 반복적 인 순서 순회를위한 C ++ 프로그램

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}

4 1 5 2 3

이진 트리의 반복적 인 순서 순회를위한 자바 프로그램

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

복잡성 분석

시간 복잡성 이진 트리의 반복적 인 순서 순회

시간 복잡성은 의 위에), 각 노드를 정확히 한 번 방문합니다. 여기서 N은 이진 트리의 노드 수입니다.

공간 복잡성 이진 트리의 반복적 인 순서 순회

공간 복잡성은 의 위에). 트리가 왜곡 될 수있는 최악의 경우를 고려하면 공간 복잡성은 이진 트리의 노드 수와 같습니다.

Translate »
1