Search Results for '2008/06/21'

8 POSTS

  1. 2008/06/21 [C++] Binary Search Tree

[C++] Binary Search Tree

Posted 2008/06/21 01:53
#ifndef BST_H
#define BST_H

#include <iostream>
#include <string>
using namespace std;

template<typename ItemType>
struct TreeNode
{
        ItemType info;
        TreeNode<ItemType>* left;
        TreeNode<ItemType>* right;
};

template<typename ItemType>
class BST
{
public :
        BST();   // Class Constructor
        ~BST();  // Class Destructor
        BST(const BST<ItemType>& right);  // Copy Constructor
        BST operator = (const BST<ItemType>& right); // Assignment Operator
        void RetrieveItem(ItemType& item, bool& found);  
        void InsertItem(ItemType item);  // Insert
        void DeleteItem(ItemType& item); // Delete
        int Size() const;
        int Size(string Country) const;
        void Print();
        void Print(string Country);
        bool IsFull() const;
        bool IsEmpty() const;
        int HeightIs() const;
private:
        TreeNode<ItemType>* root;
};

// Constructor //
template<typename ItemType>
BST<ItemType>::BST()
{
        root = NULL;
        // Function : Default Constructor
        // Post : 빈 리스트 생성.
};

// Copy Constructor //
template<typename ItemType>
void CopyTree(TreeNode<ItemType>*& copy, const TreeNode<ItemType>* originalTree)
{
        if (originalTree == NULL)
                copy = NULL;
        else {
                copy = new TreeNode<ItemType>;
                copy->info = originalTree->info; // Root를 복사하고
                CopyTree(copy->left, originalTree->left); // Left를 복사하고
                CopyTree(copy->right, originalTree->right); // right를 복사하고
        }
        // function : Tree를 복사한다. (Preorder Traval)
        // Pre : 멤버함수에 의해 호출이 되어야 한다.
        // Post: R-parameter를 복사하여 L-parameter로 반환하여 준다.
}

template<typename ItemType>
BST<ItemType>::BST(const BST<ItemType>& right)
{
        CopyTree(root, right.root);
        // function : Copy constructor
        // Post : BST Right를 복사한다.
}

// Assignment Operator //
template<typename ItemType>
BST<ItemType> BST<ItemType>::operator = (const BST<ItemType>& right)
{
        Destroy(root);  // 먼저 L-value를 삭제하고
        CopyTree(root, right->root); // 복사한다
        // function : Assignment Operator
        // Post : BST Right를 복사하여 L-value에 전달한다.
}

// BST Destructor //
template<typename ItemType>
void Destroy(TreeNode<ItemType>*& tree)
{
        if (tree != NULL) {
                Destroy(tree->left);  // Delete Left
                Destroy(tree->right); // Delete right
                delete tree; // Delete root
        }
        // function : 메모리를 반환한다. (Postorder Traval)
        // Pre : 멤버함수에서 호출이 되어야 한다.
        // Post: Tree is Null
};

template<typename ItemType>
BST<ItemType>::~BST()
{
        Destroy(root);
        // function : Destructor
        // Post : Tree is NULL
}

// Print Tree //
template<typename ItemType>
void PrintTree(TreeNode<ItemType>* tree)
{
        if (tree != NULL) {
                PrintTree(tree->left); // Print Left
                cout << tree->info; // Print Root
                PrintTree(tree->right); // Print Right
        }
        // function : BST를 순서대로 출력한다. (Inorder Traval)
        // Pre : BST is not empty
        // Post: 모든 원소를 순서대로 출력한다.
}

template<typename ItemType>
void BST<ItemType>::Print()
{
        PrintTree(root);
        // function : PrintTree 재귀함수를 호출한다.
        // Post : 모든원소를 순서대로 출력한다.
}

// Is Same //
template<typename ItemType>
bool IsSame(TreeNode<ItemType>* tree, string num)
{
        string temp1;
        char temp2[5];
        int count = tree->info.phone_no.LengthIs(); // 전화번호 갯수
        tree->info.phone_no.ResetList(); // SortedList Reset
        for (int i=0 ; i<count ; i++) { // 모든 전화번호와 입력받은 지역번호를 비교
                tree->info.phone_no.GetNextItem(temp1);
                for (int j=0 ; j<num.size() ; j++) // 지역번호 추출
                        temp2[j] = temp1[j];  
                temp2[j] = '\0';
                if (temp2 == num) // 같을 때
                        return true;
        }
        return false; // 다를 때
        // Function : 입력받은 지역번호와 같은 지역번호를 사용하는지 확인한다.
        // Post : 같은 지역번호를 사용하면 True, 아니면 False
}

// Print Tree Overloading //
template<typename ItemType>
void PrintTree2(TreeNode<ItemType>* tree, string Country)
{
        if (tree != NULL) {
                PrintTree2(tree->left, Country); // Print Left
                if (IsSame(tree, Country)) // Print Root
                        cout << tree->info.name << endl;
                PrintTree2(tree->right, Country); // Print Right
        }
        // Function : 지역번호와 일치한 사람의 이름을 출력. (Inorder Traval)
        // Pre : BST is not empty
        // Post: 지역번호와 일치한 사람의 이름을 순서대로 출력한다.
}

template<typename ItemType>
void BST<ItemType>::Print(string Country)
{
        PrintTree2(root, Country);
        // Function : PrintTree2 재귀함수를 호출한다.
        // Post : 지역번호와 일치한 사람의 이름을 를 순서대로 출력한다.
}

// Size //
template<typename ItemType>
int CountNodes(TreeNode<ItemType>* tree)
{
        if (tree == NULL)
                return 0;
        else
                return CountNodes(tree->left) + CountNodes(tree->right) + 1;
        // Function : Determines the number of elements in BST (Postorder Traval)
        // Post : Function value = number of elements in BST
}

template<typename ItemType>
int BST<ItemType>::Size() const
{
        return CountNodes(root);
        // Function : CountNodes 함수를 호출한다.
        // Post : 모든 원소의 갯수를 반환한다.
}

// Size Function Overloading //
template<typename ItemType>
int CountNodes(TreeNode<ItemType>* tree, string Country)
{
        if (tree == NULL)
                return 0;
        else {
                if (IsSame(tree, Country)) // 일치하면 Left count + Right count + 1
                        return CountNodes(tree->left, Country) + CountNodes(tree->right, Country) + 1;
                else // 일치하지 않으면 Left count + Right count
                        return CountNodes(tree->left, Country) + CountNodes(tree->right, Country);
        }
        // Function : 지역번호가 일치한 원소의 갯수를 센다. (postorder Traval)
        // Post : 지역번호가 일치한 원소의 갯수를 반환한다.
}

template<typename ItemType>
int BST<ItemType>::Size(string Country_no) const
{
        return CountNodes(root,Country_no);
        // Function : CountNodes 재귀 함수를 호출한다.
        // Post : 지역번호가 일치한 원소의 갯수를 반환한다.
}

// Retrieve Item //
template<typename ItemType>
void Retrieve(TreeNode<ItemType>* tree, ItemType& item, bool& found)
{
        if (tree == NULL)
                found = false; // 못찾을 경우
        else if (item.name < tree->info.name) // BST보다 작을경우
                Retrieve(tree->left, item, found);
        else if (item.name > tree->info.name) // BST보다 클 경우
                Retrieve(tree->right, item, found);
        else { // 찾았을 경우
                item = tree->info;
                found = true;
        }
        // Function : Key값이 일치한 원소를 찾는다.
        // Pre : Item의 Key값은 초기화 되어 있어야 한다.
        //       BST is not empty
        // Post : 찾았으면 found는 Ture이고 Item에 원소가 복사된다.
}

template<typename ItemType>
void BST<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
        Retrieve(root, item, found);
        // Function : Retrieve함수를 호출한다.
        // Pre : Item의 Key값은 초기화 되어 있어야 한다.
        //       BST is not empty
        // Post : 찾았으면 found는 Ture이고 Item에 원소가 복사된다.
}

// Insert Item //
template<typename ItemType>
void Insert(TreeNode<ItemType>*& tree, ItemType& item)
{
        if (tree == NULL) { // Insert as first
                tree = new TreeNode<ItemType>;
                tree->right = NULL;
                tree->left = NULL;
                tree->info = item;
        }
        else if (item.name < tree->info.name) // Item값이 작을경우
                Insert(tree->left, item);
        else // Item값이 클 경우
                Insert(tree->right, item);
        // Function : Adds item to BST.
        // Pre : List is not full.
        //       Item is not in BST
        // Post: item이 삽입된다.
}

template<typename ItemType>
void BST<ItemType>::InsertItem(ItemType item)
{
        Insert(root, item);
        // Function : Insert 재귀함수를 호출한다.
        // Pre : List is not full.
        //       Item is not in BST
        // Post: item이 삽입된다.
}

// Delete Item //
template<typename ItemType>
void GetPredecessor(TreeNode<ItemType>* tree, ItemType& data)
{
        while (tree->right != NULL)
                tree = tree->right;
        data = tree->info;
        // Function : 가장 큰 값을 찾는다.
        // Pre : List is not empty.
        // Post: 가장 큰 원소를 찾아서 data를 반환한다.
}

template<typename ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType& item);

template<typename ItemType>
void DeleteNode(TreeNode<ItemType>*& tree)
{
        ItemType data;
        TreeNode<ItemType>* tempPtr;
        tempPtr = tree;
        if (tree->left == NULL) { // 오른쪽 child와 Node가 없을 때
                tree = tree->right;
                delete tempPtr;
        }
        else if (tree->right == NULL) { // 왼쪽 child만 갖고 있을 때
                tree = tree->left;
                delete tempPtr;
        }
        else { // child를 둘다 갖고 있을 때
                GetPredecessor(tree->left, data); // 왼쪽에서 가장 큰 원소를 찾아서
                tree->info = data; // 값을 저장하고
                Delete(tree->left, data); // 왼쪽에서 가장 큰 원소를 삭제한다.
        }
        // Function : item과 일치한 Node를 삭제한다.
        // Pre : List is not empty.
        // Post: item과 일치한 Node가 삭제된다.
}

template<typename ItemType>
void Delete(TreeNode<ItemType>*&tree, ItemType& item)
{
        if (item.name < tree->info.name)
                Delete(tree->left, item);
        else if(item.name > tree->info.name)
                Delete(tree->right, item);
        else
                DeleteNode(tree);
        // Function : Delete할 원소를 찾는다.
        // Pre : List is not empty.
        //       Item is in BST
        // Post: 삭제할 아이템의 위치를 찾은 후 DeleteNode로 넘겨준다.
}

template<typename ItemType>
void BST<ItemType>::DeleteItem(ItemType& item)
{
        Delete(root, item);
        // Function : Delete 재귀함수를 호출한다.
        // Pre : List is not empty.
        //       Item is in BST
        // Post: item이 삭제된다.
}

// Is Full //
template<typename ItemType>
bool BST<ItemType>::IsFull() const
{
        TreeNode<ItemType>* location;
        try
        {
                location = new TreeNode<ItemType>;
                delete location;
                return false;
        }
        catch (bad_alloc exception)
        {
                return true;
        }
        // Function : Determines whether BST is full.
        // Post : Function value = (BST is full)
}

// Is Empty //
template<typename ItemType>
bool BST<ItemType>::IsEmpty() const
{
        return root == NULL;
        // Function : Determines whether BST is empty.
        // Post : Function value = (BST is empty)
}
template<typename ItemType>
int Height(TreeNode<ItemType>* tree)
{
        if (tree == NULL) // Tree가 Empty일 때
                return -1;
        else
        {
                int lheight = Height(tree->left); // 왼쪽을세고
                int rheight = Height(tree->right); // 오른쪽을 세고
                if(lheight > rheight) // 큰쪽의 높이에 자신을 추가한다.
                        return lheight + 1;
                else
                        return rheight + 1;
        }
        // Function : BST의 높이를 센다.
        // Post: 높이를 반환한다.
}

template<typename ItemType>
int BST<ItemType>::HeightIs() const
{
        return Height(root);
        // Function : Height 비멤버 함수를 호출한다.
        // Post: 높이를 반환한다.
}

#endif
이올린에 북마크하기

'C.S.E > Data Structure' 카테고리의 다른 글

[C++] Binary Search Tree  (0) 2008/06/21
[C++] Unsorted List  (0) 2008/06/21
[C++] Linked List 방식의 Sorted List  (0) 2008/06/21
[C++] Sorted List  (0) 2008/06/21
[C++] Linked List 방식의 Queue  (0) 2008/06/21
[C++] Queue  (0) 2008/06/21
« PREV : 1 : 2 : 3 : 4 : 5 : ... 8 : NEXT »