数据结构之二叉树

// mySTLBinaryTreeNote.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

template <typename T>
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree(){makeEmpty(root);}
    BinaryTree(const BinaryTree& rhs)
    {
        if (this == &rhs)    {    return *this;}
        else this->root = rhs.root;
        return this;
    }

    const BinaryTree& operator=(const BinaryTree& rhs)
    {
        if ( this != &rhs)
        {
            makeEmpty();
            root = clone(rhs.root);
        }
        return *this;
    }
    bool contains (const T& data){    return contains(data, root);}
    bool isEmpty() {return root == NULL;}
    void insert (const T& data)    {    return insert(data, root);}
    void remove(const T& data)    {    return remove(data, root);}

    const T& findMax() const
    {
        BinaryNode* t = findMax(root);
        return t->data;
    }
    const T& findMin() const
    {
        BinaryNode* t = findMin(root);
        return t->data;
    }

    void printTree(ofstream& out = cout) const
    {
        if ( isEmpty())
        {
            out <<"Empty Tree"<<end;
        }
        else
            printTree(out, root);
    }
private:
    struct BinaryNode
    {
        T data;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode(const T& data, BinaryNode* lt, BinaryNode* rt):data(data), left(lt), right(rt){}
    };

    BinaryNode* root;

    BinaryNode* finMax(BinaryNode* t) const //递归实现
    {
        if ( t == NULL){return NULL;}
        else if ( t->right){return t;}
        findMax(t->right);
    }
    BinaryNode* findMin(BinaryNode* t) const // 非递归实现
    {
        if (t != NULL)
            while(t->left != NULL) t= t->left;
        return t;
    }

    bool contains(const T& data, BinaryNode* t ) const
    {
        if (t == NULL){return false;}
        else if (data > t->data){return contains(data, t->right);}
        else if (data < t->data){return contains( data, t->left );}
        return false;
    }
    void insert(const T& data, BinaryNode* t)
    {
        if (t == NULL) {t == new BinaryTree(data, NULL, NULL);}
        else if (data > t ->data){ insert(data, t->right);}
        else if (data < t ->data ){ insert(data, t->left); }
        else;
    }
    void remove(const T& data, BinaryNode* t)
    {
        if ( t == NULL){ return; }
        else if ( data > t->data){remove(data, t->right);}
        else if (data < t->data) {remove(data, t->left);}
        else if (t->left != NULL && t->right != NULL)
        {
            t->data = findMin(t->right)->data;
            remove(t->data, t->right);
        }
        else // 也可以选用懒惰删除法，用计数记录，而不是真正的删除
        {
            BinaryNode* oldNode = t;
            t = (t->left !=NULL )? t->left : t->right;
            delete oldNode;
        }
    }
    void makeEmpty(BinaryNode * &t) //删除原指针，否则只是删除t的副本，虽然t的空间被删除，但t会成为野指针
    {
        if (t != NULL)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = NULL;
    }
    BinaryNode* clone(BinaryNode* t)
    {
        if (t == NULL){return t;}
        return new BinaryNode(t->data, clone(t->left), clone(t->right));
    }
    void printTree(ofstream& out /* = cout */, BinaryNode t)
    {
        if (t != NULL) //中序遍历
        {
            printTree(out, t->left);
            out << t->data <<endl;
            printTree(out, t->right);
        }
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}