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

위 트리를 연결리스트를 이용해서 구현하고, 주어진 노드에 대해 자신과 왼쪽 자식, 우측 자식의 용량을 순서대로 출력하시오.

※ 참고사항: 실습 및 테스트 용이성을 위해 본 문제에서는 고정된 트리를 사용하지만, 일반적으로 동적으로 삽입, 삭제 가능한 트리를 사용함

 

출력 

◦ 자식 및 노드 존재 여부에 따라 출력 내용이 달라짐
  - 한쪽 자식만 존재하는 경우, 자신과 해당 자식 노드의 용량 2개 값만 출력
  - 자식 노드가 없는 경우, 자신의 용량 1개 값만 출력
  - 존재하지 않는 노드번호가 입력되는 경우 –1을 출력

 

위 문제는 트리를 순회하며 해당하는 노드를 찾고, 조건에 맞게 출력해야 한다고 생각했다.

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,number=None): # 선위순회
    print(v.data)
    if self.leftchild(v) != None:
      self.preorder(self.leftchild(v),number)
    if self.rightchild(v) != None:
      self.preorder(self.rightchild(v),number)


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


  
  def printSLR1(self,v,number): # 후위 순회
    if number > self.n:
      print(-1)
    else:
      if self.leftchild(v) != None:
        self.printSLR1(self.leftchild(v),number)
      if self.rightchild(v) != None:
        self.printSLR1(self.rightchild(v),number)
      if v.num==number:
        target = v.data
        print(target,end=' ')
        if v.L != None:
          print(v.L.data,end=' ')
        if v.R != None:
          print(v.R.data)
        
  
  def printSLR2(self,v,number): # 선위순회
    if number > self.n:
      print(-1)
    else:
      if v.num==number:
        target = v.data
        print(target,end=' ')
        if v.L != None:
          print(v.L.data,end=' ')
        if v.R != None:
          print(v.R.data)
      if self.leftchild(v) != None:
        self.printSLR2(self.leftchild(v),number)
      if self.rightchild(v) != None:
        self.printSLR2(self.rightchild(v),number)
    

  
  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

후위순회 방식으로 트리를 탐색하며 해당하는 노드를 찾는 printSLR1과

선위순회 방식으로 트리를 탐색하며 해당하는 노드를 찾는 printSLR2를 생성했다.

 

정상 작동을 확인하기 위해 트리를 그림과 같이 구성해보자

F = tree()
F.addNode(None,'20','root',1)
root = F.root
F.addNode(root,'30','L',2)
F.addNode(root,'50','R',3)
F2 = root.L
F3 = root.R
F.addNode(F2,'70','L',4)
F.addNode(F2,'90','R',5)
F.addNode(F3,'120','R',6)
F6 = F3.R
F.addNode(F6,'130','L',7)
F.addNode(F6,'80','R',8)

 

후위순회와 선위순회방식의 작동여부를 확인해보자.

>>> F.postorder(root)
70
90
30
130
80
120
50
Root

>>> F.preorder(root)
Root
30
70
90
50
120
130
80

 

마지막으로 조건에 맞게 구성한 printSLR함수를 실행해보자.

>>> F.printSLR1(root,10)
-1

>>> F.printSLR1(root,2)
30 70 90

>>> F.printSLR2(root,10)
-1

>>> F.printSLR2(root,5)
90

실행이 잘 되는것을 확인할 수 있다.