fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. class node {
  6. public:
  7. 	int data;
  8. 	node* left;
  9. 	node* right;
  10. };
  11.  
  12. class bst {
  13. private:
  14. 	node* find_impl(node* current, int value) { // private 탐색 메소드
  15. 		if (!current) { // 현재 탐색하는 노드가 NULL인 경우
  16. 			cout << "No matching value found for " << value << ".\n";
  17. 			return NULL;
  18. 		}
  19.  
  20. 		if (current->data == value) { // 원하는 값 찾음
  21. 			cout << value << " has been found.\n";
  22. 			return current;
  23. 		}
  24.  
  25. 		if (value < current->data) { // 원하는 값이 더 작음
  26. 			cout << "current is " << current->data << ". pointer moved to left.\n";
  27. 			return find_impl(current->left, value); // 왼쪽 서브트리로 이동
  28. 		}
  29.  
  30. 		// 위의 모든 선택문을 패스했다면 원하는 값이 더 큰 경우임
  31. 		cout << "current is " << current->data << ". pointer moved to right.\n";
  32. 		return find_impl(current->right, value); // 오른쪽 서브트리로 이동
  33. 	}
  34.  
  35. 	void insert_impl(node* current, int value) { // private 삽입 메소드
  36. 		if (value < current->data) { // 삽입할 값이 현재 탐색하는 노드보다 작음
  37. 			if (!current->left) { // 왼쪽 서브트리 없음
  38. 				current->left = new node{ value, NULL, NULL }; // 바로 붙임
  39. 				cout << "current is " << current->data << ", " << value << " is inserted left\n";
  40. 			}
  41. 			else // 왼쪽 서브트리 있음
  42. 				insert_impl(current->left, value); // 왼쪽 서브트리에 삽입 메소드 다시 호출
  43. 		}
  44. 		else { // else: 삽입할 값이 현재 탐색하는 노드보다 크거나 같음
  45. 			if (!current->right) { // 오른쪽 서브트리 없음
  46. 				current->right = new node{ value, NULL, NULL }; // 바로 붙임
  47. 				cout << "current is " << current->data << ", " << value << " is inserted right\n";
  48. 			}
  49. 			else // else: 오른쪽 서브트리 있음
  50. 				insert_impl(current->right, value); //오른쪽 서브트리에 삽입 메소드 다시 호출
  51. 		}
  52. 	}
  53.  
  54. 	void inorder_impl(node* start) { // private 중위순회(LDR) 메소드
  55. 		if (!start) // 현재 탐색중인 노드가 NULL
  56. 			return; // 돌아감
  57.  
  58. 		inorder_impl(start->left); // L: 왼쪽 서브트리 순회 호출
  59. 		cout << start->data << " "; // D: 현재 노드 데이터 출력
  60. 		inorder_impl(start->right); // R: 오른쪽 서브트리 순회 호출
  61. 	}
  62.  
  63. 	node* delete_impl(node* start, int value) { // private 특정 값 삭제 메소드
  64. 		cout << "current node is " << (start ? to_string(start->data) : "NULL") << ".\n";
  65.  
  66. 		if (!start) { // 현재 노드가 NULL
  67. 			cout << "No value matches " << value << ".\n";
  68. 			return NULL; // 삭제한 노드 없음, NULL 반환
  69. 		}
  70.  
  71. 		if (value < start->data) // 삭제할 값이 현재 노드보다 작음
  72. 			start->left = delete_impl(start->left, value); // 왼쪽 서브트리에 삭제 메소드 다시 호출
  73. 		else if (value > start->data) // else if: 삭제할 값이 현재 노드보다 큼
  74. 			start->right = delete_impl(start->right, value); // 오른쪽 서브트리에 삭제 메소드 다시 호출
  75. 		else { // else: 삭제할 값이 현재 노드와 같음
  76. 			if (!start->left) { // 왼쪽 서브트리가 없음
  77. 				cout << "there is no left subtree. bring the right subtree.\n";
  78. 				auto tmp = start->right; // 현재 노드의 오른쪽 서브트리를 가져옴
  79. 				cout << "delete " << value << ".\n";
  80. 				delete start; // 현재 노드를 지움
  81. 				return tmp; // 아까 가져온 오른쪽 서브트리 반환
  82. 			}
  83.  
  84. 			if (!start->right) { // 오른쪽 서브트리가 없음
  85. 				cout << "there is no right subtree. bring the left subtree.\n";
  86. 				auto tmp = start->left; // 현재 노드의 왼쪽 서브트리 가져옴
  87. 				cout << "delete " << value << ".\n";
  88. 				delete start; // 현재 노드를 지움
  89. 				return tmp; // 아까 가져온 왼쪽 서브트리 반환
  90. 			}
  91.  
  92. 			cout << "there are both subtrees. need successor.\n";
  93. 			auto succNode = successor(start); // 후계자 반환 메소드 호출
  94. 			start->data = succNode->data; // 현재 노드의 값을 후계자의 값으로 대체
  95. 			start->right = delete_impl(start->right, succNode->data); // 아까 가져온 후계자의 원래 노드 삭제
  96. 		}
  97.  
  98. 		return start;
  99. 	}
  100.  
  101. public:
  102. 	node* root = nullptr;
  103.  
  104. 	node* find(int value) { // 특정 값 탐색 메소드
  105. 		return find_impl(root, value); // 따로 구현된 private 탐색 메소드 호출
  106. 	}
  107.  
  108. 	void insert(int value) { // 삽입 메소드
  109. 		if (!root) { // 루트가 비어있다면
  110. 			root = new node{ value, NULL, NULL }; // 로트에 바로 넣음
  111. 			cout << value << " is inserted into root\n";
  112. 		}
  113. 		else // else: 루트가 비어있지 않다면
  114. 			insert_impl(root, value); // 따로 구현된 private 삽입 메소드 호출
  115. 	}
  116.  
  117. 	void inorder() { // 중위순회 메소드
  118. 		inorder_impl(root); // 호출
  119. 	}
  120.  
  121. 	node* successor(node* start) { // 후계자 반환 메소드
  122. 		auto current = start->right; // 현재 노드의 오른쪽 서브트리 가져옴
  123.  
  124. 		while (current && current->left) // 지금 갖고있는 노드와 그 노드의 왼쪽 서브트리가 모두 존재하는 동안 반복
  125. 			current = current->left; // 왼쪽 서브트리로 이동
  126.  
  127. 		cout << "successor is " << (current ? to_string(current->data) : "NULL") << ".\n";
  128. 		return current; // 결과: 오른쪽 서브트리 왼쪽 맨 아래 리프노드 반환
  129. 	}
  130.  
  131. 	void deleteValue(int value) { // 특정 값 삭제
  132. 		root = delete_impl(root, value); // 호출
  133. 	}
  134. };
  135.  
  136. int main()
  137. {
  138. 	bst tree;
  139.  
  140. 	tree.insert(12);
  141. 	tree.insert(10);
  142. 	tree.insert(20);
  143. 	tree.insert(8);
  144. 	tree.insert(11);
  145. 	tree.insert(11);
  146. 	tree.insert(15);
  147. 	tree.insert(28);
  148. 	tree.insert(4);
  149. 	tree.insert(2);
  150. 	tree.insert(27);
  151.  
  152. 	cout << "Inorder Traversal: ";
  153. 	tree.inorder();
  154. 	cout << "\n";
  155.  
  156. 	tree.deleteValue(12);
  157. 	cout << "Delete 12 and Do Inorder Traversal: ";
  158. 	tree.inorder();
  159. 	cout << "\n";
  160.  
  161. 	if (tree.find(12))
  162. 		cout << "Value 12 is in the tree.\n";
  163. 	else
  164. 		cout << "Value 12 is not in the tree.\n";
  165.  
  166. 	tree.deleteValue(11);
  167. 	tree.deleteValue(4);
  168. 	tree.deleteValue(0);
  169. 	tree.inorder();
  170. }
Success #stdin #stdout 0.01s 5316KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
12 is inserted into root
current is 12, 10 is inserted left
current is 12, 20 is inserted right
current is 10, 8 is inserted left
current is 10, 11 is inserted right
current is 11, 11 is inserted right
current is 20, 15 is inserted left
current is 20, 28 is inserted right
current is 8, 4 is inserted left
current is 4, 2 is inserted left
current is 28, 27 is inserted left
Inorder Traversal: 2 4 8 10 11 11 12 15 20 27 28 
current node is 12.
there are both subtrees. need successor.
successor is 15.
current node is 20.
current node is 15.
there is no left subtree. bring the right subtree.
delete 15.
Delete 12 and Do Inorder Traversal: 2 4 8 10 11 11 15 20 27 28 
current is 15. pointer moved to left.
current is 10. pointer moved to right.
current is 11. pointer moved to right.
current is 11. pointer moved to right.
No matching value found for 12.
Value 12 is not in the tree.
current node is 15.
current node is 10.
current node is 11.
there is no left subtree. bring the right subtree.
delete 11.
current node is 15.
current node is 10.
current node is 8.
current node is 4.
there is no right subtree. bring the left subtree.
delete 4.
current node is 15.
current node is 10.
current node is 8.
current node is 2.
current node is NULL.
No value matches 0.
2 8 10 11 15 20 27 28
https://ideone.com/ORGQ01
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!