c++ 트리 중위순회를 재귀 함수로 진행할 때 코드 흐름에 대한 질문

조회수 509회

main.cpp

#include <stdio.h>
#include "BST.h"

int main()
{
    BST myBSTtree;

    myBSTtree.BST_InsertNode(5, 500);
    myBSTtree.BST_InsertNode(3, 300);
    myBSTtree.BST_InsertNode(2, 200);
    myBSTtree.BST_InsertNode(4, 400);
    myBSTtree.BST_InsertNode(1, 100);
    myBSTtree.BST_InsertNode(9, 900);
    myBSTtree.BST_InsertNode(7, 700);
    myBSTtree.BST_InsertNode(6, 600);
    myBSTtree.BST_InsertNode(8, 800);
    myBSTtree.BST_InsertNode(10, 1000);

    // 중위 순회 및 출력 ( 예상 1부터 10 까지 순서대로 나와야 한다)
    Order(myBSTtree.BSTRootNode);

    return 0;
}

BST.h

#pragma once

struct BSTPair
{
    int key; // key
    int value; // value

    BSTPair()
        : key()
        , value()
    {}

    BSTPair(const int& _key, const int& _value)
        : key(_key)
        , value(_value)
    {}

    ~BSTPair()
    {}
};

class BST_Node
{
public:
    BSTPair pair;
    BST_Node* leftChild = nullptr;
    BST_Node* rightChild = nullptr;

    BST_Node(BSTPair _pair, BST_Node* _leftChild, BST_Node* _rightChild)
        : pair(_pair)
        , leftChild(_leftChild)
        , rightChild(_rightChild)
    {}
};

class BST
{
public:
    BST_Node* BSTRootNode;
    int   nodeCurCount;

public:
    void BST_InsertNode(int _insertkey, int _insertvalue);

    BST()
        : BSTRootNode(nullptr)
        , nodeCurCount(0)
    {}

    ~BST()
    {}
};

void Order(BST_Node* _pNode);
bool BST_SearchNode(BST_Node* _tree, int _searchkey);

BST.cpp

#include <stdio.h>
#include "BST.h"

void Order(BST_Node* _pNode)
{
    if (_pNode == nullptr) return;
    Order(_pNode->leftChild);
    printf("키는 %d, 값은 %d \n", _pNode->pair.value, _pNode->pair.value);
    Order(_pNode->rightChild);
};

다음과 같이 코드가 있을 때 이해가 안가는 부분은 BST.h 의 void Order 재귀 함수 부분입니다. 이 재귀 함수를 디버거의 한단계씩 코드보기로 실행하면

  1. main.cpp 에서 Order함수에 myBSTtree의 루트노드인 BSTRootNode를 인자로 주고 호출한다.
  2. BST.cpp 에서 Order함수의 매개변수에 BSTRoot Node 값 대입
  3. Order 재귀 호출로 5- > 3 -> 2-> 1로 인자가 바뀜
  4. 1을 값으로 가지는 노드인 가장 왼쪽 아래에 있는 노드의 좌측 자식 노드(nullptr)를 다시 인자로 줌
  5. 인자가 nullptr 이므로 if (_pNode == nullptr) return; 구문에 종료 조건으로 걸림
  6. printf("키는 %d, 값은 %d \n", _pNode->pair.value, _pNode->pair.value); 구문이 실행됨 ( 이때 _pNode 는 nullptr 의 부모 노드 격인 값 1을 가지는 노드이다)

여기에서 궁금한 것은 왜 if (_pNode == nullptr) return; 구문에서 재귀 함수가 종료되지 않고 printf 구문이 실행되는지 그리고 종료문을 만날때 _pNode 는 nullptr 이었는데 printf 구문이 실행되면서 _pNode가 nullptr 의 부모 노드가 되어 있는지 입니다

1 답변

  • < 5.>는 키값이 1인 노드의 왼쪽 자식 노드에서 실행된 것입니다.

    < 6.>은 키값이 1인 노드에서 실행된 것입니다.

    중위 순회기 때문에 왼쪽 자식 노드가 끝나면 루트 노드로 돌아갑니다.

    여기에서 궁금한 것은 왜 if (_pNode == nullptr) return; 구문에서 재귀 함수가 종료되지 않고 printf 구문이 실행되는지

    종료된 것이 맞습니다. 이 때 종료된 함수는 키값의 1인 노드의 Order(_pNode->leftChild);이 종료된 것이고, 그 다음줄의 printf("키는 %d, 값은 %d \n", _pNode->pair.value, _pNode->pair.value);이 이어서 실행되는 것입니다.

    그리고 종료문을 만날때 _pNode 는 nullptr 이었는데 printf 구문이 실행되면서 _pNode가 nullptr 의 부모 노드가 되어 있는지 입니다

    이것도 위의 답변으로 이해가 될겁니다.

    • (•́ ✖ •̀)
      알 수 없는 사용자
    • 종료딘것이 키값이 1인 노드의 Order(_pNode->leftChild); 이라는게 이해가 안갔었는데 스택의 개념으로 상상하니까 이해가 갔습니다 스택으로 함수를 쌓았으니 반환도 위에서부터 차례로 내려오는 것이군요 감사합니다 shinjoongeun 2022.6.17 17:57

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)