lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

pythonIntroAlgorithms2Chapter2Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

class TreeNode:
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None


class BinarySearchTree:
 def __init__(self):
 self.root = None

 def insert(self, key):
 # 새로운 키를 트리에 삽입
 if self.root is None:
 self.root = TreeNode(key)
 else:
 self._insert_recursive(self.root, key)

 def _insert_recursive(self, node, key):
 if key < node.key:
 if node.left is None:
 node.left = TreeNode(key)
 else:
 self._insert_recursive(node.left, key)
 elif key > node.key:
 if node.right is None:
 node.right = TreeNode(key)
 else:
 self._insert_recursive(node.right, key)

 def search(self, key):
 # 키가 있는지 탐색
 return self._search_recursive(self.root, key)

 def _search_recursive(self, node, key):
 if node is None or node.key == key:
 return True
 if key < node.key:
 return self._search_recursive(node.left, key)
 return self._search_recursive(node.right, key)

 def preorder_traversal(self):
 # 전위 순회로 모든 노드 방문
 result = []
 self._preorder_traversal_recursive(self.root, result)
 return result

 def _preorder_traversal_recursive(self, node, result):
 if node is not None:
 result.append(node.key) # 노드 방문
 self._preorder_traversal_recursive(node.left, result) # 왼쪽 자식 방문
 self._preorder_traversal_recursive(node.right, result) # 오른쪽 자식 방문


bst = BinarySearchTree()

bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(8)
bst.insert(3)
bst.insert(7)
bst.insert(18)

print(bst.preorder_traversal())
print("Search for 18:", bst.search(18))

# 트리 구현 방법

## 1. 트리 노드 클래스 정의

- 트리는 노드들이 부모-자식 관계를 가지며 연결된 계층적 자료구조입니다.

- `TreeNode` 클래스는 각 노드의 데이터와 왼쪽 및 오른쪽 자식에 대한 참조를 포함합니다.

 

```python title="트리 노드 클래스 정의"
class TreeNode:
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None
```

 

## 2. 이진 탐색 트리 클래스 정의

- 이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 특성을 갖습니다.

- `BinarySearchTree` 클래스는 트리의 루트 노드를 저장합니다.

 

```python
class BinarySearchTree:
 def __init__(self):
 self.root = None
```

 

## 3. 키 삽입 메소드

- `insert` 메소드는 새로운 키를 트리에 삽입합니다.

- 삽입 과정은 노드를 적절한 위치에 배치하여 이진 탐색 트리의 속성을 유지합니다.

 

```python title="키 삽입 메소드 예시"
def insert(self, key):
 if self.root is None:
 self.root = TreeNode(key)
 else:
 self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
 if key < node.key:
 if node.left is None:
 node.left = TreeNode(key)
 else:
 self._insert_recursive(node.left, key)
 elif key > node.key:
 if node.right is None:
 node.right = TreeNode(key)
 else:
 self._insert_recursive(node.right, key)
```

 

## 4. 이진 탐색 트리 객체 생성 및 사용

- `BinarySearchTree` 클래스의 인스턴스를 생성하고, 키를 삽입하여 트리를 구성합니다.

```python title="이진 탐색 트리 객체 생성 및 사용 예시"
# 이진 탐색 트리 객체 생성
bst = BinarySearchTree()

# 키 삽입
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
```