[자료구조] C++트리 설명 및 구현(이진트리)/이진트리 구현

트리란?

 

트리란 확장된 반순서의 구조를 가지는 자료구조이다. 구조적으로 그래프와 선형 자료구조들 (벡터와 같은 것들) 사이에 있다고 볼 수 있다. 즉 트리는 1:N 비선형 계층형 자료구조이다.

바이너리 트리

트리에서 사용되는 용어는 아래와 같다.

- node : 트리를 구성하고 있는 기본 요소(위 그림의 1, 2, 3 ...)

- edge(간선) : 노드를 연결하는 선

- root node(루트 노드) : 부모가 없는 노드, 트리 구조는 단 하나의 루트 노드만을 가진다.(위 그림의 1)

- leaf node(단말 노드) : 자식이 없는 노드(위 그림의 8, 9, 10, 11, 13, 14)

- internal node(내부 노드) : leaf node가 아닌 노드, 즉 자식 노드를 하나 이상 가지는 노드

- subtree : 하나의 큰 트리를 구성하는 작은 트리, 위 그림에서 2로 시작되는 왼쪽 트리와, 3으로 시작되는 오른쪽 트리가 1로 시작되는 큰 트리의 서브트리이다.

(그 서브트리 또한 다른 서브트리로 이루어져 있다. 즉 트리는 구조는 재귀적이다)

- parents : 한 노드의 상위 노드, 노드 1은 노드 2의 parent이다.

- child : 하위 노드, 노드 2의 child노드는 4와 5이다.

- sibling : 같은 부모를 가지고 레벨이 같은 노드이다. 즉, 2와 3

- depth : 루트에서 어떤 노드까지의 간선 수이다. root는 깊이가 0이다. 노드 4는 깊이가 2이다.

- height : 루트 노드에서 가장 깊숙이 있는 노드의 깊이이다. 위 그림에서 height는 3

- degree : 각 노드가 지닌 가지의 수이다, 즉 자식의 수이다.

 

이진트리

 

이진트리란 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이진 트리에는 정이진트리, 완전이진트리, 편향이진트리, 포화이진트리 등이 존재한다.

 

이진트리의 특징은 아래와 같다.

이진트리 특징

- 차수가 2인 트리

- 왼쪽 자식과 오른쪽 자식을 구분하는 트리

- 공복 노드(빈 노드)도 자식 노드로 취급

- 모든 원소는 유일한 키값을 가짐

- 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값

- 오른쪽 서브트리의 모든 원소들은 루트의 키보다 큰 값

 

*정이진트리

모든 레벨의 노드들이 꽉 채우진 트리이다.

 

*완전이진트리

마지막 레벨을 제외한 모든 노드가 2개씩 꽉 채워진 트리

 

배열로 이진트리 구현

 

#include <iostream>
 
using namespace std;
int main(){
char arr[] = {' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g'};//index 0는 빈 공간
int n;
/* 트리의 형태
   a/ \b c/\ /\d e f g
*/
cin>>n;
cout<<"parent node of "<<n<<"  "<<arr[2*n]<<" and "<<arr[2*n+1];
return 0;
}

클래스로 이진트리 구현

 

#include <iostream>
#include <vector>
 
using namespace std;
 
class Node{
public:
    int data;
 
    Node(int _data){
        data = _data;
    }
    Node *left, *right;
};
 
Node* newNode(int d){
    Node* temp = new Node(d);
    temp->left = temp->right = NULL;
    return temp;
}
void preOrder(Node* root){//root->left->right
    if(!root) return;
    cout<<root->data<<" ";//우선 루트에서 출력 후
    preOrder(root->left);//왼쪽부터 탐색
    preOrder(root->right);
 
}
void inOrder(Node* root){//left->root->right
    if(!root) return;
    inOrder(root->left);//왼쪽부터 탐색 후
    cout<<root->data<<" ";//출력
    inOrder(root->right);
}
 
void postOrder(Node* root){//left->right->root
    if(!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->data<<" ";//출력
}
 
 
int getDepth(Node* root){
    int leftDepth, rightDepth = 0;
 
    if(!root->right || !root->left) return 0;//leaf인 경우
    leftDepth = getDepth(root->left);
    rightDepth = getDepth(root->right);
 
    return max(leftDepth, rightDepth)+1;
}
 
void getLeaf(Node* root, vector<Node*>* nodeVector){
    if(!root->left && !root->right){
        nodeVector->push_back(root);
        return;
    }
    getLeaf(root->left, nodeVector);
    getLeaf(root->right, nodeVector);
}
 
int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
/*
        1
       / \
      2   3
     /\
    4 5
  */
    cout<<"PreOrder : ";
    preOrder(root);
    cout<<endl;
    cout<<"InOrder : ";
    inOrder(root);
    cout<<endl;
    cout<<"PostOrder : ";
    postOrder(root);
    cout<<endl;
 
 
 
    vector<Node*> reafs;
    getLeaf(root, &reafs);
    for(auto r:reafs){
        cout<<r->data<<" ";
    }
 
}

 

 한 노드가 두 개의 노드를 포인터로 가리키고 있는 구조이다. 이후의 편의를 위해 생성자는 함수로 구현하고, 함수 내에서 다음 left와 right는 NULL로 초기화해주었다.(이후 reaf여부를 판단하는 데 도움을 줄 것이다.)

 

출력은 Preorder, Inorder, Postorder 세 가지로 구현하였다.

 

Preorder(전위) : root->left->right의 순서를 가진다.

Inorder(중위) : left->root->right의 순서를 가진다.

Postorder(후위) : left -> right -> root의 순서를 가진다.