[c++][자료구조] Complete Binary Tree (완전 이진 트리) 구현 및 응용 함수들

STL container 중 하나인 트리 중 Complete Binary Tree (완전 이진 트리)를 구현해보았다.

그리고 응용 함수들을 만들어 보았다.

 

구현

 

Struct

 

struct TreeNode{
    int key; // node 속 data 저장
    TreeNode* left;
    TreeNode* right;

    TreeNode(int k, TreeNode* l , TreeNode* r){
        key = k;
        left = l;
        right = r;
    }
    TreeNode(int k) : key(k), left(nullptr), right(nullptr){}
    
    ~TreeNode(){}
};

using tree = TreeNode*;

 

 

기본 함수들

 

empty : 비어있다면 true 반환 , 아니면 false 반환.

 

bool empty(tree root){
    return (root==nullptr);
}

 

 

size : node 의 갯수 출력

 

int size(tree root){
    if(empty(root)) return 0;

    return (size(root->left) + size(root->right) + 1);
}

 

 

height : 트리의 높이 반환

 

int height(tree root){
    if(empty(root)) return -1;

    return max(height(root->left) , height(root->right)) +1;
}

 

 

트리 BFS , DFS 함수

 

1) DFS : recursion 이용.

 

Inorder : v에 inorder 순서로 tree를 저장.

 

void inorder(tree root , vector<int> &v){
    if(empty(root)) return;

    inorder(root->left, v);
    v.push_back(root->key);
    inorder(root->right , v);
}

 

 

Preorder : v에 preorder 순서로 tree를 저장.

 

void preorder(tree root , vector<int> &v){
    if(empty(root)) return;

    v.push_back(root->key);
    preorder(root->left, v);
    preorder(root->right, v);
}

 

 

Postorder : v에 Postorder 순서로 tree를 저장.

 

void postorder(tree root, vector<int> &v){
    if(root==nullptr) return;

    postorder(root->left, v);
    postorder(root->right ,v);
    v.push_back(root->key);
}

 

 

2) BFS : queue를 이용.

 

BFS_order : tree를 BFS 순서로 담은 벡터 반환.

 

vector<int> BFS_order(tree root){
    vector<int> v;

    if(empty(root)) return v;


    queue<tree> q;
    q.push(root);
    
    while(!q.empty()){
        tree node = q.front();
        v.push_back(node->key);
        q.pop();

        if(node->left != nullptr) q.push(node->left);
        if(node->right != nullptr) q.push(node->right);
    }

    return v;
}

 

 

응용함수들

 

maximumBT : 가장 큰 값을 가지고 있는 노드 반환.

 

tree maximumBT(tree root)
    if(empty(root)) return nullptr;

    tree max = root;

    if( maximumBT(root->left) && root->left->key > max->key) max = root->left ;
    if( maximumBT(root->right) && root->right->key > max->key) max = root->right ;
    
    return max;
}

 

 

findpath : root -> x (특정 노드) 까지의 길을 벡터 v에 저장.

 

bool findPath(tree root , tree x , vector<int> &v){
    if(empty(root)) return false;

    v.push_back(root->key);

    if(findPath(root->left , x , v) || findPath(root->right , x , v) || (root->key == x->key)) return true;

    v.pop_back();
    
    return false;
}

 

 

findpathback : x(특정 노드) -> root 까지의 길을 벡터 v에 저장

 

bool findPathBack(tree root , tree x , vector<int> &v){
    if(empty(root)) return false;

    if(findPathBack(root->left,x,v) || findPathBack(root->right,x,v) || (root->key == x->key)){
        v.push_back(root->key);
        return true;
    }

    return false;
}

 

 

LCA_BT : 두 특정 노드의 공동 상위 노드 중 가장 가까운 것을 반환. (recursion 이용)

 

tree LCA_BT(tree root, tree p , tree q){
    if(empty(root)) return nullptr;

    if(root==p || root ==q) return root;

    tree left = LCA_BT(root->left , p, q);
    tree right = LCA_BT(root->right , p, q);

    if(left && right) return root;
    else if(left && !right) return left;
    else if(!left && right) return right;
    return nullptr;
}

 

 

LCA_BT_iteration : 두 특정 노드의 공동 상위 노드 중 가장 가까운 것을 반환. (iteration 이용)

 

int LCA_BTiteration(tree root , tree p , tree q){
    if(empty(root)) return -1;
    vector<int> p_vec;
    vector<int> q_vec;
    int answer = -1;
    if(findPath(root,p,p_vec) && findPath(root,q,q_vec) ){
        if(p_vec > q_vec){
            for(int i = 0 ; i < q_vec.size() ; ++i){
                if(p_vec[i] == q_vec[i]) answer = p_vec[i];
            }
        }
        else{
            for(int i = 0 ; i < p_vec.size() ; ++i){
                if(p_vec[i] == q_vec[i]) answer = p_vec[i];
            }
        }
    }

    return answer;
}

 

 

 

makeTree_BFS : 벡터를 트리로 변환 시켜주는 함수. BFS 순서로 만듦.

 

tree makeTree_BFS(tree root, vector<int> v){
    if(v.empty()) return nullptr;

    queue<tree> q;

    root->key = v[0];
    int i = 1;

    q.push(root);

    while(i < v.size()){
        tree Node = q.front();
        q.pop();
        Node->left = new TreeNode(v[i]);
        i++;
        q.push(Node->left);

        if(i >= v.size()) break;
        Node->right = new TreeNode(v[i]);
        i++;
        q.push(Node->right);
    }

    return root;
}

 

---

 

Tree를 통해 만든 STL container에는 map이 있다.

map은 프로그래밍 문제를 풀 때 자주 사용된다.

map에 대해 궁금 하다면 아래 글을 참고하자!

 

2022.02.20 - [c++/문법] - [c++][자료구조] Map STL 정리 및 예제

[c++][자료구조] Map STL 정리 및 예제