안녕하세요 오유님들
프로그래밍을 공부하고 있는 컴공 학부생입니다...
이번 과제가 레드블랙 트리를 구축하는 것인데요.
일단 이진탐색트리를 먼저 만들고 그 다음에 레드블랙 트리로 발전시켜나가려고하는데
이진탐색트리 구현과정에 막히는 부분이 있네요...
자식노드와 부모노드가 상호참조하게 하고 싶은데
현재 작성한 코드는 부모노드에서 자식노드로 가는 포인터만 존재하고 있습니다...
일단 코드 일부분만 올려볼게요.
#include <iostream>
#include <string>
using namespace std;
class TreeNode{ // 노드 클래스
friend class Tree;
public:
TreeNode( const int &d ) // 노드 생성자. 서브트리를 생성한다.
: leftPtr( 0 ), data( d ), rightPtr( 0 ) // 자기자신은 입력받은 데이터로 초기화, 왼쪽 자식과 오른쪽 자식 생성
{
}
private:
TreeNode *leftPtr; // 왼쪽 자식 포인터
TreeNode *rightPtr; // 오른쪽 자식 포인터
TreeNode *parPtr; // 부모 포인터
int data; // 노드에 들어갈 데이터
//int maxheight;
enum { red, black } color;
};
class Tree{ // 트리 클래스
public:
Tree(); // 트리 생성자
void insertNode( const int & ); // 입력 함수. insertNodeHelper를 호출한다.
void inOrderTraversal() const; // 중위순회 함수. inOrderHelper를 호출한다.
void SearchNode( const int & ); // 탐색 함수. SearchNodeHelper를 호출한다.
//void TestHeight();
private:
TreeNode *rootPtr; // 루트 노드 포인터
void insertNodeHelper( TreeNode **, const int & ); // 입력 함수
void inOrderHelper( TreeNode * ) const; // 중위순회 함수
void SearchNodeHelper( TreeNode *, const int & ); // 탐색 함수
void reColoring();
void reStructuring();
//높이 함수
//void HeightHelper( TreeNode *, int &, int &, int & );
void AVLstructuring();
};
Tree::Tree(){ // 트리를 생성함과 동시에 루트노드의 포인터를 0(External) 으로 초기화 한다.
rootPtr = 0;
}
void Tree::insertNode( const int &value ){ // 입력 함수. main에서 데이터를 받아온다.
insertNodeHelper( &rootPtr, value );
}
void Tree::insertNodeHelper( TreeNode **ptr, const int &value ){
if ( *ptr == 0 ){ // 현재 가리키고 있는 노드가 External 노드이면 새로운 노드를 하나 생성한다.
*ptr = new TreeNode( value ); // 노드 생성시 main에서 입력 받은 데이터로 초기화한다.
// 부모노드의 주소를 현재 노드의 parPtr에 저장해야함.
cout << value << " 가 입력되었습니다." << endl;
}
else{ // 현재 가리키고 있는 노드가 internal 노드일 때 External 노드를 찾아간다.
if ( value < (*ptr)->data ){ // 입력받은 값이 현재 노드의 데이터 값보다 작으면 왼쪽 노드를 확인한다.
insertNodeHelper( &((*ptr)->leftPtr), value );
}
else{ // 입력받은 값이 현재 노드의 데이터 값보다 크면 오른쪽 노드를 확인한다.
if ( value > (*ptr)->data ){
insertNodeHelper( &((*ptr)->rightPtr), value );
}
else // 입력 받은 값이 이미 트리에 있으면 메세지 출력
cout << value << "는 이미 존재하는 값입니다." << endl;
}
}
}
이게 코드 일부분이고 주요한 부분은 빨간색으로 색칠해놨어요.
제멋대로 코드라서 해석하기 힘드실 것같네요...
그래도 과제여서 혼자 힘으로 해보려고했는데 도저히 저부분에서 막혀서 진도가 나가지 않아서
조언좀 얻고자 이렇게 도움을 청해봅니다...
프로그래밍 고수님들의 조언 부탁드립니다ㅠㅠ
