자료구조 및 실습 - [8] 트리 Tree (파이썬으로 선위순회, 후위순회 구현) (2)

선위순회

선위순회는 노드를 자기 자식노드보다 앞서서 방문하는 방법이다.

이는 재귀적으로 구현할 수 있다.

선위순회 의사코드

후위순회

선위순회는 노드를 자기 자식노드보다 나중에 방문하는 방법이다.

이또한 재귀적으로 구현할 수 있다.

후위순회 의사코드

 

두가지 방법을 구현하는데 차이점은 노드를 방문하는 타이밍에 있다. 간단하게 순서만 바꿔주면 구현할 수 있다.

아래는 전체적인 트리 ADT의 메서드에 선위순회, 후위순회를 추가해놓은 것이다. 

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

class tree:
  def __init__(self):
    self.root = None
    self.n=0
  
  def root(self):
    return self.root
  
  def element(self,v):
    return v.data

  def isRoot(self,v):
    return v==self.root

  def parent(self,v):
    return v.parant
  
  def leftchild(self,v):
    return v.L
  
  def rightchild(self,v):
    return v.R
  
  def sibling(self,v):
    p = v.parent
    if (p.L == v):
      return p.R
    else:
      return p.L
  
  def isInternal(self,v):
    return (v.L != None) and (v.R != None)
  
  def isExternal(self,v):
    return (v.L == None) and (v.R == None)
  
  def setElement(self,v,e):
    v.data = e
    return e
  
  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 preorder(self,v): # 선위순회
    print(v.data)
    if self.leftchild(v) != None:
      self.preorder(self.leftchild(v))
    if self.rightchild(v) != None:
      self.preorder(self.rightchild(v))

  def postorder(self,v): # 후위 순회
    if self.leftchild(v) != None:
      self.postorder(self.leftchild(v))
    if self.rightchild(v) != None:
      self.postorder(self.rightchild(v))
    print(v.data)

  
  def addNode(self,v,data,location,num):
    if location =='L':
      v.L = Node(data,None,None,v,num)
      self.n+=1
    elif location == 'root':
      self.root = Node('Root',None,None,None,num)
      self.n+=1
    else:
      v.R = Node(data,None,None,v,num)
      self.n+=1