清泉逐流

做着努力,等待幸福到来

Binary tree

作者:Eamonn 时间 : 2014-09-10 20:13 分类:C/C++

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
template <typename T>
struct BNode{
    BNode *l;
    BNode *r;
    T data;
};
template <typename T>
class BTree{
    public:
        static const int PRE_ORDER  = 1;
        static const int POST_ORDER = 2;
        static const int IN_ORDER   = 3;
           
        BTree();
        ~BTree();
        void SetEmptyValue(T value){ m_empty_value = value; }
        void Create(vector<T> &seq, const int order=PRE_ORDER);
        void Print(const int order=PRE_ORDER);
        void Delete(void);
       
    private:
        BNode<T> *m_root;
        T m_empty_value;
           
        void PrintNode(const int order=PRE_ORDER, BNode<T> *node=NULL);
        BNode<T> *CreatePreOrder(vector<T> &seq, int &index);
        BNode<T> *CreatePostOrder(vector<T> &seq, int &index);
        void DeleteNode(BNode<T> *node);
           
};
template <typename T>
BTree<T>::BTree()
{
    m_root = NULL;
}
template <typename T>
BTree<T>::~BTree()
{
    if(NULL != m_root){
        Delete();
    }
}
// Create binary tree with pre-order and post-order
template <typename T>
void BTree<T>::Create(vector<T> &seq, const int order)
{
    int index = 0;
    switch(order){
        case PRE_ORDER:
            m_root = CreatePreOrder(seq, index);
            break;
        case POST_ORDER:
            index = seq.size() - 1;
            m_root = CreatePostOrder(seq, index);
            break;
    }
       
}
template <typename T>
BNode<T> * BTree<T>::CreatePreOrder(vector<T> &seq, int &index)
{
    T c = seq.at(index);
    if(c==m_empty_value){
        return NULL;
    }
    BNode<T> *node = new BNode<T>;
    node->data = c;
    index++;
    node->l = CreatePreOrder(seq, index);
    index++;
    node->r = CreatePreOrder(seq, index);
    return node;
}
template <typename T>
BNode<T> * BTree<T>::CreatePostOrder(vector<T> &seq, int &index)
{
    T c = seq.at(index);
    if(c==m_empty_value){
        return NULL;
    }
    BNode<T> *node = new BNode<T>;
    node->data = c;
    index --;
    node->r = CreatePostOrder(seq, index);
    index --;
    node->l = CreatePostOrder(seq, index);
    return node;
}
template <typename T>
void BTree<T>::Print(const int order)
{
    PrintNode(order, m_root);
}
template <typename T>
void BTree<T>::PrintNode(const int order, BNode<T> *node)
{
    if(node){
        switch(order){
            case PRE_ORDER:
                cout << node->data << " ";
                PrintNode(order, node->l);
                PrintNode(order, node->r);
                break;
            case POST_ORDER:
                PrintNode(order, node->l);
                PrintNode(order, node->r);
                cout << node->data << " ";
                break;
            case IN_ORDER:
                PrintNode(order, node->l);
                cout << node->data << " ";
                PrintNode(order, node->r);
                break;
        }
    }else{
        cout << m_empty_value << " ";
    }
}
template <typename T>
void BTree<T>::Delete(void)
{
    DeleteNode(m_root);
    m_root = NULL;
}
template <typename T>
void BTree<T>::DeleteNode(BNode<T> *node)
{
    if(node){
        DeleteNode(node->l);
        DeleteNode(node->r);
        delete node;
    }  
}
int main(int argc, char* argv[])
{
    vector<char> seq;
    char c;
    ifstream f("binary_tree.txt");
    while(f>>c){
        seq.push_back(c);
    }
    f.close();
       
    BTree<char> bt;
       
    bt.SetEmptyValue('$');
    bt.Create(seq, BTree<char>::POST_ORDER);
       
    bt.Print(BTree<char>::IN_ORDER);
       
    bt.Delete();
       
    return 0;
}


转载注明: http://www.eamonning.com/note/view/39
» 笔记大类