11-1 트리

qzzloz·2023년 7월 6일
cppdata structure
0

Data Structure

목록 보기
3/9
post-thumbnail
  • 트리: 하나의 루트 노드에서 시작해서 여러 개의 자식 노드들로 이어지는 자료구조

1. 트리의 용어

  • 노드: 트리의 구성요소
  • 간선: 노드를 연결하는 선(==link, branch)
  • 루트노드: 최상위 노드, 부모노드가 없다.
  • 서브트리: 하나의 노드와 그의 자손들로 이루어져 있다.
  • 단말노드: 자식노드가 없는 노드
  • 비단말노드: 자식노드가 있는 노드
  • 부모 노드: 자식 노드를 가지는 노드, 자식 노드보다 상위 노드이다.
  • 자식 노드: 부모 노드를 가지는 노드, 부모 노드보다 하위 노드이다.
  • 형제 노드: 같은 부모 노드를 가지는 노드
  • 노드의 크기: 자신과 모든 자식 노드의 개수
  • 노드의 레벨: 특정 깊이를 가지는 노드들의 집합
  • 노드의 깊이: 루트 노드에서 특정 노드에 도달하기까지 거쳐야 하는 간선의 수
  • 노드의 차수: 노드의 자식 노드 수
  • 트리의 차수: 노드의 최대 차수
  • 트리의 높이: 루트노드에서 가장 깊은 곳에 있는 노드의 깊이

2. 트리의 특징

  • 그래프의 한 종류, 최소연결트리라고도 불린다.
  • 루트 노드에서 특정 노드까지 가는 경로는 유일하다.
  • 임의의 두 노드 간 경로도 유일하다.
  • 한 개의 루트노드만이 존재한다.
  • 모든 자식 노드는 한 개의 부모 노드만을 가진다.

3. 이진트리

이진트리란 자식 노드를 최개 2개만 가질 수 있는 트리이다.

  • 이진 트리의 모든 노드는 차수가 2이하이다.
  • 이진 트리는 노드를 하나도 갖지 않을 수 있다. 즉, 서브 트리는 공집합일 수 있다.
  • 서브 트리 간의 순서가 존재한다. 일반적으로 왼쪽 -> 오른쪽 방향이다.
  • 모든 서브 트리도 이진 트리여야 한다.

4. 이진트리의 성질

노드의 개수: n

  • 간선의 개수: n-1
  • 이진트리의 높이: n-1 ~ 천장(log2(n+1))-1

높이: h

  • 가질 수 있는 노드의 최대 ~ 최소 개수: h+1 ~ 2^(h+1)-1

  • 노드의 번호는 레벨 단위로 왼쪽에서 오른쪽으로 번호를 부여한다.

5. 포화 이진트리(Full Binary Tree)

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

6. 완전 이진 트리(Complete Binary Tree)

모든 레벨에서 노드가 왼쪽에서 오른쪽으로 순차적으로 채워져 있는 이진트리이다.
트리의 높이가 h라면 레벨 1부터 h-1까지는 노드가 모두 채워진다.
마지막 레벨 h에서는 노드가 왼쪽->오른쪽 방향으로 순서대로 채워진다.
포화 이진트리는 완전 이진 트리라고 할 수 있다!

7. 이진 트리 구현 - 연결 리스트

BinaryNode 클래스: 노드는 왼쪽 자식 노드를 가리키는 포인터인 left, 오른쪽 자식 노드를 가리키는 포인터인 right, 데이터를 저장하는 data 변수로 구성된다.

BinaryTree 클래스: 루트 노드를 설정한다. 

#include <iostream>
using namespace std;

class BinaryNode {
protected:
    int data;
    BinaryNode* left;
    BinaryNode* right;

public:
    BinaryNode(int val=0, BinaryNode* l=NULL, BinaryNode* r=NULL): data(val), left(l), right(r) {}
    ~BinaryNode() {}

    void setData(int val){ data = val; }
    void setLeft(BinaryNode* l){ left = l; }
    void setRight(BinaryNode* r){ right = r; }
    int getData() {return data;}
    BinaryNode* getLeft(){return left;}
    BinaryNode* getRight(){return right;}
    bool isLeaf(){ return left==NULL && right==NULL;}

};

class BinaryTree{
    BinaryNode* root;

public:
    BinaryTree(): root(NULL){}
    ~BinaryTree() {}

    void setRoot(BinaryNode* node){ root=node; }
    BinaryNode* getRoot() { return root; }
    bool isEmpty() {return root==NULL;}

    void display(){
        cout << "Binary Tree:" << endl;
        if (isEmpty()){
            cout<< "Empty Tree." << endl;
        } 
        else
            display(root,0);
    }
    
private:
    void display(BinaryNode* node , int depth){
        if (node==NULL)
            return;

        for (int i=0; i<depth; i++)
            cout<<" ";
        cout << "- " << static_cast<char>(node->getData()) << endl;
        display(node->getLeft(), depth+1);
        display(node->getRight(), depth+1);
    }
};

int main(){
    BinaryTree tree;

    BinaryNode *d = new BinaryNode('D', NULL, NULL);
    BinaryNode *e = new BinaryNode('E', NULL, NULL);
    BinaryNode *b = new BinaryNode('B', d, e);
    BinaryNode *f = new BinaryNode('F', NULL, NULL);
    BinaryNode *c = new BinaryNode('C', f, NULL);
    BinaryNode *a = new BinaryNode('A', b, c);

    tree.setRoot(a);

    tree.display();   
}

8. 이진 트리의 순회

  • 전위순회(preorder traversal)
    루트 -> 왼쪽 자식 -> 오른쪽 자식
    (1 - 2 - 4 - 5 - 3 - 6)

  • 중위순회(inorder traversal)
    왼쪽 자식 -> 루트 -> 오른쪽 자식
    (4 - 2 - 5 - 1 - 3 - 6)

  • 후위순회(postorder traversal)
    왼쪽 자식 -> 오른쪽 자식 -> 루트
    (4 - 5 - 2 - 6 - 3 - 1)

9. 이진 트리의 순회 구현

이진 트리 구현 코드의 BinaryTree 클래스에 순회 알고리즘인 inorder, preorder, postorder 메소드를 추가한다.

#include <iostream>

using namespace std;

class BinaryNode {
protected:
    int data;
    BinaryNode* left;
    BinaryNode* right;

public:
    BinaryNode(int val=0, BinaryNode* l=NULL, BinaryNode* r=NULL): data(val), left(l), right(r) {}
    ~BinaryNode() {}

    void setData(int val){ data = val; }
    void setLeft(BinaryNode* l){ left = l; }
    void setRight(BinaryNode* r){ right = r; }
    int getData() {return data;}
    BinaryNode* getLeft(){return left;}
    BinaryNode* getRight(){return right;}
    bool isLeaf(){ return left==NULL && right==NULL;}

};

class BinaryTree{
    BinaryNode* root;

public:
    BinaryTree(): root(NULL){}
    ~BinaryTree() {}

    void setRoot(BinaryNode* node){ root=node; }
    BinaryNode* getRoot() { return root; }
    bool isEmpty() {return root==NULL;}

    void display(){
        cout << "Binary Tree:" << endl;
        if (isEmpty()){
            cout<< "Empty Tree." << endl;
        } 
        else
            display(root,0);
    }

    void inorder(){cout << "\n   inorder: "; inorder(root);}
    void inorder(BinaryNode *node){
        if(node!=NULL){
            inorder(node -> getLeft());
            cout << "[" << static_cast<char>(node->getData()) << "] ";
            inorder(node -> getRight());
        }
    }
    
    void preorder() {cout << "\n  preorder: "; preorder(root);}
    void preorder(BinaryNode *node){
        if(node!=NULL){
            cout << "[" << static_cast<char>(node ->getData()) << "] ";
            preorder(node -> getLeft());
            preorder(node -> getRight());
        }
    }

    void postorder(){cout << "\n postorder: "; postorder(root);}
    void postorder(BinaryNode *node){
        if(node!=NULL){
            postorder(node -> getLeft());
            postorder(node -> getRight());
            cout << "[" << static_cast<char>(node -> getData()) << "] ";
        }
    }
private:
    void display(BinaryNode* node , int depth){
        if (node==NULL)
            return;

        for (int i=0; i<depth; i++)
            cout<<" ";
        cout << "- " << static_cast<char>(node->getData()) << endl;
        display(node->getLeft(), depth+1);
        display(node->getRight(), depth+1);
    }
};

int main(){
    BinaryTree tree;

    BinaryNode *d = new BinaryNode('D', NULL, NULL);
    BinaryNode *e = new BinaryNode('E', NULL, NULL);
    BinaryNode *b = new BinaryNode('B', d, e);
    BinaryNode *f = new BinaryNode('F', NULL, NULL);
    BinaryNode *c = new BinaryNode('C', f, NULL);
    BinaryNode *a = new BinaryNode('A', b, c);

    tree.setRoot(a);

    tree.display();   

    tree.inorder();
    tree.preorder();
    tree.postorder();

    return 0;
}

10. 레벨 순회

큐를 사용하여 구현한다.
큐에서 노드를 하나 꺼내서 방문 처리하고, 방문한 노드의 자식 노드를 큐에 순서대로 삽입하는 방법이다.
트리의 모든 노드를 방문할 때까지 반복한다.

레벨 순회 구현 알고리즘

queue.enque(root)
while(!queue.isEmpty()){
	x = queue.dequeue()		// 큐의 노드를 하나 꺼내 x에 넣어서 방문 처리
    						//dequeue() 메소드는 큐의 노드를 꺼내서 리턴한다.
    if(x != NULL){
    	print(x)
        queue.enqueue(LEFT(x))	// x의 왼쪽 노드를 큐에 삽입
        queue.enqueue(RIGHT(x)) // x의 오른쪽 노드를 큐에 삽입
    }
}

11. 레벨 순회 구현

  1. 이진 트리 순회 구현 코드의 BinaryTree 클래스 상단에 원형큐 클래스를 추가한다.
#include <iostream>

using namespace std;

class BinaryNode {
protected:
    int data;
    BinaryNode* left;
    BinaryNode* right;

public:
    BinaryNode(int val=0, BinaryNode* l=NULL, BinaryNode* r=NULL): data(val), left(l), right(r) {}
    ~BinaryNode() {}

    void setData(int val){ data = val; }
    void setLeft(BinaryNode* l){ left = l; }
    void setRight(BinaryNode* r){ right = r; }
    int getData() {return data;}
    BinaryNode* getLeft(){return left;}
    BinaryNode* getRight(){return right;}
    bool isLeaf(){ return left==NULL && right==NULL;}

};
inline void error(char* str){
	cerr << str << endl;
	exit(1);
};

#define MAX_QUEUE_SIZE 100
class CircularQueue{
	int front;
	int rear;
	BinaryNode* data[MAX_QUEUE_SIZE];
public:
	CircularQueue(){
		front = rear = 0;
	}
	~CircularQueue(){	}
	bool isEmpty(){return front == rear;}
	bool isFull(){return (rear+1) % MAX_QUEUE_SIZE == front;}
	void enqueue(BinaryNode* val){
		if(isFull()) error("포화상태\n");
		else{
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}

	BinaryNode* dequeue(){
		if(isEmpty()) error("공백상태\n");
		else{
			front = (front +1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}
};

class BinaryTree{
    BinaryNode* root;

public:
    BinaryTree(): root(NULL){}
    ~BinaryTree() {}

    void setRoot(BinaryNode* node){ root=node; }
    BinaryNode* getRoot() { return root; }
    bool isEmpty() {return root==NULL;}

    void display(){
        cout << "Binary Tree:" << endl;
        if (isEmpty()){
            cout<< "Empty Tree." << endl;
        } 
        else
            display(root,0);
    }

    void inorder(){
        cout << "\n   inorder: ";
        inorder(root);
    }
    void inorder(BinaryNode *node){
        if(node!=NULL){
            inorder(node -> getLeft());
            cout << "[" << static_cast<char>(node->getData()) << "] ";
            inorder(node -> getRight());
        }
    }
    
    void preorder() {
        cout << "\n  preorder: ";
        preorder(root);
    }
    void preorder(BinaryNode *node){
        if(node!=NULL){
            cout << "[" << static_cast<char>(node ->getData()) << "] ";
            preorder(node -> getLeft());
            preorder(node -> getRight());
        }
    }

    void postorder(){
        cout << "\n postorder: ";
        postorder(root);
    }
    void postorder(BinaryNode *node){
        if(node!=NULL){
            postorder(node -> getLeft());
            postorder(node -> getRight());
            cout << "[" << static_cast<char>(node -> getData()) << "] ";
        }
    }
    void levelorder(){
        cout << "\nlevelorder: ";
        if(!isEmpty()){
            CircularQueue q;
            q.enqueue(root);
            while(!q.isEmpty()){
                BinaryNode* n = q.dequeue();
                if(n!=NULL){
                    cout << "["<<static_cast<char>(n->getData()) << "] ";
                    q.enqueue(n->getLeft());
                    q.enqueue(n->getRight());
                }
            }
        }
        cout<<"\n";
    }

private:
    void display(BinaryNode* node , int depth){
        if (node==NULL)
            return;

        for (int i=0; i<depth; i++)
            cout<<" ";
        cout << "- " << static_cast<char>(node->getData()) << endl;
        display(node->getLeft(), depth+1);
        display(node->getRight(), depth+1);
    }
};

int main(){
    BinaryTree tree;

    BinaryNode *d = new BinaryNode('D', NULL, NULL);
    BinaryNode *e = new BinaryNode('E', NULL, NULL);
    BinaryNode *b = new BinaryNode('B', d, e);
    BinaryNode *f = new BinaryNode('F', NULL, NULL);
    BinaryNode *c = new BinaryNode('C', f, NULL);
    BinaryNode *a = new BinaryNode('A', b, c);

    tree.setRoot(a);

    tree.display();   

    tree.inorder();
    tree.preorder();
    tree.postorder();
    tree.levelorder();

    return 0;
}
profile
qzzloz
이전 포스트

09-2 덱

다음 포스트

12-1 그래프

0개의 댓글