相对于栈和链表等数据结构来说，树有着更复杂的结构。正如我们平常生活中看到的树一样，它有很多分支，而且分支上面还会有分支。

树的用途十分广泛，最常见的树是二叉树，衍生了很多类型的树，红黑树，搜索树等等，被用来查找效率十分高，一个最典型的应用就是mysql中的索引。

树是由很多个节点构成，要实现一个树最最主要的就是实现树的节点。

一、二叉树节点实现

1.1 二叉树节点的定义

template <typename T>
class CBinNode
{
private:
    T data;
    CBinNode *parent, *lChild, *rChild;
public:
    CBinNode() : parent(0), lChild(0), rChild(0), data(0) {};
    CBinNode(const T data, CBinNode<T> *parent = 0, CBinNode<T> *lc = 0, CBinNode<T> *rc = 0)
        : data(data), parent(parent), lChild(lc), rChild(rc) {};
    ~CBinNode();

    T getData() const { return data; }
    CBinNode<T>* getParent() const { return parent; }
    CBinNode<T>* getLChild() const { return lChild; }
    CBinNode<T>* getRChild() const { return rChild; }

    void setLChild(CBinNode<T>* node);
    void setRChild(CBinNode<T>* node);

    // 作为左节点插入
    CBinNode<T>* insertAsLChild(const T&);
    // 作为右节点插入
    CBinNode<T>* insertAsRChild(const T&);

    // 总结点数
    int size() const;
    // 树的深度
    int height() const;
    // 叶子节点数
    int leaf() const;

    // 是否为根节点
    bool isRoot() const;
    // 是否为叶子节点
    bool isLeaf() const;
    // 是否为左子节点
    bool isLChild() const;
    // 是否为右子节点
    bool isRChild() const;
    // 是否有左子节点
    bool hasLChild() const;
    // 是否有右子节点
    bool hasRChild() const;
    // 是否有子节点
    bool hasChild() const;
    // 是否有两个子节点
    bool hasTwoChild() const;
};

1.2 二叉树节点的实现

1.2.1 析构函数

对于一个即将被删除的节点，除了删除本身之外，应该把子节点也删掉。

template<typename T>
CBinNode<T>::~CBinNode()
{
    // 移除左节点及其下属节点
    if (lChild) {
        delete lChild;
        //delete tmp;
    }

    // 移除右节点极其下属节点
    if (this->hasRChild()) {
        CBinNode<T> * tmp = rChild;
        delete tmp;
    }

    lChild = 0;
    rChild = 0;
    parent = 0;
}

1.2.2 获取节点信息

// 求当前结点的度
template<typename T>
int CBinNode<T>::size() const {
    return this == 0 ? 0 : 1 + lChild->size() + rChild->size();
}

// 求高度
template<typename T>
inline int CBinNode<T>::height() const {
    if (!this) return 0;
    int lLen = 0, rLen = 0;
    // 高度取左右节点中更大的一个即可
    if (lChild) lLen = 1 + lChild->height();
    if (rChild) rLen = 1 + rChild->height();
    return lLen > rLen ? lLen : rLen;
}

// 求叶子节点数
template<typename T>
inline int CBinNode<T>::leaf() const {
    if (!this) return 0;
    // 只有没有左右子节点才算叶子结点
    if (!lChild && !rChild) return 1;
    return lChild->leaf() + rChild->leaf();
}

1.2.3 插入操作

template<typename T>
CBinNode<T>* CBinNode<T>::insertAsLChild(const T& x) {
    if (!this) return 0;
    // 删除所有的左节点
    if (lChild) delete lChild;
    return lChild = new CBinNode(x, this);
}

template<typename T>
CBinNode<T>* CBinNode<T>::insertAsRChild(const T& x)
{
    if (!this) return 0;
    // 删除所有的右节点
    if (rChild) delete rChild;
    return rChild = new CBinNode(x, this);
}

template <typename T>
void CBinNode<T>::setLChild(CBinNode<T> *node) {
    if (!this) return 0;
    if (lChild) delete lChild;
    lChild = node;
}

template <typename T>
void CBinNode<T>::setRChild(CBinNode<T> *node) {
    if (!this) return 0;
    if (rChild) delete rChild;
    rChild = node;
}

1.2.4 其他属性操作

template<typename T>
bool CBinNode<T>::isRoot() const {
    return parent == 0;
}

template<typename T>
bool CBinNode<T>::isLeaf() const {
    return (lChild == 0 && rChild == 0);
}

template<typename T>
bool CBinNode<T>::isLChild() const {

    return parent == 0 ? false : this == parent->getLChild();
}

template<typename T>
bool CBinNode<T>::isRChild() const {
    return parent == 0 ? false : this == parent->getRChild();
}

template<typename T>
bool CBinNode<T>::hasLChild() const {
    return lChild != 0;
}

template<typename T>
bool CBinNode<T>::hasRChild() const {
    return rChild != 0;
}

template<typename T>
bool CBinNode<T>::hasChild() const {
    return (lChild || rChild);
}

template<typename T>
bool CBinNode<T>::hasTwoChild() const {
    return (lChild && rChild);
}

二、树的实现

树的结构非常简单，包含一个节点作为根就行，其他的节点大多都都间接调用节点接口。

#include"BinNode.h"
using namespace std;

template <typename T>
class CTree {
public:
    CTree();
    ~CTree();
    CTree(T data);
    CTree(CBinNode<T> *root);

    int size() const;
    int height() const;
    int leaf() const;
    // 作为根节点插入
    CBinNode<T>* insertAtRoot(T data);
    // 作为左节点插入
    CBinNode<T>* insertNodeAtLeft(CBinNode<T>*node, T data);
    // 作为右节点插入
    CBinNode<T>* insertNodeAtRight(CBinNode<T>*node, T data);
    // 移除节点
    CBinNode<T>* removeNode(CBinNode<T>* node);
private:
    CBinNode<T> *root;
};

template<typename T>
inline CTree<T>::CTree() :root(0) {
}

template<typename T>
inline CTree<T>::~CTree() {
    if (!root) return;
    delete root;
}

template<typename T>
inline CTree<T>::CTree(T data) {
    root = new CBinNode<T>(data);
}

template<typename T>
CTree<T>::CTree(CBinNode<T> *root) : root(root) {
}

template<typename T>
CBinNode<T>* CTree<T>::insertAtRoot(T data) {
    if (root) return;
    root = new CBinNode<T>(data);
}

template<typename T>
CBinNode<T>* CTree<T>::insertNodeAtLeft(CBinNode<T>* node, T data) {
    if (!node || !root) return 0;
    node->insertAsLChild(data);
}

template<typename T>
CBinNode<T>* CTree<T>::insertNodeAtRight(CBinNode<T>* node, T data) {
    if (!node || !root) return 0;
    node->insertAsLChild(data);
}

template<typename T>
inline int CTree<T>::size() const
{
    return !root ? 0 : root->size();
}

template<typename T>
inline int CTree<T>::height() const {
    return root->height();
}

template<typename T>
inline int CTree<T>::leaf() const {
    return root->leaf();
}

template<typename T>
inline CBinNode<T>* CTree<T>::removeNode(CBinNode<T>* node)
{
    if (!node) return 0;
    if (root != node && node->getParent()) {
        CBinNode<T>* p = node->getParent();
        if (node == p->getLChild()) p->setLChild(0);
        if (node == p->getRChild()) p->setRChild(0);
    }
    delete node;
}