[문제풀이] Binary-Tree 순회

문제풀이로 내가 이진트리를 정확히 이해하고 있는지 판단.

풀이 시간: 4시간

결과: 풀이 완료

접근 방법

part.1 이진트리 입력받아 구조화
part.2 전위순회 구현
part.3 중위순회 구현
part.4 후위순회 구현

part.1 이진트리 구조화

처음에는 클래스 노드와 트리노드를 만들어 연결리스트 + 재귀함수로 구현하고자 했다.

위 방식은 보편적이지만 그만큼 단순한 구조로 인해 이진트리에 대한 전반적인 개념이해에 도움은 되지만 내 것이 된다는 느낌을 받지 못했다.

그러므로 연결리스트 대신 딕셔너리를 이용. 각 노드들은 key가 되어 value로 자식노드들을 가지고 있다.

딕서너리 안에는 아래와 같이 저장되게 끔 코드를 작성했다.

  {
  'A': ['B', 'C'],
  'B': ['D', '.'],
  'C': ['E', 'F'],
  'E': ['.', '.'],
  'F': ['.', 'G'],
  'D': ['.', '.'],
  'G': ['.', '.']
  }

part.2 전위순회 구현

전위순회에 대해

전위순회란, 루트 노드를 먼저 방문한 후 이 노드의 왼쪽 서브노드를 방문하고 더 이상 방문할 왼쪽 서브노드가 없으면 오른쪽 서브노드를 방문하는 방법

전위 스택에 아래와 같이 push와 pop을 반복하며 노드를 순회 할 것이다.

def preorder(tree): #tree는 딕셔너리 자료형으로 구성
    stk1 =[] 
	
    # 처음 노드 stack에 쌓을 때는 False
    # 노드 방문 후 다시 스텍에 쌓을 때, True
    # bool 값으로 출력유무를 결정.
    # 즉 스텍에 역순으로 쌓고, pop하면 전위순회가 가능.
    stk1.append([list(tree.keys())[0], False])
    str1 =''
    #처음 root를 기준으로 순회시키기 위해 함수 실행시 Root를 임의로 지정이 필요.
    #stack이 빌때까지 반복문 실행.
    while stk1:
        temp = stk1.pop() #pop해서 임시변수에 저장
        if temp[1] == True: #한번 자식노드 있는지 확인 노드면 True로 바뀌고 문자열에 추가
            str1+=temp[0]
            continue #문자열에 노드를 쌓았으면 다음 반복회차로 이동
        
      	# 우측자식,좌측자식,부모 순으로 스택에 적재
        
        if tree.get(temp[0])[1] != ".":
            stk1.append([tree.get(temp[0])[1], False])
        if tree.get(temp[0])[0] != ".":
            stk1.append([tree.get(temp[0])[0], False])
        stk1.append([temp[0],True])
            
    
    print(str1)
    
    return

part.3 중위순회 구현

중위순회에 대해

중위순회란, 왼쪽 서브노드를 먼저 방문하고 루트노드 방문. 이후 우측 서브노드 순으로 방문하는 순회 방법

스택에 아래와 같이 우측 자식노드->현재 노드->좌측 자식노드순으로 적재를 반복하며 노드를 순회 할 것이다.

def inorder(tree):

    # 처음 노드 stack에 쌓을 때는 False
    # 노드 방문 후 다시 스텍에 쌓을 때, True
    # bool 값으로 출력유무를 결정.
    # 즉 스텍에 우,중,좌 순으로 쌓고, pop하면 중위순회가 가능.
	
    stk1 =[]
    stk1.append([list(tree.keys())[0], False])
    str1 =''
    #처음 root를 기준으로 순회시키기 위해 함수 실행시 Root를 임의로 지정이 필요.
    
    while stk1:
        temp = stk1.pop()
        if temp[1] == True: #한번 자식노드 있는지 확인 노드면 True로 바뀌고 문자열에 추가
            str1+=temp[0]
            continue #문자열에 노드를 쌓았으면 다음 반복회차로 이동
        
        
        # 우측자식, 부모, 좌측자식 순으로 스택에 적재
        
        if tree.get(temp[0])[1] != ".":
            stk1.append([tree.get(temp[0])[1], False])
        stk1.append([temp[0],True])
        if tree.get(temp[0])[0] != ".":
            stk1.append([tree.get(temp[0])[0], False])
            
    
    print(str1)
    
    return

part.4 후위순회 구현

후위순회에 대해

후위순회란, 좌측 서브노드를 먼저 방문하고 우측 서브노드 방문후 루트노드 로 방문하는 순회 방법

스택에 아래와 같이 우측 자식노드->현재 노드->좌측 자식노드순으로 적재를 반복하며 노드를 순회

def postorder(tree):

	# 처음 노드 stack에 쌓을 때는 False
    # 노드 방문 후 다시 스텍에 쌓을 때, True
    # bool 값으로 출력유무를 결정.
    # 즉 스텍에 중,우,좌 순으로 쌓고, pop하면 후위순회가 가능.

    stk1 =[]
    stk1.append([list(tree.keys())[0], False])
    str1 =''
    
    #처음 root를 기준으로 순회시키기 위해 함수 실행시 Root를 임의로 지정이 필요.
    
    while stk1:
        temp = stk1.pop()
        if temp[1] == True:
            str1+=temp[0]
            continue #문자열에 노드를 쌓았으면 다음 반복회차로 이동
      
        # 스택에 부모, 우측자식, 좌측 자식 순으로 적재.
        stk1.append([temp[0],True])
        if tree.get(temp[0])[1] != ".":
            stk1.append([tree.get(temp[0])[1], False])
        if tree.get(temp[0])[0] != ".":
            stk1.append([tree.get(temp[0])[0], False])
    
    print(str1)
    
    return

끝