[ 알고리즘 ] Do it 자료구조와 함께 배우는 알고리즘 10장 정리

연습문제 Q_1 > 모든 노드의 데이터를 내림차순으로 출력하는 함수를 작성하세요.

void PrintTreeReverse(const BinNode *p); // 모든 노드르 키 값의 내림차순으로 출력

// Q_1 모든 노드의 데이터를 내림차순으로 출력
void PrintTreeReverse(const BinNode *p) {
    //오른쪽부터 중위순회하면 돼
    if(p != NULL) {
        PrintTreeReverse(p->right);
        PrintLnMember(&p->data);
        PrintTreeReverse(p->left);
    }
}

 

연습문제 Q_2 > FreeTree 함수를 아래와 같이 변형핳면 어떻게 실행되는지 생각해 보세요.

// Q_2 FreeTree 함수를 아래와 같이 변경하면 어떻게 실행되는지 생각
void FreeTree_Q2(BinNode *P) {
    if(p != NULL) {
        FreeTree(p->left);
        free(p);
        FreeTreee(p->right);
    }
    // p->right 전에 p가 가리키는 메모리 영역이 사라지므로 p->right를 참조할 수 없게 된다.
    // p.50 참조
    // + 참고로, p 변수 자체가 없어지는건 아님.
}

 

연습문제 Q_3 > 가장 작은 키 값을 갖는 노드의 포인터를 반환하는 함수와 가장 큰 키 값을 갖는 노드의 포인터를 반환하는 함수를 작성하세요. 트리가 비어 있는 경우에는 널을 반환합니다.

BinNode *GetMinNode(const BinNode *p) 

BinNode *GetMaxNode(const BinNode *p)

// Q_3-1 가장 작은 키 값을 갖는 노드의 포인터 반환. 트리가 비어있는 경우에는 널을 반환.
// 1번은 그렇다쳐도, 코드가 정답이랑 아예똑같 ㅋㅋ
BinNode *GetMinNode(const BinNode *p) {
    
    if(p == NULL) // 트리가 비어있음.
        return NULL;
    else {
        while(p->left != NULL)
            p = p->left;
        
        return p;
    }
    
}

// Q_3-2 가장 큰 키 값을 갖는 노드의 포인터 반환. 트리가 비어있는 경우에는 널을 반환.
// 1번은 그렇다쳐도, 코드가 정답이랑 아예똑같 ㅋㅋ
BinNode *GetMaxNode(const BinNode *p) {
    if(p == NULL) // 트리가 비어있음.
        return NULL;
    else {
        while(p->right != NULL)
            p = p->right;
        
        return p;
    }

}

 

 

공부 내용 정리

 

트리

리스트는 순서대로 데이터를 나열하는 자료구조인데 비해, 트리는 데이터 사이의 계층 관계를 나타내는 자료구조다.


루트 

트리의 가장 윗부분에 위치하는 노드


리프 

트리의 가장 아랫부분에 위치하는 노드. 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라, 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다는 의미.
다른 용어로는 끝 노드(terminal node), 바깥 노드(external node) 

안쪽 노드 

루트를 포함하여 리프를 제외한 노드
다른 용어로는 끝이 아닌 노드(non-terminal node)


자식 

어떤 노드로부터 가지로 연결된 아래쪽 노드.
리프는 자식을 갖지 않는다.


부모 

어떤 노드에서 가지로 연결된 위쪽 노드. 노드는 1개의 부모를 갖는다. 
루트는 부모를 갖지 않는다.


형제 

같은 부모를 가지는 노드.


조상 

어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상(ancestor)이라고 한다.


자손 

어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손(descendant)이라고 한다.


레벨 

루트로부터 얼마나 멀리 떨어져 있는지에 대한 값.
루트의 레벨은 0, 루트로부터 가지가 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어난다.


차수 

노드가 갖는 자식의 수.
모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다.


높이 

루트로부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)을 높이라고 한다.


서브 트리 

트리 안에서 다시 어떤 노드를 루트로 정하고, 그 자손으로 이루어진 트리.


널 트리 

노드, 가지가 없는 트리.


순서 트리와 무순서 트리 

형제 노드의 순서 유무에 따라 트리를 두 종류로 분류. 형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)


순서 트리 탐색 

순서 트리의 노드를 스캔하는 방법은 두 가지.


너비 우선 탐색(Breadth - first Search) 

낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고, 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다. 

깊이 우선 탐색(Depth-first Search) 

리프까지 내려가면서 검색하는 것을 우선순위로 두는 탐색방법. 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아간다. 

깊이 우선 순회의 3가지 방법
(Feat. 이진트리를 예로 설명) 

전위 순회(Preorder)
부모 노드 -> 왼쪽 자식 -> 오른쪽 자식 

중위 순회(Inorder)
왼쪽 자식-> 부모 노드 -> 오른쪽 자식 

후위 순회(Postorder)
왼쪽 자식 -> 오른쪽 자식 -> 부모 노드



이진 트리(Binary tree) 

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리.
이 때 각 노드의 자식은 2명 이하.
순서 트리다.


완전 이진 트리(Complete binary tree) 

루트부터 노드가 채워져 있으면서, 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리. 

특징 
- 마지막 레벨을 제외한 레벨은 노드를 가득 채웁니다.
- 마지막 레벨은 왼쬐부터 오른쪽 방향으로 노드를 채우되, 반드시 끝까지 채울 필요는 없다.
- 높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^(k+1) -1개. 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n.


이진 검색 트리(Binary Search Tree) 

다음의 조건을 모두 만족하는 이진트리.
1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
3. 같은 키 값을 갖는 노드는 없다.


특징
- 이진 검색 트리를 중위 순회하면 키 값의 오름차순을 얻을 수 있다. 

이진 검색 트리의 개별 노드는 자기 참조형 구조체인 BinNode이다.

 

 

출처 - '자료구조와 함께 배우는 알고리즘 입문 C언어편' 도서

 

+ 트리 부분은 본문코드가 그렇게 좋은 것 같지 않다...ㅜ 잘못된 부분도 많고 불필요한 부분도 많은 듯 하다.