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 재귀 함수 부분입니다. 이 재귀 함수를 디버거의 한단계씩 코드보기로 실행하면
- main.cpp 에서 Order함수에 myBSTtree의 루트노드인 BSTRootNode를 인자로 주고 호출한다.
- BST.cpp 에서 Order함수의 매개변수에 BSTRoot Node 값 대입
- Order 재귀 호출로 5- > 3 -> 2-> 1로 인자가 바뀜
- 1을 값으로 가지는 노드인 가장 왼쪽 아래에 있는 노드의 좌측 자식 노드(nullptr)를 다시 인자로 줌
- 인자가 nullptr 이므로 if (_pNode == nullptr) return; 구문에 종료 조건으로 걸림
- 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
-
댓글 입력