logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

无聊时写过的一点代码，包括二叉树、二叉树模板、平衡二叉树模板，对某些人可能有用，呵呵...

 SpringEmpire 2007-09-12
 
 无聊时写过的一点代码，包括二叉树、二叉树模板、平衡二叉树模板，对某些人可能有用，呵呵
/* A binary tree
 * by cookie.chao@gmail.com
 * Oct 1, 2006
 */
#include <iostream.h>
#include <vector>
#include <string>
 
class BTnode
{
        friend class BTree;
    public:
        BTnode();
        BTnode(int &);
        BTnode operator=(BTnode &);
        ~BTnode();
    private:
        int     _val;
        int     _cnt;
        BTnode  *_lchild;
        BTnode  *_rchild;
};
 
inline BTnode::BTnode()
{
    _val = 0;
    _cnt = 1;
    _lchild = 0;
    _rchild = 0;
}
inline BTnode::BTnode(int &s)
{
    _val = s;
    _cnt = 1;
    _lchild = 0;
    _rchild = 0;
}
inline BTnode::~BTnode()
{
}
BTnode BTnode::operator=(BTnode &rhs)
{
    _val = rhs._val;
    _cnt = rhs._cnt;
    _lchild = rhs._lchild;
    _rchild = rhs._rchild;
    return rhs;
}
 
class BTree
{
        friend class BTnode;
    public:
        void    add(int &);
        void    addtonode(BTnode *, int &);
        bool    rmove(int &);
        bool    pre_traversal();
        bool    pre_traversal_node(BTnode *t);
        bool    mid_traversal();
        bool    post_traversal();
        bool    empty() { return _root == 0; }
        void    clear();
        void    del_node(BTnode *);
        BTree();
        BTree(int &);
        BTree(BTree &);
        ~BTree();
    private:
        BTnode  *_root;
};
BTree::BTree()
{
    _root = 0;
}
BTree::BTree(int &s)
{
    BTnode root(s);
    _root = &root;
}
BTree::~BTree()
{
    clear();
}
void BTree::addtonode(BTnode *node, int &s)
{
    if( s == node->_val)
    {
        (node->_cnt)++;
    }
    else if(s > node->_val)
    {
        if(node->_rchild == 0)
        {
            BTnode *pn = new BTnode(s);
            node->_rchild = pn;
        }
        else
        {
            addtonode(node->_rchild, s);
        }
    }
    else
    {
        if(node->_lchild == 0)
        {
            BTnode *pn = new BTnode(s);
            node->_lchild = pn;
        }
        else
        {
            addtonode(node->_lchild, s);
        }
    }
}
void BTree::add(int &s)
{
    if(_root == 0)
    {
        BTnode *pn = new BTnode(s);
        _root = pn;
    }
    else
    {
        addtonode(_root, s);
    }
}
bool BTree::pre_traversal()
{
    pre_traversal_node(_root);
    return true;
}
bool BTree::pre_traversal_node(BTnode* root)
{
    if(root == 0)
    {
        return false;
    }
    cout<<root->_val<<" "<<root->_cnt<<endl;
    pre_traversal_node(root->_lchild);
    pre_traversal_node(root->_rchild);
    return true;
}
void BTree::clear()
{
    del_node(_root);
    return;
}
void BTree::del_node(BTnode *root)
{
    if( (root->_lchild == 0) && (root->_rchild == 0) )
    {
        delete root;
        return;
    }
    else
    {
        if(root->_lchild != 0)
        {
            del_node(root->_lchild);
            root->_lchild = 0;
        }
        if(root->_rchild != 0)
        {
            del_node(root->_rchild);
            root->_rchild = 0;
        }
        return;
    } 
}
 
void main()
{
    int s;
    BTree t;
    s = 2;
    t.add(s);
    s = 1;
    t.add(s);
    t.add(s);
    t.add(s);
    s = 2;
    t.add(s);
    s = 0;
    t.add(s);
    t.add(s);
    s = 3;
    t.add(s);
    s = 4;
    t.add(s);
    t.pre_traversal();
}



 /* A binary tree using template
 * by cookie.chao@gmail.com
 * Oct 5, 2006
 */
#include <iostream>
#include <vector>
#include <string>
////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
template<typename Type>
class BTree;
 
template<typename Type>
class BTnode
{
    friend class BTree<Type>;
public:
    BTnode();
    BTnode(Type &);
    BTnode operator=(BTnode &);
    ~BTnode();
private:
    Type     _val;
    int     _cnt;
    BTnode    *_lchild;
    BTnode    *_rchild;
};
 
template<typename Type>
inline BTnode<Type>::BTnode()
{
    _val = 0;
    _cnt = 1;
    _lchild = 0;
    _rchild = 0;
}
template<typename Type>
inline BTnode<Type>::BTnode(Type &s)
{
    _val = s;
    _cnt = 1;
    _lchild = 0;
    _rchild = 0;
}
template<typename Type>
inline BTnode<Type>::~BTnode()
{
}
template<typename Type>
BTnode<Type> BTnode<Type>::operator=(BTnode<Type> &rhs)
{
    _val = rhs._val;
    _cnt = rhs._cnt;
    _lchild = rhs._lchild;
    _rchild = rhs._rchild;
    return rhs;
}
////////////////////////////////////////////////////////////////////////////////
template<typename Type>
class BTree
{
    friend class BTnode<Type>;
public:
    void    add(Type &);
    void    addtonode(BTnode<Type> *, Type &);
    bool    rmove(Type &);
    bool    pre_traversal();
    bool    mid_traversal();
    bool    post_traversal();
    bool    pre_traversal_node(BTnode<Type> *t);
    bool    mid_traversal_node(BTnode<Type> *t);
    bool    post_traversal_node(BTnode<Type> *t);
    bool    empty() { return _root == 0; }
    void    clear();
    void    del_node(BTnode<Type> *);
    BTree();
    BTree(Type &);
    BTree(BTree<Type> &);
    ~BTree();
private:
    BTnode<Type>  *_root;
};
template<typename Type>
BTree<Type>::BTree()
{
    _root = 0;
}
template<typename Type>
BTree<Type>::BTree(Type &s)
{
    BTnode<Type> root(s);
    _root = &root;
}
template<typename Type>
BTree<Type>::~BTree()
{
    clear();
}
template<typename Type>
void BTree<Type>::addtonode(BTnode<Type> *node, Type &s)
{
    if(s == node->_val)
    {
        (node->_cnt)++;
    }
    else if(s > node->_val)
    {
        if(node->_rchild == 0)
        {
            BTnode<Type> *pn = new BTnode<Type>(s);
            node->_rchild = pn;
        }
        else
        {
            addtonode(node->_rchild, s);
        }
    }
    else
    {
        if(node->_lchild == 0)
        {
            BTnode<Type> *pn = new BTnode<Type>(s);
            node->_lchild = pn;
        }
        else
        {
            addtonode(node->_lchild, s);
        }
    }
}
template<typename Type>
void BTree<Type>::add(Type &s)
{
    if(_root == 0)
    {
        BTnode<Type> *pn = new BTnode<Type>(s);
        _root = pn;
    }
    else
    {
        addtonode(_root, s);
    }
}
///////////////////////////////////////////////////////////////////////
//先序遍历
template<typename Type>
bool BTree<Type>::pre_traversal()
{
    pre_traversal_node(_root);
    return true;
}
template<typename Type>
bool BTree<Type>::pre_traversal_node(BTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    cout<<root->_val<<" "<<root->_cnt<<endl;
    pre_traversal_node(root->_lchild);
    pre_traversal_node(root->_rchild);
    return true;
}
///////////////////////////////////////////////////////////////////////
//中序遍历
template<typename Type>
bool BTree<Type>::mid_traversal()
{
    mid_traversal_node(_root);
    return true;
}
template<typename Type>
bool BTree<Type>::mid_traversal_node(BTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    mid_traversal_node(root->_lchild);
    cout<<root->_val<<" "<<root->_cnt<<endl;
    mid_traversal_node(root->_rchild);
    return true;
}
///////////////////////////////////////////////////////////////////////
//后序遍历
template<typename Type>
bool BTree<Type>::post_traversal()
{
    post_traversal_node(_root);
    return true;
}
template<typename Type>
bool BTree<Type>::post_traversal_node(BTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    post_traversal_node(root->_lchild);
    post_traversal_node(root->_rchild);
    cout<<root->_val<<" "<<root->_cnt<<endl;
    return true;
}
///////////////////////////////////////////////////////////////////////
template<typename Type>
void BTree<Type>::clear()
{
    del_node(_root);
    return;
}
template<typename Type>
void BTree<Type>::del_node(BTnode<Type> *root)
{
    if( (root->_lchild == 0) && (root->_rchild == 0) )
    {
        delete root;
        return;
    }
    else
    {
        if(root->_lchild != 0)
        {
            del_node(root->_lchild);
            root->_lchild = 0;
        }
        if(root->_rchild != 0)
        {
            del_node(root->_rchild);
            root->_rchild = 0;
        }
        return;
    }  
}
////////////////////////////////////////////////////////////////////////////
void main()
{
    int i;
    cout<<"BTree<int>\n";
    BTree<int> t;
    i = 5;
    t.add(i);
    i = 3;
    t.add(i);
    i = 7;
    t.add(i);
    i = 1;
    t.add(i);
    i = 4;
    t.add(i);
    i = 6;
    t.add(i);
    i = 8;
    t.add(i);
    cout<<"pre\n";
    t.pre_traversal();
    cout<<"mid\n";
    t.mid_traversal();
    cout<<"post\n";
    t.post_traversal();
    cout<<"BTree<string>\n";
    string s;
    BTree<string> st;
    s = "abbaa";
    st.add(s);
    s = "bbbbb";
    st.add(s);
    s = "abaaa";
    st.add(s);
    s = "aaaaa";
    st.add(s);
    st.add(s);
    st.pre_traversal();
    cout<<"BTree<char>\n";
    BTree<char> ct;
    char c;
    c = 'd';
    ct.add(c);
    c = 'a';
    ct.add(c);
    c = 'e';
    ct.add(c);
    c = 'f';
    ct.add(c);
    c = 'd';
    ct.add(c);
    ct.pre_traversal();
}
 
 
 
 
 /* A balance binary tree using template
 * by cookie.chao@gmail.com
 * Oct 5, 2006
 */
//尚未完成对值的删除的操作
//此时删除，如果该值所在的结点的_cnt变为0，则将会删除以该结点为根结点的子树
//并且，删除后没有进行旋转，可能破坏树的平衡性
 
#include <iostream>
#include <vector>
#include <string>
using namespace std;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template<typename Type> class BBTree;
 
template<typename Type> class BBTnode            //结点
{
    friend class BBTree<Type>;
public:
    BBTnode();
    BBTnode(const Type &);
    BBTnode operator=(const BBTnode &);
    ~BBTnode();
private:
    Type     _val;                    //结点的值
    int     _cnt;                    //出现的次数
    int        _bf;                //平衡度
    BBTnode    *_lchild;                //左子树
    BBTnode    *_rchild;                //右子树
};
 
template<typename Type> inline BBTnode<Type>::BBTnode()
{
    _val = 0;
    _cnt = 1;
    _bf = 0;
    _lchild = 0;
    _rchild = 0;
}
 
template<typename Type> inline BBTnode<Type>::BBTnode(const Type &s)
{
    _val = s;
    _cnt = 1;
    _bf = 0;
    _lchild = 0;
    _rchild = 0;
}
 
template<typename Type> inline BBTnode<Type>::~BBTnode()
{
}
 
template<typename Type> BBTnode<Type> BBTnode<Type>::operator=(const BBTnode<Type> &rhs)
{
    _val = rhs._val;
    _cnt = rhs._cnt;
    _bf = rhs._bf;
    _lchild = rhs._lchild;
    _rchild = rhs._rchild;
    return rhs;
}
////////////////////////////////////////////////////////////////////////////////
template<typename Type> class BBTree
{
    friend class BBTnode<Type>;
public:
    void    add(const Type &);                    //添加一个值
    bool    remove(const Type &);                    //删除一个值
    bool    pre_traversal();                    //先序遍历
    bool    mid_traversal();                    //中序遍历
    bool    post_traversal();                    //后序遍历
    bool    empty() { return _root == 0; }                //是否为空
    void    clear();                        //清空
    int        get_depth(BBTnode<Type> *);            //取得树的深度
    BBTnode<Type>*    r_rotate(BBTnode<Type> *);            //右旋
    BBTnode<Type>*    l_rotate(BBTnode<Type> *);            //左旋
    BBTree();
    BBTree(const Type &);
    BBTree(const BBTree<Type> &);
    ~BBTree();
private:
    BBTnode<Type>  *_root;
    BBTnode<Type>*    addtonode(BBTnode<Type> *, const Type &);
    bool    pre_traversal_node(BBTnode<Type> *);
    bool    mid_traversal_node(BBTnode<Type> *);
    bool    post_traversal_node(BBTnode<Type> *);
    bool    remove_node(BBTnode<Type> *, const Type &);
    void    del_node(BBTnode<Type> *);                //删除子树
};
 
template<typename Type> int BBTree<Type>::get_depth(BBTnode<Type> *root)
{
    if(root == 0)
        return 0;
    int depth, l_depth, r_depth;
    if((root->_lchild == 0) && (root->_rchild == 0))
        return 1;
    l_depth = get_depth(root->_lchild);
    r_depth = get_depth(root->_rchild);
    depth = l_depth > r_depth ? l_depth:r_depth;
    ++depth;
    return depth;
}
 
template<typename Type> BBTree<Type>::BBTree()
{
    _root = 0;
}
 
template<typename Type> BBTree<Type>::BBTree(const Type &s)
{
    BBTnode<Type> root(s);
    _root = &root;
}
 
template<typename Type> BBTree<Type>::~BBTree()
{
    clear();
}
 
template<typename Type> void BBTree<Type>::add(const Type &s)
{
    if(_root == 0)
    {
        BBTnode<Type> *pn = new BBTnode<Type>(s);
        _root = pn;
    }
    else
    {
        _root = addtonode(_root, s);
    }
}
 
template<typename Type> bool BBTree<Type>::remove(const Type &val)
{
    if(_root == 0)
    {
        cout<<"Can't remove element because there doesn't exit such an element\n";
        return false;
    }
    return remove_node(_root, val);
}
 
template<typename Type> bool BBTree<Type>::remove_node(BBTnode<Type> *root, const Type &val)
{
    if(root->_val == val)
    {
        --root->_cnt;
        if(root->_cnt == 0)
        {
            //delete root;
            //root = 0;
            return true;
        }
        return false;
    }
    else if(root->_val < val)
    {
        if(root->_rchild == 0)
        {
            cout<<"Can't remove element because there doesn't exit such an element\n";
            return false;
        }
        else if(remove_node(root->_rchild, val))
        {
            if(root->_rchild->_cnt == 0)
            {
                del_node(root->_rchild);
                root->_rchild = 0;
            }
            root->_bf = get_depth(root->_lchild) - get_depth(root->_rchild);
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        if(root->_lchild == 0)
        {
            cout<<"Can't remove element because there doesn't exit such an element\n";
            return false;
        }
        else if(remove_node(root->_lchild, val))
        {
            if(root->_lchild->_cnt == 0)
            {
                del_node(root->_lchild);
                root->_lchild = 0;
            }
            root->_bf = get_depth(root->_lchild) - get_depth(root->_rchild);
            return true;
        }
        else
        {
            return false;
        }
    }
}
 
template<typename Type> BBTnode<Type>* BBTree<Type>::addtonode(BBTnode<Type> *node, const Type &s)
{
    if(s == node->_val)
    {
        (node->_cnt)++;
        return node;
    }
    else if(s > node->_val)
    {
        if(node->_rchild == 0)
        {
            BBTnode<Type> *pn = new BBTnode<Type>(s);
            node->_rchild = pn;
            --node->_bf;
        }
        else
        {
            node->_rchild = addtonode(node->_rchild, s);
            node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
            if(node->_bf == -2)
            {
                if(node->_rchild->_bf == -1)
                {
                    node = l_rotate(node);
                    node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
                    node->_lchild->_bf = get_depth(node->_lchild->_lchild) - get_depth(node->_lchild->_rchild);
                }
                if(node->_rchild->_bf == 1)
                {
                    node->_rchild = r_rotate(node->_rchild);
                    node = l_rotate(node);
                    node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
                    node->_lchild->_bf = get_depth(node->_lchild->_lchild) - get_depth(node->_lchild->_rchild);
                    node->_rchild->_bf = get_depth(node->_rchild->_lchild) - get_depth(node->_rchild->_rchild);
                }
            }
        }
    }
    else
    {
        if(node->_lchild == 0)
        {
            BBTnode<Type> *pn = new BBTnode<Type>(s);
            node->_lchild = pn;
            ++node->_bf;
        }
        else
        {
            node->_lchild = addtonode(node->_lchild, s);
            node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
            if(node->_bf == 2)
            {
                if(node->_lchild->_bf == 1)
                {
                    node = r_rotate(node);
                    node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
                    node->_rchild->_bf = get_depth(node->_rchild->_lchild) - get_depth(node->_rchild->_rchild);
                }
                if(node->_lchild->_bf == -1)
                {
                    node->_lchild = l_rotate(node->_lchild);
                    node = r_rotate(node);
                    node->_bf = get_depth(node->_lchild) - get_depth(node->_rchild);
                    node->_lchild->_bf = get_depth(node->_lchild->_lchild) - get_depth(node->_lchild->_rchild);
                    node->_rchild->_bf = get_depth(node->_rchild->_lchild) - get_depth(node->_rchild->_rchild);
                }
            }
        }
    }
    return node;
}
 
template<typename Type> BBTnode<Type>* BBTree<Type>::r_rotate(BBTnode<Type> *node)
{
    cout<<"r_rotate "<<node->_val<<" with "<<node->_lchild->_val<<endl;
    BBTnode<Type> *temp;
    temp = node->_lchild;
    node->_lchild = node->_lchild->_rchild;
    temp->_rchild = node;
    return temp;
}
template<typename Type> BBTnode<Type>* BBTree<Type>::l_rotate(BBTnode<Type> *node)
{
    cout<<"l_rotate "<<node->_val<<" with "<<node->_rchild->_val<<endl;
    BBTnode<Type> *temp;
    temp = node->_rchild;
    node->_rchild = node->_rchild->_lchild;
    temp->_lchild = node;
    return temp;
}
///////////////////////////////////////////////////////////////////////
//先序遍历
template<typename Type> bool BBTree<Type>::pre_traversal()
{
    pre_traversal_node(_root);
    return true;
}
template<typename Type> bool BBTree<Type>::pre_traversal_node(BBTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    cout<<"val:"<<root->_val<<" cnt:"<<root->_cnt<<" bf:"<<root->_bf<<endl;
    pre_traversal_node(root->_lchild);
    pre_traversal_node(root->_rchild);
    return true;
}
///////////////////////////////////////////////////////////////////////
//中序遍历
template<typename Type> bool BBTree<Type>::mid_traversal()
{
    mid_traversal_node(_root);
    return true;
}
template<typename Type> bool BBTree<Type>::mid_traversal_node(BBTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    mid_traversal_node(root->_lchild);
    cout<<"val:"<<root->_val<<" cnt:"<<root->_cnt<<" bf:"<<root->_bf<<endl;
    mid_traversal_node(root->_rchild);
    return true;
}
///////////////////////////////////////////////////////////////////////
//后序遍历
template<typename Type> bool BBTree<Type>::post_traversal()
{
    post_traversal_node(_root);
    return true;
}
template<typename Type> bool BBTree<Type>::post_traversal_node(BBTnode<Type>* root)
{
    if(root == 0)
    {
        return false;
    }
    post_traversal_node(root->_lchild);
    post_traversal_node(root->_rchild);
    cout<<"val:"<<root->_val<<" cnt:"<<root->_cnt<<" bf:"<<root->_bf<<endl;
    return true;
}
///////////////////////////////////////////////////////////////////////
template<typename Type> void BBTree<Type>::clear()
{
    del_node(_root);
    return;
}
template<typename Type> void BBTree<Type>::del_node(BBTnode<Type> *root)
{
    if( (root->_lchild == 0) && (root->_rchild == 0) )
    {
        delete root;
        return;
    }
    else
    {
        if(root->_lchild != 0)
        {
            del_node(root->_lchild);
            root->_lchild = 0;
        }
        if(root->_rchild != 0)
        {
            del_node(root->_rchild);
            root->_rchild = 0;
        }
        return;
    } 
}
////////////////////////////////////////////////////////////////////////////
void main()
{
    cout<<"BBTree<int>\n";
    BBTree<int> t;
    t.add(5);
    t.add(7);
    t.add(6);
    t.add(9);
    t.add(8);
    t.add(4);
    t.add(3);
    t.add(2);
    t.add(1);
    t.add(1);
    t.add(1);
    t.remove(1);
    t.remove(1);
    t.pre_traversal();
    cout<<"mid\n";
    t.mid_traversal();
    cout<<"post\n";
    t.post_traversal();
    cout<<"BBT<string>\n";
    BBTree<string> st;
    st.add("ddddddd");
    st.add("bbbbbbb");
    st.add("fffffff");
    string s;
    s = "eeeeeee";
    st.add(s);
    st.pre_traversal();
}
 
 
 
 



Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1781895


[收藏到我的网摘]   [发送Trackback]  zhaomingliang发表于 2007年09月12日 11:39:33

相关文章：

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： SpringEmpire > 《我的图书馆》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多