자료구조 및 실습 - [8] 트리 Tree (파이썬으로 트리 구현) (1)

트리 ADT

트리 ADT는 계층적으로 저장된 데이터 원소들을 모델링 한 것이다. 앞선 데이터 구조들과 차이점이라면 계층적이라는 점이다.

맨 위의 원소를 제외하고, 각 트리 원소는 부모(parent) 원소와 0개 이상의 자식(children) 원소들을 가진다.
전제: 트리는 비어있지 않다 -> 알고리즘 단순화

---

트리 용어

루트(root): 부모가 없는 노드(A)
내부노드(internal node): 적어도 한 개의 자식을 가진 노드(A, B, C, F)
외부노드(external node), 또는 리프 (leaf): 자식이 없는 노드(E, I, J, K, G, H, D)
형제(siblings): 같은 부모를 가진 노드들(G, H)
노드의 조상(ancestor): 부모(parent), 조부모(grandparent), 증조부모(grand-grandparent), 등
노드의 자손(descendant): 자식(child), 손주(grandchild), 증손주(grandgrandchild), 등
부트리(subtree): 노드와 그 노드의 자손들로 구성된 트리

경로(path): 조상 또는 자손을따라 이어진 노드 시퀀스(예:ABF)
경로길이(path length): 경로내 간선(edge)의 수
노드의 깊이(depth): 루트로부터 노드에 이르는유일한 경로의 길이
노드의 높이(height): 노드로부터 외부노드에이르는 가장 긴 경로의 길이
트리의 높이(height of a tree): 루트의 높이

---

트리 ADT 메서드

트리 ADT의 메서드는 다음과 같다.

- 일반 메서드
  boolean isEmpty()*
  integer size()

- 접근 메서드
  node root()
  node parent(v)
  node children(v)
  element element(v)

- 질의 메서드
  boolean isInternal(v)
  boolean isExternal(v)
  boolean isRoot(v)

- 갱신 메서드
  swapElements(v, w) #노드와 노드의 데이터를 서로 swap
  element setElement(v, e) #노드의 데이터를 e로 set

- 예외
invalidNodeException(): 불법 노드 접근 시 발령

트리ADT를 구현하는 데이터 구조에 따라 추가적인 갱신 메서드 (삽입, 삭제 등) 정의가 가능하다!!

깊이

깊의 의사코드

노드 v의 깊이(depth)의 재귀적 정의

  - 만약 v가 루트면, v의 깊이는 0

  - 그렇지 않으면, v의 깊이는 v의 부모의 깊이 더하기 1

 

실행시간은 O(n) 이며 단, n은 트리 내 총 노드 수이다.

 

 

높이

높이의 의사코드

노드 v의 높이(heigth)의 재귀적 정의

  - 만약 v가 외부노드면, v의 높이는 0

  - 그렇지 않으면, v의 높이는 v의 자식들 중 최대 높이 더하기 1

 

실행시간은 O(n) 이며 단, n은 트리 내 총 노드 수이다.

 

---

순회

순회(traversal)란 트리의 노드들을 체계적인 방식으로 방문하는 것을 말한다.

 

선위순회 (preorder traversal) : 노드를 그의 자손들보다 앞서 방문

선위순회 의사코드

선위순회시 방문하는 순서

 

 

레벨순회 (levelorder traversal): 큐를 이용하여 깊이 d의 모든 노드들을 깊이 d + 1의 노드들에 앞서 방문

레벨이란 트리의 같은 깊이 d에 존재하는 모든 노드들의 집합을 나타낸다.

레벨순회의 의사코드

레벨순회시 방문 순서

 

 

후위순회( postorder traversal) : 노드를 그의 자손들보다 나중에 방문

후위순회 의사코드

후위순회시 방문하는 순서

---

이진트리 ADT

이진트리란 트리의 각 내부노드가 두 개의 자식을 가짐 – 왼쪽(left) 및 오른쪽(right) 자식

좌우 자식노드 가운데 하나가 비어 있는 경우라도 적정이진트리로 구현 가능하다.

 

이진트리 ADT 메서드

이진트리 ADT는 트리 ADT의 확장이다 – 즉, 트리 ADT의 모든 메서드를 상속한다.

 

-추가적인 메서드
  node leftChild(v)
  node rightChild(v)
  node sibling(v)

이진트리ADT를 역시 구현하는 데이터 구조에 따라 추가적인 갱신 메서드 (삽입, 삭제 등) 정의가 가능하다!!

 

이진트리의 깊이와 높이

이진트리의 깊이와 높이 의사코드

노드 v의 깊이(depth)의 재귀적 정의

  - 만약 v가 루트면, v의 깊이는 0

  - 그렇지 않으면, v의 깊이는 v의 부모의 깊이 더하기 1

 

노드v의 높이(height)의 재귀적 정의

  - 만약 v가 외부노드면, v의 높이는 0

  - 그렇지 않으면, v의 높이는 v의 왼쪽과 오른쪽 자식 중 최대 높이 더하기 1

---

이진트리 순회

이진트리의 순회는 트리순회의 특화다.

선위순회와 후위순회의 의사코드

선위순회(preorder traversal): 노드를 그의 왼쪽 및 오른쪽 부트리보다 앞서 방문
후위순회(postorder traversal): 노드를 그의 왼쪽 및 오른쪽 부트리보다 나중에 방문

 

두 가지 방법은 '방문을 언제하느냐?' 에 달려있다.

 

중위순회의 의사코드

중위순회(inorder traversal): 노드를 그의 왼쪽 부트리보다는 나중에, 오른쪽 부트리보다는 앞서 방문한다.

중위순회도 위 두가지 방법과 비슷하게 방문 순서만 차이가 있다.

---

파이썬으로 트리 구현

class Node:
  def __init__(self,data,L=None,R=None,parent=None):
    self.data = data
    self.L = L
    self.R = R
    self.parent = parent

class tree:
  def __init__(self):
    self.root = None
    self.n=0

  def isEmpty(self):
    return self.root==None
  
  def treesize(self):
    print(self.n)
    return self.n
  
  def rootnode(self):
    #print(self.root)
    return self.root.data
  
  def parent(self,v):
    if v == self.root:
      print("Root Node")
    else:
      #print(v.parent.data)
      return v.parent.data
  
  def children(self,v):
    return v.L.data,v.R.data
  
  def element(self,v):
    return v.data
  
  def isInternal(self,v):
    if v.L != None or v.R != None:
      return True
    else: 
      return False
  
  def isExternal(self,v):
    if v.L == None and v.R == None:
      return True
    else:
      return False
  
  def isRoot(self,v):
    if self.root == v:
      return True
    else:
      return False
  
  def swapElements(self,v,w):
    tmp = v.data
    v.data = w.data
    w.data = tmp
    print(f"v.data : {tmp} => {v.data} / w.data : {v.data} => {w.data} ")
  
  def setElements(self,v,e):
    tmp = v.data
    v.data = e
    print(f"Succesly set element v.data : {tmp}=> {e}")
  
  def addNode(self,v,data,location):
    if location =='L':
      v.L = Node(data,None,None,v)
      self.n+=1
    elif location == 'root':
      self.root = Node('Root')
      self.n+=1
    else:
      v.R = Node(data,None,None,v)
      self.n+=1

>>> a = tree()
>>> a.addNode(None,None,'root')
>>> a.addNode(a.root,"root_left",'L')
>>> a.addNode(a.root,"root_right",'R')
>>> a.swapElements(a.root.L,a.root.R)
v.data : root_left => root_right / w.data : root_right => root_left 

>>> print(a.isEmpty())
False

>>> a.treesize()
3

>>> print(a.rootnode())
Root

>>> print(a.children(a.root))
('root_right', 'root_left')

>>> a.swapElements(a.root.L,a.root.R)
v.data : root_right => root_left / w.data : root_left => root_right

>>> print(a.isInternal(a.root))
True

>>> print(a.isExternal(a.root))
False

>>> print(a.isInternal(a.root.L))
False

>>> print(a.isExternal(a.root.L))
True

>>> print(a.isRoot(a.root))
True

>>> print(a.isRoot(a.root.L))
False

>>> a.setElements(a.root.L,"LEFT")
Succesly set element v.data : root_left=> LEFT

>>> print(a.element(a.root.L))
LEFT

메서드가 잘 실행되는 것을 확인할 수 있다.