이진 탐색 트리 구현 - 삽입

이진 탐색 트리는 

 

노드 - 데이터 / 오른쪽 노드 주소 / 왼쪽 노드 주소 구조이고,

 

삽입 / 삭제 / 출력 기능을 수행한다.

 

노드의 구조는 기존 연결 리스트와 비슷하다. next 대신 left, right가 있다.

 

typedef struct node {
	// 저장할 데이터와 자식 노드의 주소를 저장한다.
	int Data;
	struct node* left;
	struct node* right;
}Node;

 

삽입 기능

 

이진 탐색 트리에서는 데이터의 값이 작으면 왼쪽 크면 오른쪽으로 이동하여 추가된다.

void BinaryTree::append(int Data) {
	Node* newNode = new Node;

	newNode->Data = Data;
	newNode->left = nullptr;
	newNode->right = nullptr;

	// root가 nullptr 이면 노드가 없음
	if (!root) {
		root = newNode;
	}
	else {
		//데이터의 크기에 따라 왼쪽인지 오른쪽인지 갈림
		Node* temp = root;
		
		while (1) { 
			if (temp->Data > Data) {
				if (temp->left) {
					temp = temp->left;
				}
				else {
					temp->left = newNode;
					break;
				}
			}
			else if(temp->Data < Data){
				if (temp->right) {
					temp = temp->right;
				}
				else {
					temp->right = newNode;
					break;
				}
			}
			else {
				std::cout << "중복된 값입니다.\n";
				break;
			}
		}
	}
}

노드를 생성하고 데이터를 입력하고 초기화 해준다.

 

루트가 있는지 체크하고 없으면 루트에 바로 노드를 입력한다.

 

루트가 있다면 반복문을 돌며 새로운 노드의 위치를 찾아간다.