본 포스트는 파이썬언어를 중심으로 작성되었습니다.
자료구조[3]-이진트리(python)
https://hazarddev.tistory.com/25?category=794281
트리자료구조_on c[1]
본 포스트는 c언어를 중심으로 작성되었습니다. 트리자료구조_on c[1] 저번 스택, 큐에 이어 트리 자료구조에 대해 포스팅을 할까 합니다. 트리 말 그대로 트리입니다. 나뭇가지 처럼 뻗어져 나가
hazarddev.tistory.com
트리자료구조를 표현하기에는 이름 그대로 나무를 사용하여 설명하는 것이 편리할 것 같습니다. 위의 c언어를 중심으로 작성된 트리자료구조를 보고 오시면 본 글을 이해하기 훨씬 수월할 것 이라고 생각이 듭니다. c언어를 모르시더라도 개념자체만 보고오셔도 좋습니다!^^
그렇다면 대략적인 설명을 하도록 하겠습니다.
원래 연결리스트를 먼저 포스팅을 하고 트리자료구조에 대한 포스팅을 이어나가려 했으나, 어려운 개념부터 이해하고 보면 또 이해가 조금 잘되지 않을까(?)하는 생각으로 트리자료구조에 대해 설명해보도록 하겠습니다.
파이썬 포스팅에서는 용어만 간략하게 설명하도록 하겠습니다.
| 이름 | 설명 | |
| 노드 차수 | 자식노드의 수 | 이진 트리에서의 차수는 최대 2입니다. 한개의 노드는 최대 2개의 자식노드를 가질 수 있습니다. 즉, n개의 최말단 노드가 있다고 가정 시에 트리의 차수는 n-1개가 됩니다. |
| 노드 레벨 | 한 노드와 단말노드 사이의 길이 | 한노드와 그 아랫 노드 사이의 길이입니다. |
| 크기 | 모든 노드의 수 | |
| 형제 노드 | 부모가 같은 자식 노드 | |
| 말단 노드 | 자식이 없는 노드 | |
| 내부 노드 | 자식이 있는 노드 | |
위 용어 정도만 우선 알아두시면 이해하는데 도움이 됩니다. 이진트리의 종류나 논리적 구조에 대해서 알고 싶다면 위 링크를 통해 들어가서 확인 해보시면 좀 더 정확하게 알 수 있습니다. c언어를 모르시더라도, 위 링크에 코드 구현은 없고 이론만 적어놓아서 무리는 없습니다!
이진트리를 구현하기에 가장 좋은 방법은 파이썬에서 리스트를 사용하는 것입니다. 앞서 했던 큐나 스택처럼 구현해주면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
class Height(object): 높이를 구하는 객체는 추상데이터 형태로써 선언해줍니다.
def __init__(self):
self.height = 0
class Node(object):
def __init__(self, value = None, level = 1):
self.value = value
self.level = level
self.left = None
self.right = None
def __repr__(self):
return "{}".format(self.value)
def addNode(self, value, level = 2):
newNode = Node(value, level) 4. 루트노드를 만들었다면, 레벨은 증가 할테니 위 init함수에 선언된
if not self.value: 레벨값보다 높은 2를 넣습니다. 5번은 getHeight()입니다
self.value = newNode
elif not self.left:
self.left = newNode
elif not self.right:
self.right = newNode
else:
self.left = self.left.addNode(value, level)
return self
def searchNode(self, value):
if self.value == value:
return self
else:
result = None
if self.left:
result = self.left.searchNode(value)
if self.right:
result = result or self.right.searchNode(value)
return result
def getHeight(self):
r, l = 0 , 0
5. 새로운 변수 r/l을 선언해줍니다.
if self.right: 만약 우측에 있는 값이라면 r값을 상승, 아니라면 l을 상승시키면서 재귀합니다.
r = self.right.getHeight() + 1
if self.left:
l = self.left.getHeight() + 1
return max(r, l) 6. 모든 제어문이 통과되었다면, 최댓값으로써 값을 추출해 반환합니다.
def isBalanced(self, height = Height()): 7. 우리가 만든 이진 트리는 완전 이진트리이기 때문에
lh = Height() 좌 우측의 높이가 같습니다.
rh = Height()
if self.value is None:
return True
l, r = True, True
if self.left:
l = self.left.isBalanced(lh)
if self.right:
r = self.right.isBalanced(rh)
height.height = max(lh.height, rh.height) + 1
if abs(lh.height - rh.height) <= 1:
return l and r
return False
class BinaryTree(Node):
def __init__(self):
super(BinaryTree, self).__init__()
self.root = None
def addNode_2(self, value): 1. 단말노드에 처음으로 데이터 값을 넣습니다.1이라는 값이 먼저 들어갈 것입니다.
if not self.root: 2. 만약 루트노드가 아니라면 루트 노드 후위값으로 삽입합니다.
self.root = Node(value)
else: 3. 루트노드라면 노드클래스에 선언된 addNode로써 루트노드를 만들어 줍니다.
self.root.addNode(value)
def getHeight_1(self):
return self.root.getHeight()
if __name__ == "__main__":
bt = BinaryTree() 이진트리객체를 인스턴스화 해줍니다
for i in range(1,10):
bt.addNode_2(i) 여기서 번호로 설명하도록 하겠습니다. 여기부터 따라와주세요
print(bt.getHeight_1())
print(bt.isBalanced())
|
cs |
|
|
|
결과값:
4
True
가 반환 되었습니다.
물론 좌 우측의 높이가 같다는 점은 유념해야 합니다.
코드설명을 최대한 해보려고 했습니다. 어렵지 않았죠? ㅎㅎ 음... 여기서 이해해야 하는 부분은 객체화입니다. 객체화 시켜주는 것이 객체 지향프로그래밍의 장점이라고 생각합니다. 처음에는 이해가 잘 안가지만, 앞선 자료구조 포스팅을 좀 보고 오시면 이해가 될 수 있습니다. 클래스 포스팅까지 보고오시면 이해는 더욱 쉬울거라 생각합니다.
https://hazarddev.tistory.com/29?category=794282
자료구조[1]-STACK(python)
자료구조[1]-STACK 본 포스트는 python언어로 작성되었음을 알려드립니다. 1. stack이란? https://hazarddev.tistory.com/17?category=794281 STACK(스택)이 뭔가요?[1] 본 포스트는 c언어를 중심으로 작성되었습..
hazarddev.tistory.com
궁금한 점은 댓글로 달아주시면 성심껏 답글을 달도록 하겠습니다.!!
'Python' 카테고리의 다른 글
| 파이썬 dict && DefaultDict 다루기!! 이 정도면 편하게 쓴다! (0) | 2020.12.01 |
|---|---|
| 파이썬에서의 문자열 리스트 변환 및 자르기! (0) | 2020.11.29 |
| 자료구조[2] - Queue(python) (0) | 2020.06.02 |
| 자료구조[1]-STACK(python) (0) | 2020.06.01 |
| 파이썬 리스트 중복제거! (0) | 2020.04.02 |
댓글