我的c++学习笔记（五）———二叉树的完整实现(1)

O、准备
首先简单描述一下二叉树的概念：
在二叉树中，每个节点可以有0个，1个或2个子节点，除了根节点以外，每个节点有且只有一个父节点，对于每个节点满足以下条件：
左子节点 < 自己 < 右子节点
由小于号的递推关系，可以有以下结论：
二叉树中的每一个节点都大于其左边子树上的任意节点，而小于其右边子树上的任意节点

下面详细描述一个采用c++模板实现的二叉树的设计
注：这里的二叉树设计仅仅是我学习《算法导论》做的一个练习而已，接口不考虑与STL的兼容，如果需要程序中需要用到二叉树，可以使用std::set

有一点很容易明白：二叉树与节点是一种“HAS-A”的关系(二叉树含有节点)，而不是“IS-A”的关系(二叉树是一种节点)，所以可以设计两个类：Node与BinTree，分别代表节点与二叉树，并且BinTree类中包含Node成员

一、对外接口
首先考虑二叉树将要提供的接口：
  1、size()
  2、min(), max()
  3、query(data) 查询树中是否存储有数据data, 返回bool
  4、successor(data)
     返回等于所有大于data的元素中的最小元素
     树中是否存在与data相等的操作对上述返回值无影响
  5、insert(data), remove(data) 添加或删除指定的元素
     删除元素时若该元素不存在则对树无影响
     插入元素时若已存在相等的元素则对树无影响
     两种操作均返回bool值
上述接口定义与《算法导论》上的描述并不完全一致，书上的所有操作都直接以节点的引用作为参数，为了向用户隐藏二叉树的内部实现（即用户不需要知道二叉树由节点构成，甚至都不需要了解其树状结构），我把这里的参数及返回值都改成了值(value)，而不是引用(reference)
为了使我们的二叉树独立于特定的类型，我采用了模板来实现，因此得到BinTree的对外接口部分如下：
template >
class BinTree{
public:        
    /* 定义空集异常类 */
    struct NoElem{};

    size_t    size()    const;
    inline    Data    min() const throw(NoElem);
    inline    Data    max() const throw(NoElem);
    bool    query(const Data& data ) const;
    Data    successor(const Data& data )const ;
    bool    insert(const Data& );
    bool    remove(const Data& );

    ...
};/* end class BinTree */
模板形参Data作为将要存储的数据类型，Compare为函数对象，定义作用在Data类型上的比较操作，默认为小于号
上面的设计目前还存在两个问题:
1、没有提供用户自定义的内存模型，这个主要是因为我目前基本没有内存模型的概念，以后再说吧
2、min()，max()抛出异常的声明很怪异，这里我主要考虑如果二叉树为空，该怎么表述查找结果的问题，直观起见，我不想给这两个函数添加参数，更不想返回一个结构体，所以就弄了这么个怪胎出来。
3、事实上，还可以定义prodecessor(前趋)函数，其定义与successor完全对称，我没有实现这个函数。

二、Node类的实现
根据BinTree的树状结构，可以设计Node类的定义如下：

/* forward declaration */
template<typename Data, typename Compare> class BinTree;

template<typename Data, typename Compare=std::less<Data> >
class Node{
    friend class BinTree<Data, Compare>;

    /*
     * member variables
     */
    /* 指针由BinTree直接控制 */
    Node<Data, Compare> * parent;
    Node<Data, Compare> * right;
    Node<Data, Compare> * left;
    Data data;
    Compare comp;

    Node(Data srcData=0, Compare srcComp=Compare() ):
        parent(0), right(0), left(0), data(srcData), comp(srcComp){};

};/* end class Node */

这里，Node类没有公有成员，他只能由模板参数相同的BinTree类构造并访问
注意这里的friend声明， 对于给定的Node类，我只希望BinTree 作为其友元， 而以其他模板实实例化出来的BinTree比如BinTree、BinTree，都不能成为Node的友元
为了实现这样的友元声明，需要有一个BinTree模板的前向声明，具体参见《c++ primer》第16章

在最初的设计中，我并没有将Compare列为模板形参，这样做有两个坏处:
1、 试想一下，如果没有Compare模板形参，对于Node类，我需要将BinTree声明为其友元，即只约束BinTree的一个模板形参，为了达到这个目的，我查阅了《C++ primer》(《TCPL》还没看到模板那块，水木上的网友推荐了一本《c++ template》，但是没看过的书拿来当手册总是不那么方便)，求助了google，愣是没找到答案，而添加Compare模板形参后好操作多了。
2、 如果第一条还不能算作一个坏处的话，这一条是真的要考虑了，在后续的BinTree设计中，不管是query()，还是successor()，以及 insert()，remove()等，都需要比较两个节点中的数据是否相等，如果把这些操作都交给BinTree，可读性似乎不那么好，在Node中检 验相等似乎更自然一点，为此，与上面的定义相比，我在Node的定义中添加了以下成员函数：

    bool operator==(const Node node){
        return !comp(data, node.data) && !comp(node.data, data);}
    bool operator==(const Data& otherData){
        return !comp(data,otherData) && !comp(otherData, data);}

第二个operator==()可能不是必须的，因为Node的默认构造函数似乎定义了Data到Node >的隐式类型转换(我没验证)，但为了消除潜在的二义性，我还是重载了这个操作符。
之所以将operator==定义为成员而不是《TCPL》上建议的友元，还是因为我觉得Node类的所有接口都只能被BinTree访问，如果定义为友元的话就可以被任意用户访问了，另外，友元的声明也是一个让人头疼的事。