[자료구조와알고리즘with파이썬] Ch.04 트리

트리: 계층적인 관계를 가진 자료

부모노드	간선으로 직접 연결된 노드 중에 상위 노드
자식노드	간선으로 직접 연결된 노드 중에 하위 노드
형제노드	같은 부모노드를 가진 노드

조상노드	어떤 노드에서 루트노트까지의 경로상에 있는 모든 노드
자손노드	어떤 노드 하위에 연결된 모든 노드

단말노드	자식노드가 없는 노드 / 자식이 있으면 비단말노드
노드의 차수	노드가 가지고 있는 자식노드의 수
트리의 차수	트리에 포함된 모든 노드의 차수 중에서 가장 큰 수
레벨	트리의 각 층에 번호를 매기는 것
트리의 높이	트리가 가지고 있는 최대 레벨

 

<QUIZ>
1. 오른쪽 트리에서 다음을 구해보세요.
(a) 루트노드: A
(b) 노드J의 부모노드: D
(c) 노드G의 형제노드: H, I
(d) 노드C의 차수: 3
(e) 트리의 높이: 3 (이 책으로는 4)
(f) 트리의 차수: 3

 

---

포화이진트리 (full binary tree)

트리의 각 레벨에 노드가 꽉 차있는 이진트리

 

완전이진트리 (complete binary tree)

마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리 (그 외의 다른 노드는 모두 채워져 있어야함)

 

균형 이진 트리 (balanced binary tree)

모든 노드에서 좌우 서브 틀의 높이 차이가 1 이하인 트리

 

노드 i의 부모 노드 인덱스: i/2
노드 i의 왼쪽 자식 노드 인덱스: 2i
노드 i의 오른쪽 자식 노드 인덱스: 2i + 1

 

class BTNode:
	def __init__(self, elem, left=None, right=None):
    	self.data = elem
        self.right = right
        self.left = left

 

<QUIZ> p.127
1. 9개
2. 1+2+4+8+16 = 31개
3. 최소 5개, 최대 31개
4.
5. n+1개
--> 전체 링크의 수는 2n개이다. (n은 노드의 개수)
n개의 노드가 연결되기 위해서는 n-1개의 링크가 필요하다.
따라서 2n - (n - 1)을 하면 None을 가지는 링크만 남게 된다. 따라서 n+1개이다!

---

이진트리의 순회

전위순회(preorder traversal): 부모노드 - 왼 - 오

중위순회(inorder traversal): 왼 - 부모노드 - 오

후위순회(postorder traversal): 왼 - 오 - 부모노드

 

def preorder(n):
	if n is not None:
    	print(n.data, end=' ')
        preorder(n.left)
        preorder(n.right)

def inorder(n):
	if n in not None:
    	inorder(n.lelft)
        print(n.data, end=' ')
        inorder(n.right)

def postorder(n):
	if n is not None:
    	postorder(n.left)
        postorder(n.right)
        print(n.data, end=' ')

 

레벨순회(level order)

레벨 순으로 노드를 방문 (왼 -> 오)

큐 이용

def levelorder(root):
	queue = ArrayQueue() //큐 객체 초기화
    queue.enqueue(root) //최초에 루트노드만 들어있다.
    while not queue.isEmpty(): //큐가 공백상태가 아닌 동안,
    	n = queue.dequeue()
        if n is not None:
        	print(n.data, end=' ')
            queue.enqueue(n.left)
            queue.enqueue(n.right)

---

전체 노드의 수 구하기

def count_node(n):
	if n in Noe:
    	return 0
    else:
    	return count_node(n.left) + count_node(n.right) + 1

 

트리의 높이 구하기

def calc_height(n):
	if n is None:
    	return 0
    hLeft = calc_height(n.left)
    hRight = calc_height(n.right)
    if(hLeft>hRight):
    	return hLeft+1
    else:
    	return hRight+1

 

---

수식트리(Expression Tree)

연산자는 루트나 가지노드에

피연산자는 모두 단말노드에

def evaluate(node):
	if node is None: //공백 트리이면 0 반환
    	return 0 
    elif node.isLeaf(): //단말노드이면 -> 피연산자
    	return node.data //그 노드의 값(데이터) 반환
    else:
    	op1 = evaluate(node.left)
        op2 = evaluate(node.right)
        if node.data == '+' : return op1+op2
        elif node.data == '-' : return op1-op2
        elif node.data == '*" : return op1*op2
        elif node.data == '/' : return op1/op2

 

전위표기법: 연산자를 먼저 적고 좌우 피연산자를 이어서 적는 방법. 맨 앞에서 뒤로 읽으면서 처리함

중위표기법: 연산자를 중간에 적는 방법.

후위표기법: 연산자를 마지막에 적는 방법. 맨 뒤에서 앞으로 읽으면서 처리함

전위(prefix)	중위(infix)	후위(postfix)
연산자 피연산자1 피연산자2	피연산자1 연산자 피연산자2	피연산자1 피연산자2 연산자
+ A B	A + B	A B +
+ 5 * A B	5 + A * B	5 A B *  +

---

전위표기: 맨 앞에서 뒤로 읽으면서 처리

* + 1 3 / 4 2

*는 루트노드가 된다.

+는 *의 왼쪽 자식노드가 된다. (+이전 항목이 *로 연산자기이 때문)

1이전 항목이  +로 연산자기이 때문에 1은 +의 왼쪽 자식노드가 된다.

3이전 항목이 피연산자1이기 때문에 3은 +의 두 번째 피연산자가 된다.

/는 / 이전 연산자 *의 오른쪽 자식노드가 된다.

4는 이전 항목이 /로 연산자기이 때문에 /의 왼쪽 자식노드가 된다.

2는 이전 항목이 피연산자 4이기 때문에 /의 오른쪽 자식노드가 된다.

 

후위표기: 맨 뒤에서 앞으로 읽으면서 처리

1 3 + 4 2 / *

맨 끝에 있는 *는 수식트리의 루트노드이다.

/ 이전의 항목이 연산자이기 때문에 /는 *의 오른쪽 자식노드가 된다.

2 이전의 항목이 연산자이기 때문에 2는 /의 오른쪽 자식노드가 된다.

4 이전의 항목은 피연산자이기 때문에 4는 /의 왼쪽 자식노드가 된다.

+는 *의 왼쪽 자식노드가 된다.

3은 +의 오른쪽 자식노드가 된다.

1은 +의 왼쪽 자식노드가 된다.