5.2 二叉树

节点度数不超过2的树，称作二叉树(binary tree)
同一节点的子节点与子树，均以左右区分，即lChild()、lSubtree()、rChild()、rSubtree()，隐含有序
深度为k的节点，至多2^k个
含n个节点、高度为h的二叉树中，h < n < 2^h+1
当n = h + 1时，退化为一条单链
当n = 2^h+1 - 1时，即满二叉树(full binary tree)
二叉树是多叉树的特例，但在有根且有序时，其描述能力足以覆盖后者
多叉树均可转化并表示为二叉树，左子树（节点）为firstChild()，右子树（节点）为nextSibling()

BinNode模板类

#define BinNodePosi(T) BinNode<T>* // 节点位置
template <typename T> struct BinNode {
    BinNodePosi(T) parent, lChild, rChild; // 父节点、子节点
    T data; int height; int size(); // 高度、子树规模
    BinNodePosi(T) insertAsLC(T const &); // 作为左子节点插入
    BinNodePosi(T) insertAsRC(T const &); // 作为右子节点插入
    BinNodePosi(T) succ(); // （中序遍历）当前节点直接后继
    template <typename VST> void travLevel(VST &); // 子树层次遍历
    template <typename VST> void travPre(VST &); // 子树先序遍历
    template <typename VST> void travIn(VST &); // 子树中序遍历
    template <typename VST> void travPost(VST &); // 子树后序遍历
}

BinNode接口实现

template <typename T> BinNodePosi(T) BinNode<T>::insertAsLC(T const & e) {
    return lChild = new BinNode(e, this);
}

template <typename T> BinNodePosi(T) BinNode<T>::insertAsRC(T const & e) {
    return rChild = new BinNode(e, this);
}

template <typename T> int BinNode<T>::size() { // 后代总数，亦即以其为根的子树的规模
    int s = 1; // 计入自身
    if (lChild) s += lChild -> size(); // 递归计入左子树规模
    if (rChild) s += rChild -> size(); // 递归计入右子树规模
    return s;
}

BinTree模板类

template <typename T> class BinTree {
protected:
    int _size; // 规模
    BinNodePosi(T) _root; // 根节点
    virtual int updateHeight(BinNodePosi(T) x); // 更新节点x高度
    void updateHeightAbove(BinNodePosi(T) x); // 更新全树节点高度
public:
    int size() const {
        return _size;
    } // 规模
    bool empty() const {
        return !_root;
    } // 判空
    BinNodePosi(T) root() const {
        return _root;
    } // 根节点
    /* ... 子树接入、删除、分离接口 ... */
    /* ... 遍历接口 ... */
}

高度更新

#define stature(p) ((p) ? (p) -> height : -1) // 节点高度，约定空树高度为-1

template <typename T> int BinTree<T>::updateHeight(BinNodePosi(T) x) {
    return x -> height = 1 + max(stature(x -> lChild), stature(x -> rChild));
} // 采用常规二叉树规则

template <typename T> void BinTree<T>::updateHeightAbove(BinNodePosi(T) x) {
    while (x) { // 可优化，若高度未变即可终止
        updateHeight(X);
        x = x -> parent;
    }
}

节点插入

template <typename T> BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const & e) { // insertAsLC()对称
    _size++;
    x -> insertAsRC(e);
    updateHeightAbove(x);
    return x -> rChild;
}