数据结构(C++)——二叉树 BinTree

淡淡的烟草味﹌ 2022-05-18 11:15 152阅读 0赞

二叉树的实现

二叉树节点—BinNode模板类

#define BinNodePosi(T) BinNode<T>* //节点位置
    
    #define stature(p) ((p) ? (p).height: -1) //节点高度
    
    typedef enum { RB_RED, RB_BLACK } RBColor; //节点颜色
    
    template <typename T> struct BinNode {      //二叉树结点模板类 
    
        /*--成员变量--*/
    
        T data; //数值
    
        BinNodeposi(T) parent; //父节点
    
        BinNodeposi(T) lChild; //左孩子
    
        BinNodeposi(T) rChild; //右孩子
    
        int height; //高度
    
        int npl; //左式堆
    
        RBColor color; //颜色
    
        /*--构造函数--*/
    
        BinNode(): parent(NULL), lChild(NULL), rChild(NULL), height(0), npl(1), Color(RB_REB) {} //默认初始化
    
        BinNode(T e, BinNodeposi(T) p = NULL, BinNodeposi(T) lc = NULL, BinNodeposi(T) rc = NULL, int h = 0, int l = 1, RBColor c = RB_REB)
            : data(e), parent(p), lChild(lc), rChild(rc), height(h), npl(l), Color(c) {}
    
        /*--重要接口--*/
    
        int size(); //规模
    
        BinNodeposi(T) insertAsLC(T const &e); //插入左孩子
    
        BinNodeposi(T) insertAsRC(T const &e); //插入右孩子
    
        BinNodeposi(T) succ(T const &e); //直接后继
    
        template <typename VST> void tracLevel(VST&); //层次遍历
    
        template <typename VST> void travPre(VST&); //先序遍历
    
        template <typename VST> void tracIn(VST&); //中序遍历
    
        template <typename VST> void tracPost(VST&); //后序遍历
    
        /*--判断器、比较器--*/
    
        bool operator>(BinNode const& bn) { return data > bn.data; }
    
        bool operator<(BinNode const& bn) { return data < bn.data; }
    
        bool operator==(BinNode const& bn) { return data == bn.data; }
    
        bool operator>=(BinNode const& bn) { return data >= bn.data; }
    
        bool operator>=(BinNode const& bn) { return data >= bn.data; }
    
    };

![70][]

常用功能的快捷方式（宏实现）

#define IsRoot(x) (!((x).parent))
    
    #define IsLeaf(x) (!((x).lChild && (x).rChild))
    
    #define IsLChild(x) (!((x).parent) && ((x) == (x).parent.lChild))
    
    #define IsRChild(x) (!((x).parent) && ((x) == (x).parent.rChild))
    
    #define HasParent(x) ((x).parent)
    
    #define HasLChild(x) ((x).lChild)
    
    #define HasRChild(x) ((x).rChild)
    
    #define HasChild(x) (HasLChild(x) || HasRChild(x))                  //至少拥有一个孩子
    
    #define HasBothChild(x) (HasLChild(x) && HasRChild(x))              //同时拥有两个孩子
    
    #define sibling(p) (IsLChild(*(p)) ? (x).parent.rChild: (x).parent.lChild)          //兄弟
    
    #define uncle(p) (sibling((p).parent))                                              //叔叔
    
    #define FromParentTo(x)  ( IsRoot(x) ? _root : ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) )         //来自父亲的引用

二叉树节点操作接口

插入孩子节点：

template <typename T>
    BinNodePosi(T) BinNode::insertAsLC(T const &e)      //左孩子插入
    { return lChild = new BinNode(e, this); }
    
    template <typename T>
    BinNodePosi(T) BinNode::insertAsRC(T const &e)      //右孩子插入
    { return rChild = new BinNode(e, this); }

![70 1][](右节点插入完全对称)

在二叉树节点模板类的基础上，进一步定义二叉树模板类

BinTree模板类

#include "BinNode.h" //引用二叉树结点模板类
    
    template <typename T> class BinTree {
    pretected:
    
        int _size; //规模
    
        BinNodePosi(T) _root; //根节点
    
        virtual int updateHeight(BinNodePosi(T) x); //更新当前节点高度
    
        void updateHeightAbove(BinNodePosi(T) x); //更新所有祖先节点高度
    
    public:
    
        /*--构造与析构函数--*/
    
        BinTree(): _size(0), _root(NULL) {}
    
        ~BinTree() { if (_size > 0) remove(_root); }
    
        /*--常用接口--*/
    
        int size() const { return _size; } //规模
    
        bool empty() const { return !_root; } //判空
    
        BinNodePosi(T) root() const { return _root; } //取根
    
        BinNodePosi(T)  insertAsRoot(T const &e); //插入根节点
    
        BinNodePosi(T) insertAsLC(BinNodePosi(T) x, T const &e); //作为左孩子节点插入
    
        BinNodePosi(T) insertAsRC(BinNodePosi(T) x, T const &e); //作为右孩子节点插入
    
        BinNodePosi(T) attachaAsLC(BinNodePosi(T) x, BinTree <T>* &S); //作为左子树插入
    
        BinNodePosi(T) attachaAsRC(BinNodePosi(T) x, BinTree <T>* &S); //作为右子树插入
    
        int remove(BinNodePosi(T) x); //删除节点
    
        BinTree<T>* secede(BinNodePosi(T) x); //删除子树
    
        /*--遍历接口--*/
    
        template <typename VST> void travLevel(VST&visit) //层次遍历
        { if (_root) _root->travLevel(visit); }
    
        template <typename VST> void travPre(VST&visit) //先序遍历
        { if (_root) _root->travPre(visit); }
    
        template <typename VST> void travIn(VST&visit) //中序遍历
        { if (_root) _root->travIn(visit); }
    
        template <typename VST> void travPost(VST&visit) //后序遍历
        { if (_root) _root->travPost(visit); }
    
        /*--判断器、比较器--*/
    
        bool operator>(BinTree<T> const& t)
        { return _root && t._root && lt(_root, t._root); }
    
        bool operator<(BinTree<T> const& t)
        { return _root && t._root && lt(_root, t._root); }
    
        bool operator==(BinTree<T> const& t) 
        { return _root && t._root && (_root == t._root); }
    
        bool operator>=(BinTree<T> const& t) 
        { return _root && t._root && (_root >= t._root); }
    
        bool operator<=(BinTree<T> const& t) 
        { return _root && t._root && (_root <= t._root); }
    
    }

重要接口

1.高度更新

template <typename T> int BinTree::updateHeight(BinNodePosi(T) x)       //更新节点ｘ高度
    { return x->height = max(stature(x->lchild), stature(x->rchild)); }
    
    template <typename T> int BinTree::updateHeightAbove(BinNodePosi(T) x)       //更新v及祖先的高度
    { while (x) { updateHeight(x); x = x->parent; } }

2.节点插入

template <typename T> BinNodePosi(T) BinTree<T>::insertAsRoot(T const &e)
    { _size ++; return _root = new BinNode<T>(e); }                         //将ｅ当作根节点插入空的二叉树
    
    template <typename T> BinNodePosi(T) BinTree<T>::insertAsLC(BinNodePosi(T) x, T const &e)
    { _size ++; x->insertAsLC(e); updateHeightAbove(x); return x->lchild; }   //ｅ插入为ｘ的左孩子
    
    template <typename T> BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const &e)
    { _size ++; x->insertAsRC(e); updateHeightAbove(x); return x->rchild; }   //ｅ插入为ｘ的右孩子

![70 2][]

3.子树接入

template <typename T>
    BinNodePosi(T) attachaAsLC(BinNodePosi(T) x, BinTree <T>* &S) {
    
        if ( x->lchild = S->root ) x->lchild->parent = x;
    
        _size += S->_size; updateHeightAbove(x);
    
        S->root = NULL; S->size = 0; release(S); S = NULL;
    
        return x;
    
    }
    
    BinNodePosi(T) attachaAsRC(BinNodePosi(T) x, BinTree <T>* &S)
    
    {
    
        if ( x->rchild = S->root ) x->rchild->parent = x;
    
        _size += S->_size; updateHeightAbove(x);
    
        S->root = NULL; S->size = 0; release(S); S = NULL;
    
        return x;
    
    }

![70 3][]

4.子树删除

template <typename T>
    int BinTree<T>::remove(BinNodePosi(T) x) {
    
        IsLChild(x) ? x->parent->lChild = NULL: x->parent->rChild = NULL;
    
        updateHeightAbove(x.parent);
    
        int n = removeAt(x); return n;
    
    }
    
    template <typename T>
    int removeAt(BinNodePosi(T) x) {
    
        if (x) return 0;
    
        int n = 1 + removeAt(x->lChild) +  removeAt(x->rChild);
    
        release(x); 
    
        return n;
    
    }

5.子树分离

template <typename T>
    BinTree<T>* BinTree::secede(BinNodePosi(T) x) {
    
        IsLChild(x) ? x->parent->lChild = NULL: x->parent->rChild = NULL;
    
        updateHeightAbove(x->parent);
    
        BinTree<T>* S = new BinTree<T>
        S->root = x;
    
        x->parent = NULL;
    
        S->_size = x->_size;
    
        return S;
    
    }

[70]: /images/20220518/adcf4dddde544fcea1c2e7afdcf581a3.png
[70 1]: /images/20220518/4b4016ad85a0485fbdb6e725e028eff4.png
[70 2]: /images/20220518/3706bc27959f4b858946ff896f6e65fb.png
[70 3]: /images/20220518/54a073bdc0b44c249c61aa7b620bc22d.png