二叉树的一些基本操作

1，这段时间看书有点多了,以前熟悉的东西反而淡忘了.
是总结下基础的时候了.
2，实例代码:

#include <iostream>
#include <stack>
#include <queue>
#include <stdexcept>
using namespace std;

template <class T>
struct BSTNode
{
    BSTNode();
    BSTNode(const T& val,BSTNode<T>* l=NULL,BSTNode<T>* r=NULL);  //成员函数只是两个构造函数
    T  key;
    BSTNode<T>* left;
    BSTNode<T>* right;

};

template <class T>
BSTNode<T>::BSTNode(const T& val,BSTNode<T>* l,BSTNode<T>* r)
:key(val),left(l),right(r)
{}

template <class T>
BSTNode<T>::BSTNode():left(NULL),right(NULL)
{}



template <class Type>
class BSTree
{
public:
    BSTree();
    ~BSTree()
    {
        destroy(root);
    }

    bool isempty()
    {
        return root==NULL;
    }
    void visit(BSTNode<Type>* p);
    void insert(Type p); //在二叉树中插入一个节点
    int height() //返回高度
    {
        return height(root);
    }
    int nodecount()
    {
        return nodecount(root);
    }
    int leafcount()
    {
        return leafcount(root);
    }
    void inorder()
    {
        inorder(root);
    }
    void preorder()
    {
        preorder(root);
    }
    void postorder()
    {
        postorder(root);
    }
    void levelorder()
    {
        levelorder(root);
    }
    BSTNode<Type>* copytree(BSTNode<Type>* p);
    BSTree& operator=(const BSTree& tr);
private:
    int height(BSTNode<Type>* p);
    int nodecount(BSTNode<Type>* p);
    int leafcount(BSTNode<Type>* p);
    void destroy(BSTNode<Type>* p);
    void preorder(BSTNode<Type>* p);
    void inorder(BSTNode<Type>* p);
    void postorder(BSTNode<Type>* p);
    void levelorder(BSTNode<Type>* p);
private:
    BSTNode<Type> * root;
};

template <class Type>
BSTree<Type>::BSTree():root(NULL)
{} //初始化NULL非常的重要,便于以后对每个节点判断是否为0

template <class Type>
void BSTree<Type>::insert(Type p)
{
    if(root==NULL)
        root=new BSTNode<Type>(p);  //注意,节点的每一个指针都保证是用new动态分配资源
    else
    {
        BSTNode<Type>* pre;
        BSTNode<Type>* tmp=root;
        while(tmp!=NULL)
        {
            pre=tmp;
            if(tmp->key==p)
            {
                return;//假设只能插入不同的节点
            }
            else if(p<tmp->key)
            {
                tmp=tmp->left;
            }
            else
            {
                tmp=tmp->right;
            }
        }
        if(p<pre->key)
            pre->left=new BSTNode<Type>(p);
        else if(p>pre->key)
            pre->right=new BSTNode<Type>(p);
    }

}

template <class Type>
int BSTree<Type>::height(BSTNode<Type>* p)
{
    if(p==NULL)
        return 0;
    else
        return 1+( height(p->left)>height(p->right)? height(p->left):height(p->right) );
}

template <class Type>
int BSTree<Type>::nodecount(BSTNode<Type>* p)
{
    if(p==NULL)
        return 0;
    else
        return 1+nodecount(p->left)+nodecount(p->right);
}

template <class Type>
int BSTree<Type>::leafcount(BSTNode<Type>* p)  //就编了这么一个出来
{
    if(p==NULL)
        return 0;
    else  if(p->left==NULL&&p->right==NULL)
        return 1;
    else
        return leafcount(p->left)+leafcount(p->right);
}

template <class Type>
void BSTree<Type>::destroy(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        destroy(p->left);
        destroy(p->right);
        delete p;
        p=NULL;
    }
}

template <class Type>
void BSTree<Type>::visit(BSTNode<Type>* p)
{
    cout<<p->key<<" ";
}

template <class Type>
void BSTree<Type>::inorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        inorder(p->left);
        visit(p);
        inorder(p->right);
    }
}

template <class Type>
void BSTree<Type>::preorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        visit(p);
        preorder(p->left);
        preorder(p->right);
    }
}
template <class Type>
void BSTree<Type>::postorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        visit(p);
    }
}

template <class Type>
void BSTree<Type>::levelorder(BSTNode<Type>* p)
{
    if(p==NULL)
        return;
    queue< BSTNode<Type>* > que;
    que.push(p);
    BSTNode<Type>* tmp;
    while(!que.empty())
    {
        tmp=que.front();
        visit(tmp);
        que.pop();
        if(tmp->left!=NULL)
            que.push(tmp->left);
        if(tmp->right!=NULL)
            que.push(tmp->right);
    }
}

template <class Type>
BSTNode<Type>* BSTree<Type>::copytree(BSTNode<Type>* p)
{
    if(p==NULL)
        return NULL;
    BSTNode<Type>* l=copytree(p->left);
    BSTNode<Type>* r=copytree(p->right);
    BSTNode<Type>* tree=new BSTNode<Type>(p->key,l,r);
    return tree;
}

template <class Type>
BSTree<Type>& BSTree<Type>::operator=(const BSTree& tr)
{
    if(this!=&tr)
    {
        destroy(); //释放当前的
        copytree(tr.root);
        return *this;
    }

}

int main()
{
    BSTree<char> bstchar;
    cout<<bstchar.isempty()<<endl;
    cout<<"叶子个数:"<<bstchar.leafcount()<<endl;

    BSTree<int> bstlist;
    for(int i=0;i!=15;i++)
        bstlist.insert(i); //实际上是一个但链表,
    cout<<"bstlist的高度:"<<bstlist.height()<<endl;
    cout<<"叶子个数:"<<bstlist.leafcount()<<endl;

    int val[]={5,3,7,1,4,6,8,9};
    BSTree<int> bstarray;
    for(int i=0;i<sizeof(val)/sizeof(val[0]);i++)
        bstarray.insert(val[i]); //实际上是一个但链表,

    cout<<"bstarray的高度:"<<bstarray.height()<<endl;
    cout<<"递归中序遍历的结果:";
    bstarray.inorder();
    cout<<endl;
    cout<<"递归先序遍历的结果:";
    bstarray.preorder();
    cout<<endl;
    cout<<"递归后序遍历的结果:";
    bstarray.postorder();
    cout<<endl;
    cout<<"水平遍历的结果:";
    bstarray.levelorder();
    cout<<endl;
    cout<<"节点个数:"<<bstarray.nodecount()<<endl;
    cout<<"叶子个数:"<<bstarray.leafcount()<<endl;
    return 0;
}