비선형구조 : 트리

비선형구조 : 트리

비선형구조 : 선형 구조에 해당하지 않는 자료구조로 대표적으로 트리와 그래프가 있다.

그래프 : 정점과 간선으로 이루어져 있는 자료구조

정점(vertex,node) : 자료,상태 등 무언가를 담고 있음

간선(edge) : 정점 간의 관계를 나타냄 (연결리스트를 만들때 prev, next 생각하면 될 듯)

그래프의 간선은 방향이 있을 수도, 없을 수도 있다. 방향이 있다면 방향대로만 이동이 가능함

트리 : 특별한 성질을 갖는 그래프의 종류

트리의 성질

트리의 간선들은 모두 방향성을 갖는다.

어떤 정점을 가리키는 정점의 개수는 최대1개이다.

어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개

트리는 사이클을 갖지 않는다. (사이클 시작 정점으로 돌아오는 경로)

루트노드 : 트리에서 어떠한 정점도 가리키지 않는 정점 (위 그림에서 2는 루트노드이다)

트리의 깊이 : 루트 노드로부터의 거리

부모 노드, 자식노드 : 임의의 정점 A가 다르 정점 B를 가리킬 때 A는 B의 부모노드 B는 A의 자식 노드라고 함

ex) 위 그림에서 정점 7은 정점 2 와 6의 부모노드

리프 노드 : 가리키는 정점이 없는 정점 (위 그림에서는 2, 5, 11, 4)

이진트리 : 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리

이진트리 구현하기

class Tree : def __init__(self, i, l, r) : self.index = i self.left = l self.right = r def addNode(self, i, l, r) : if self.index == None or self.index == i : self.index = i self.left = Tree(l, None, None) if l != None else None #삼항연산자 self.right = Tree(r, None, None) if r != None else None return True else : flag = False if self.left != None : flag = self.left.addNode(i, l, r) #재귀적으로 동작함 True가 될때까지 if flag == False and self.right != None : flag = self.right.addNode(i, l, r) return flag

이진트리 구현의 과정이 잘 이해가 되지 않아서 여러번 생각해보고 과정을 하나하나 뜯어보면서 이해했는데

직관적으로 이해하고 넘어가는 것이 중요한것 같다 재귀적동작을 일일히 뜯어서 이해하려니 머리아픔..

간단하게 설명하자면 입력된 값의 인덱스가 일치한다면 루트 노드라는 소리이고 단순하게 왼쪽, 오르쪽에 다시 입력을 받을 트리 구조를 넣어주는 것 하지만 인덱스 값이 일치하지 않는다는 것은 자식 노드라는 소리이고 이는 else 구문으로 넘어가 다시 재귀적으로 자식노드가 없는 리프노드 까지 addNode 과정을 반복하게 됨.

하나하나 손으로 뜯어보다가 이해가 안돼서 이런 코드의 진행 과정을 알려주는 파이썬 튜터(https://pythontutor.com/)라는 좋은 사이트를 발견했다.

여기에 코드를 입력하면 아래 그림처럼 각 실행단계마다 자료가 어떻게 돌아가는지 볼 수 있다.

from http://comgiri.tistory.com/23 by ccl(A) rewrite - 2021-09-25 16:26:31