JArchive 프로그래밍 일기

균형 이진 탐색 트리란?

오른쪽 서브트리의 높이와 왼쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말합니다.

이러한 높이 차이를 균형인수(Balance Factor) 라고 합니다. (BF)

AVL 트리는 삽입 또는 삭제로 트리가 균형을 잃었을 때 스스로 노드를 재배치하여 위의 조건을 다시 맞춥니다. 

( BF가 1 이하:   1, 0, 1 중에서 값을 가집니다. )

[장점]

BF가 1 이하이므로(높이 차이가 거의 비슷하기 때문에) 탐색, 삽입, 삭제 모두 O(log2n) 시간 안에 가능합니다. 

균형 없는 트리라면, 한쪽으로만 자라날 수 있기 때문에, 최악의 경우 시간 복잡도가 O(n)이 됩니다. 

[취약점]

자료가 많아지면 트리의 높이가 커지는 문제가 있습니다.

자료 삽입삭제가 자주 일어나면 균형을 유지하느라 재배치에 쏟는 시간이 많아질 수 있습니다. 

AVL TREE 라는 이름은 만든 사람 2명의 앞글자를 딴 것입니다. 아델슨 벨스키(Abelson-Velskii)와 라딘스(Landis)

균형을 잃은 4가지  경우

(전제)

root 노드를 기준으로 왼쪽, 오른쪽을 구분한다. 

root : 초기 부모

pivot : root의 자리를 대신할 자식 

LL과 RR은 한 번만 회전하는 단순회전이고, LR, RL은 두 번 회전하는 이중회전 입니다.

어떤 방향에 따라 부모와 자식 원소의 위치를 바꾸면 됩니다. 

1. LL (Left-Left) : 오른쪽으로 회전

노드 '3'을 오른쪽으로 회전한다. 노드 '3'이 노드 '2'의 자식이 된다. 

균형이 왼쪽 서브 트리의 왼쪽 서브 트리에 의해 깨진 경우. 오른쪽 방향으로 회전한다.

다시 말하면, 루트 노드의 왼쪽 자식노드의 왼쪽 서브트리에 의해 균형이 깨진 경우를 말한다. 

2. RR (Right-Right) : 왼쪽으로 회전

'1' 노드가 '2'노드의 자식이 된다.

루트노드 1을 기준으로 생각한다.

1의 오른쪽 서브 트리(2)의 오른쪽 서브 트리(3)에 의해 균형이 깨진 경우. 왼쪽 방향으로 회전한다. 

루트 노드의 오른쪽 자식노드의 오른쪽 서브 트리에 의해 균형이 깨진 경우를 말한다. 

3. LR ( Left-Right): LL회전 후에 RR회전

루트 노드 3을 기준으로 보자.  

왼쪽 서브 트리의 오른쪽 노드인 1과 2를 먼저 왼쪽으로 회전한다.

왼쪽 서브트리를 오른쪽으로 회전하여 3이 2의 자식이 되도록 한다. 

루트 노드 3을 기준으로, 루트의 왼쪽 서브트리(1)의 오른쪽 서브 트리(2)가 균형을 잃은 경우.

왼쪽으로 회전 후 오른쪽으로 회전한다. 

( 루트의 왼쪽 서브트리의 오른쪽 서브 트리를 왼쪽으로 회전하고, 루트와 루트의 왼쪽 서브트리를 오른쪽으로 회전한다. )

4. RL (Right-Left) : RR 회전 후에 LL회전

루트 노드 1을 기준으로 보자. 

오른쪽 서브트리가 균형을 잃었다. 

오른쪽 서브트리의 왼쪽 자식을 오른쪽으로 회전한다. 2와 3을 오른쪽으로 회전.

그리고 루트노드의 오른쪽 자식 '2'를 기준으로 왼쪽으로 회전한다. 

 루트 노드의 오른쪽 서브트리의 왼쪽 서브트리가 균형을  잃은 경우.

오른쪽으로 회전 후, 왼쪽으로 회전한다. 

( 왼쪽 서브 트리를 오른쪽으로 회전 후. 루트 노드와 오른쪽 서브 트리를 왼쪽으로 회전한다. )

탐색

이진 탐색 트리의 연산과 같습니다. 

삽입 

회전을 이해해야 한다. 

오른쪽 회전, 왼쪽 회전 두 가지를 기반으로 기본 연산을 한다. 

LeftRotate() : 왼쪽방향으로 회전 

RightRotate() :오른쪽방향으로 회전 

leftRightRotate() : 왼쪽, 오른쪽 방향 회전 

rightLeftRotate() : 오른쪽, 왼쪽 방향 회전 

[ 참고 포스팅 ]

https://edu-coding.tistory.com/43

http://egloos.zum.com/printf/v/913998

이진탐색트리

이진 탐색 트리란?

이진 트리는 자식 노드가 최대 2개인 트리 입니다.

이진 탐색 트리는 이진 탐색을 위한 이진 트리 입니다.

이진 탐색은 집합이 '배열'인 경우에만 가능합니다.

왜냐하면 처음과 끝을 알아야 하고, 집합의 전체 길이를 알아야 합니다.

가장 중요한 것은 인덱스를 이용하여 바로 중앙 요소에 접근할 수 있어야 합니다.

그러나, 링크드 리스트 처럼 동적으로 집합의 크기가 달라지는 경우에는 사용할 수 없습니다.

부모 노드('나')를 기준으로, 왼쪽 자식노드는 나보다 작고, 오른쪽 자식 노드는 나보다 큽니다.

이 규칙을 기반하여 탐색합니다.

탐색

Node* SearchNode(Node* tree, int target){
    if(tree == NULL){
        return NULL;
    }

    if(tree->data == target){ // 탐색 성공

    }else if(tree->data < target){ // 현재 데이터가 타겟보다 작다면, 오른쪽으로
        return SearchNode(tree->right, target);
    }else{
        return SearchNode(tree->left, target); // 타겟보다 크다면, 왼쪽으로 가본다
    }
}

삽입

새 노드를 어디에 삽입할지 찾아야 합니다.

루트 노드와 새 노드를 인자로 받습니다.

void InsertNode(Node** tree, Node* child){

    if((*tree)->data < child->data){ // 새 노드가 현재 노드보다 큰 경우, 

        if((*tree)->right == NULL){
            (*tree)->right = child;
        }else{
            InsertNode(&(*tree)->right, child);
        }

    }else if((*tree)->data > child->data){ // 새 노드가 현재 노드보다 작은 경우,
        if((*tree)->left == NULL){
            (*tree)->left = child;
        }else{
            InsertNode(&(*tree)->left, child);
        }
    }
}

삭제

삭제할 노드가 트리의 맨 끝 리프노드라면 쉽습니다.

하지만 리프노드가 아닌 경우의 삭제 처리가 복잡합니다.

삭제할 노드가 자식을 양쪽 다 가진 경우.

삭제할 노드가 자식을 한 쪽만 가진 경우.

양쪽 자식을 가진 경우

삭제되는 노드의 오른쪽 하위 트리중에서 가장 작은 값을 삭제되는 노드의 부모에게 연결해줍니다.

왜 삭제되는 노드의 오른쪽 하위 트리가 필요한 걸까?

삭제되는 노드의 오른쪽 하위에 있는 노드들은 삭제된 노드보다 전부 큰 수를 가지고 있습니다.

그 하위 트리 중에서 가장 작은 수를 삭제된 자리에 집어넣는 것입니다.

하위 트리 중에서 가장 작은 수는 그 트리에서 왼쪽 가장 끝에 있을 것 입니다.

외자식을 가진 경우

삭제되는 노드의 자식 트리를 부모에게 연결해줍니다.

삭제 코드

• 삭제할 타겟을 탐색합니다.
• 타겟을 찾고 나서, 아래를 수행합니다.
• 잎 노드인 경우, 삭제하고 끝납니다.
• 양쪽 자식을 가진 경우, 최소값을 가진 노드를 찾아내서 삭제한 노드 자리에 갖다 놓습니다.
• 외자식을 가진 경우, 삭제한 노드의 자식을 부모에게 이어줍니다.

Node* RemoveNode(Node* tree, Node* parent, int target){

    // 삭제할 타겟 노드 
    Node* remove_node = NULL;

    // 타겟을 탐색
    if(tree == NULL){
        return NULL;
    }

    if(tree->data < target){
        remove_node = RemoveNode(tree->right, tree, target);
    }else if(tree->data > target){
        remove_node = RemoveNode(tree->left, tree, target);

    }else{ // 타겟 찾음 (3가지 노드 종류에 따라 삭제 수행)

        if(tree->left == NULL && tree->right == NULL){  // 1. 타겟이 잎노드인 경우,

            if(parent->right == tree){
                parent->right = NULL;
            }else{
                parent->left = NULL;
            }

        }else if(tree->left != NULL && tree->right != NULL){ // 2. 양쪽 자식 있는 경우,

            // 오른쪽 자식트리에서 '최소값'가진 노드를 탐색
            Node* minNode = SearchMinNode(tree->right);
            remove_node = RemoveNode(tree, NULL, minNode->data); // 최소값 노드를 제거 
               tree->data = minNode->data; //타겟 자리에 최소값을 갖다놓음    

        }else{ // 3. 외자식 있는 경우, 

            Node* tempTree = NULL;

            if(tree->right != NULL){ // 어느 쪽 자식트리인지 확인 
                tempTree = tree->right;
            }else{
                tempTree = tree->left;
            }

            // 타겟의 자식트리를 자신의 부모에게 이어준다.
            if(parent->right == tree){
                parent->right = tempTree;
            }else{
                parent->left = tempTree;
            }
        }
    }

    return remove_node;
}

양쪽 자식이 있는 경우에서 최소값 노드 찾는 SearchMinNode() 함수

해당 트리 내에 최소값을 찾습니다.

따라서 계속 왼쪽으로만 탐색해서 발견된 값을 리턴하면 됩니다.

Node* SearchMinNode(Node* tree){

    if(tree == NULL){
        return NULL;
    }

    if(tree->left == NULL){ // 자신이 마지막 왼쪽노드면 자신을 리턴!
        return tree;
    }else{
        return SearchMinNode(tree->left);  // 더 왼쪽으로 가본다.
    }

}

이진 탐색이란?

탐색의 범위를 반으로 줄여나가며 탐색하는 방식입니다. 

이미 정렬된 집합에서 빠르게 탐색할 수 있습니다. 

아래는 탐색 과정입니다. 

1. 가운데 요소를 고릅니다. (center)

2. 타깃이 가운데 요소보다 작은지, 큰지 비교합니다. 

3. 타깃이 가운데 요소보다 크다면, 가운데 요소 기준으로 오른쪽 집합으로 가서 재탐색합니다.

   (반대 쪽 집합은 탐색에서 제외되는 것입니다.)

   작다면 가운데 요소 기준으로 왼쪽 집합으로 가서 재탐색합니다. 

4. 타깃을 찾을 때 까지 위의 과정을 반복합니다. 

2번의 비교과정 후에, 어느 쪽 집합에서 재탐색할 지 정해지면, 탐색 범위가 반씩 줄어드므로 빠르게 탐색할 수 있습니다. 

이진 탐색의 구현 

매개 변수는 3개를 받습니다. 

데이터 집합(배열), 데이터 집합의 크기, 타겟값 입니다. 

int BinarySearch(int dataset[], int size, int target) {
	int left, right, center = 0;

	left = 0;
	right = size - 1;

	while (left <= right) { // 탐색 범위가 0 될 때 까지, 
		center = (left + right) / 2;

		if (dataset[center] == target) {
			return dataset[center];
		}
		else if(dataset[center] < target){
			left = center + 1;
		}
		else {
			right = center - 1;
		}
	}

	return NULL;

}

상호 배타적 집합

모집합이 여러 작은 집합들로 나뉜 상황을 표현하는 독특한 트리

상호 배타적 집합(Disjoint-Set)을 표현하는 유니온 파인드(Union-Find) 자료구조

유니온-파인드는 '합집합 찾기'라는 의미를 가지고 있다.

서로소 집합 알고리즘 이라고도 한다. (1외에 공약수 없음)

n 명의 사람 중에서 생일이 같은 사람들끼리 팀을 구성하는 상황을 생각해보자.

생일이 여러 달에 속한 사람은 없다. 따라서 2개 팀에 속한 사람이 없다.

유니온 파인드 자료구조는 상호 배타적인 부분 집합들로 나눠진 원소들을 저장하고 조작하는 자료구조다.

유니온 파인드 연산 3가지

n명의 사람을 0번부터 n-1번 까지의 원소로 표현한다.

각 1개의 원소를 포함하는 n개의 집합을 만든다. (초기화)

두 사람 a, b가 생일이 같다는 것을 확인 할 때마다 두 사람이 포함된 집합이 합쳐진다.(Union 연산)

어떤 원소 b가 주어졌을 때, 이 원소가 속한 집합을 반환한다. (Find 연산)

트리로 상호 배타적 집합 표현하기

• 한 집합에 속하는 원소를 하나의 트리로 묶어준다.
• 트리의 루트에 있는 원소를 각 집합의 대표라고 부른다.
• 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣으면 된다.각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은지 비교하기
• 루트가 같다면 같은 트리에 속한 것
• 두 원소가 같은 트리에 속해 있는지 어떻게 확인할까?

• Find(찾기) 연산루트는 부모가 없으므로 자기 자신을 가리킨다.
• 3의 부모는 4, 4의 부모는 5, 5의 부모는 5 자신이다. 재귀함수로 구현한다.
• 모든 자식 노드가 부모에 대한 포인터를 가져야 한다.
• Union(합치기) 연산한 노드를 다른 노드의 자식으로 넣기 전에 먼저 양 트리의 루트를 찾아야 한다.
• 각 트리의 루트를 찾고, 하나를 다른 한쪽의 자손으로 이어준다.

그림으로 보는 Union-Find (벡터로 구현)

1. 초기화노드 i의 부모 노드를 P[i]에 저장한다.
2. 처음에 모든 노드의 부모는 자기 자신이다.
3. 
4. Union
   
   )
   
   4의 부모는 3으로 변경된다.
   
   )
   
   Union 연산이 끝난 후, 배열은 다음과 같이 갱신된다.
   
5. 1, 2, 3의 부모는 모두 1이므로, 세 정점은 같은 집합에 속한다.
6. 3의 부모는 2가 된다.
7. 1, 2, 3이 연결된다면?
8. 2의 부모는 1로 변경된다.
9. Union(1, 2) , Union(3, 4) 연산으로 노드를 2개씩 합친다.
10. Find
11. 자신이 속한 집합의 루트를 알아내기 위해 재귀 함수가 사용된다.

(코드) 트리로 상호 배타적 집합 구현

struct NaiveDisjointSet{

    vector<int> parent; // 자신의 부모의 번호를 저장  

    NaiveDisjointSet(int n): parent(n){
        for(int i = 0; i < n; i++){ // 처음에는 자기 자신이 자신의 부모다. (혼자니까)
            parent[i] = i; // 자신이 어떤 부모에 포함됬는지 기록 
        }
    } 

    // u 가 속한 트리의 루트의 번호를 찾아서 반환  // 트리의 높이에 비례하는 시간이 걸린다
    int find(int u) const{
        if(u == parent[u]){ // u가 부모라면 
            return u;
        }

        return find(parent[u]);
    } 

    // u가 속한 트리와 v가 속한 트리를 합친다  
    void merge(int u, int v){

        u = find(u); // 양 트리의 루트를 찾아낸다 
        v = find(v);

        if(u == v) return; // u와 v가 같은 트리에 속한 경우 종료. 

        parent[u] = v; 
    } 

}; 

union은 예약어이므로 함수명으로 사용할 수 없다.

상호 배타적 집합의 최적화

• 트리를 사용하니까 연산 순서에 따라 한쪽으로 기울어질 수도 있다는 문제가 있다.
• 그러면 Find 연산도 Union 연산도 시간 복잡도 O(n)이 된다.

랭크에 의한 합치기(union-by-rank)

기울어진 트리를 피하기 위해, 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣자.

(코드) 최적화된 상호 배타적 집합의 구현

rank[] 는 해당 노드가 한 트리의 루트인 경우, 해당 트리의 높이를 저장하는 배열

두 노드를 합칠 때, 높이가 낮은 쪽을 높은 쪽 트리의 서브트리로 포함시킨다.

두 트리의 높이가 같다면, 결과 트리의 높이를 1 증가시킨다.

struct OptimizedDisjointSet{

    vector<int> parent; // 자신의 부모의 번호를 저장  
    vector<int> rank;   // 높이를 저장  

    OptimizedDisjointSet(int n): parent(n), rank(n, 1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    } 

    // u 가 속한 트리의 루트의 번호를 찾아서 반환 
    int find(int u) const{
        if(u == parent[u]){ // u가 부모라면 
            return u;
        }

        return parent[u] = find(parent[u]); // 재귀호출 하면서 parent벡터 업데이트
    } 

    // u가 속한 트리와 v가 속한 트리를 합친다  
    void merge(int u, int v){

        u = find(u); // 양 트리의 루트를 찾아낸다 
        v = find(v);

        if(u == v) return; // u와 v가 같은 트리에 속한 경우 종료. 

        // v를 u의 자식으로 넣는다. 
        if(rank[u] > rank[v]) swap(u, v); 

        // u를 v의 자식으로 넣는다. 
        parent[u] = v; 

        // 높이가 같으면 결과 트리의 높이를 1 증가 
        if(rank[u] == rank[v]) ++rank[v];  

}; 

[출처]

트리를 이용한 상호 배타적 집합 그림 출처

유니온 파인드 그림 출처

유니온 파인드 개념

알고리즘 문제해결전략 (구종만 저) 트리 챕터 상호배타적집합 코드

수식 트리 

수식을 표현하는 이진트리 입니다. 

수식트리는 아래의 두 가지 규칙을 따릅니다.

피연산자는 잎노드 이다. 

연산자는 루트노드 또는 가지노드이다.  

수식 트리 만들기 - Build() 함수 

연산자의 경우, 토큰으로 새 노드를 생성하여 연결합니다.

그리고 Build() 함수를 재귀호출 하여 다음에 오는 노드 두개를 새 노드의 자식으로 연결합니다. 

피연산자의 경우, 토큰으로 새 노드를 생성합니다. 

// 수식 트리 구축하기 
void BuildTree(char* postfixExp, Node** node) {

	// 맨 뒤 부터 하나씩 토큰을 읽는다. 
	int len = strlen(postfixExp);
	char token = postfixExp[len - 1];
	postfixExp[len-1] = '\0';

	switch (token) {
		//연산자라면, 2번 BuildTree 재귀호출.
	case '+': case '-': case '*': case '/':
		(*node) = CreateNode(token); //노드에 연결 
		BuildTree(postfixExp, &(*node)->right); // 식을 '뒤부터'읽으니까 오른쪽부터.
		BuildTree(postfixExp, &(*node)->left);
		break;
		
	default: //피연산자라면 노드 생성 
		(*node) = CreateNode(token);
		break;
	}
}

수식 트리 계산하기 - Calculate() 함수

연산자인 경우, 두 자식의 아래 노드들의 연산 결과가 먼저 필요하므로,

두 자식을 파라미터로 넘겨서 Calculate() 함수를 재귀 호출합니다.

피연산자인 경우, 토큰에 담겨있던 수를 double형으로 변환하여 반환합니다. 

double Calculate(Node* tree) {
	
	double left, right, result = 0;
	char tempChar[2];

	if (tree == NULL) {
		return 0;
	}

	switch (tree->data) {
		case '+': case '-': case '*': case '/':
			left = Calculate(tree->left);
			right = Calculate(tree->right);

			if (tree->data == '+') { 
				result = left + right; 
			}
			else if (tree->data == '-') {
				result = left - right;
			}
			else if (tree->data == '*') {
				result = left * right;
			}
			else if (tree->data == '/') {
				result = left / right;
			}
			break;
		default: //피연산자인 경우,
			memset(tempChar, 0, sizeof(tempChar));
			tempChar[0] = tree->data;
			result = atof(tempChar);
			break;
	}

	return result;
}

이진 트리란?

모든 노드가 2개의 자식을 가진 트리입니다.

이진 트리의 순회 

전위 순회, 중위 순회, 후위 순회 세 가지 방식이 있습니다.  

'루트 노드' 중심으로 생각하면 어렵지 않습니다. 

루트 노드를 가장 먼저 가면 전위 순회.

중간에 루트노드에 가면 중위 순회.

루트 노드를 맨 마지막에 가면 후위 순회입니다. 

전위 순회 

루트 -> 왼쪽 -> 오른쪽  순으로 방문합니다. 

/* 전위 순회 */
void Preorder(Node* node) {

	// 루트 -> 왼쪽 -> 오른쪽 

	if (NULL == node) {
		return;
	}

	printf("%d\n", node->data);
	
	Preorder(node->leftChild);

	Preorder(node->rightSibling);

}

중위 순회 

왼쪽 -> 루트 -> 오른쪽 순으로 방문합니다. 

/* 중위 순회 */
void Inorder(Node* node) {

	// 왼쪽 -> 루트 -> 오른쪽

	if (NULL == node) {
		return;
	}

	Inorder(node->leftChild);

	printf("%d\n", node->data);

	Inorder(node->rightSibling);

}

후위 순회

왼쪽 -> 오른쪽 -> 루트  순으로 방문합니다. 

/* 후위 순회 */
void Postorder(Node* node) {

	// 왼쪽 -> 오른쪽 -> 루트

	if (NULL == node) {
		return;
	}

	Postorder(node->leftChild);
	
	Postorder(node->rightSibling);

	printf("%d\n", node->data);

}

트리란? 

뿌리에서 시작하여 가지, 잎으로 이루어진 나무와 비슷한 자료구조. 

운영체제의 파일 시스템, DOM 구조가 '트리'를 활용합니다. 

트리의  구성 요소 

부모 : 1번 노드는 2,3,4번 노드의 부모입니다. 

자식 : 2,3,4번 노드는 1번 노드의 자식입니다. 

루트(root) : 트리의 맨 꼭대기 '1'번 노드를 루트 노드라고 합니다.

가지 : 트리와 잎노드 사이의 모든 노드들을 뜻합니다. 

잎 노드(terminal node): 가장 끝의 노드, 단말 노드입니다. 

경로 : 3번 노드에서 10번 노드까지의 '경로'는 3, 7, 10 입니다. 

길이 : 3번 노드에서 10번 노드까지 2번 이동해야 하므로, 길이는 2입니다. 

노드의 깊이 : 루트 노드에서 해당 노드까지의 길이입니다. 예를 들어, 6번 노드의 깊이는 2입니다.  

(루트의 깊이는 0 입니다. )

레벨 : 깊이가  같은 노드의 집합입니다. 예를 들어, 2, 3, 4번 노드는 깊이가 1로 같으므로 레벨1 입니다. 

차수 : 자식 노드의 개수 입니다. 

트리의 차수 : 차수가 최대인 노드의 차수. 아래 그림에서는 1번 노드가 자식이 3개여서, 트리의 차수는 3입니다. 

트리 구현

왼쪽 자식-오른쪽 형제 표현법(Left Child Right Sibling)을 이용하여 노드를 만들고 부모 자식을 연결합니다. 

노드

링크드 리스트랑 똑같습니다.

typedef struct Node {
	struct Node* leftChild;
	struct Node* rightSibling;
	int data;
};

노드 생성 및 메모리 해제 

왼쪽 자식을 가리키는 포인터와 오른쪽 형제를 가리키는 포인터를 초기화 해줍니다.  

Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->leftChild = NULL;
	newNode->rightSibling = NULL;
	newNode->data = data;

	return newNode;
}

루트의 왼쪽 자식들 오른쪽 자식들을 free()하고, 루트 자신을 메모리 해제한다. 

/* 트리의 노드 전부 삭제 후, 루트 삭제. */
void FreeTree(Node* rootNode) {

	if (NULL != rootNode->leftChild) {
		FreeTree(rootNode->leftChild);
	}

	if (NULL != rootNode->rightSibling) {
		FreeTree(rootNode->rightSibling);
	}

	rootNode->leftChild = NULL;
	rootNode->rightSibling = NULL;

	FreeNode(rootNode);
}

자식 노드 연결 

부모 노드와 자식 노드 포인터를 매개변수로 입력 받습니다. 

자식이 없다면, 자식에 할당해줍니다. 

자식이 있다면, rightSibling 포인터를 이용하여 마지막 자식을 찾아내서 새 자식(?)을 연결합니다. 

/* 부모에게 자식 연결 */
void ConnectChild(Node** parent, Node* child) {

	if (NULL == (*parent)->leftChild) { // 자식이 없다면, 
		(*parent)->leftChild = child;
	}
	else {// 자식이 있다면, 끝을 찾아서 연결한다.
		Node* lastChild = (*parent)->leftChild;

		while (NULL != lastChild->rightSibling) {
			lastChild = lastChild->rightSibling;
		}

		lastChild->rightSibling = child;
	}
}

트리를 순회하며 출력 

자식과 형제를 출력하기 위해 함수를 재귀 호출 합니다.  

/* 트리 순회하며 출력 */
void Print(Node* node, int depth) {

	int num = 0;

	// 깊이 만큼 들여쓰기 
	for (num = 0; num < depth; num++) {
		printf(" ");
	}

	// 데이터 출력 
	printf("%d\n", node->data);

	// depth를 더해서 자식노드를 출력하도록 함수 재귀 호출 
	if (NULL != node->leftChild) {
		Print(node->leftChild, depth++);
	}

	// 형제노드를 출력하도록 함수 재귀 호출 (depth 유지.)
	if (NULL != node->rightSibling) {
		Print(node->rightSibling, depth);
	}
	
}