二叉树基本操作

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

template<class DataType>
struct BiNode
{
    DataType data;
    struct BiNode *left,*right;
    BiNode():left(NULL),right(NULL){}
};

template<class DataType>
class BiTree
{
    public:
        BiTree() { root = Create();}
        BiTree(DataType a[],int n);
        ~BiTree() { Release(root);}
        void PreOrder() { _PreOrder(root); }
        void InOrder() { _InOrder(root); }
        void PostOrder() { _PostOrder(root); }
        void LevelOrder();
        void NRPreOrder();/*{ _NRPreOrder(root);}*/ //不递归的话就可以不用调用private定义的函数
        void NRInOrder() { _NRInOrder(root); }
        void NRPostOrder(){ _NRPostOrder(root); }
        BiNode<DataType> * search(DataType x) {  return _search(root,x); };
        int Count_leaf() { return _Count_Leaf(root); };
    private:
        BiNode<DataType> *root;
        BiNode<DataType> * Create();
        void Release(BiNode<DataType> *bt);
        void _PreOrder(BiNode<DataType> *bt);
        void _InOrder(BiNode<DataType> *bt);
        void _PostOrder(BiNode<DataType> *bt);
        //void _NRPreOrder(BiNode<DataType> *bt);
        void _NRInOrder(BiNode<DataType> *bt);
        void _NRPostOrder(BiNode<DataType> *bt);
        BiNode<DataType> *_search(BiNode<DataType> *bt, DataType x);
        int _Count_Leaf(BiNode<DataType> *bt);
};
//这种构造方式比较麻烦，就直接用后一种构造方式了
template<class DataType>
BiNode<DataType> * BiTree<DataType>::Create()
{
    BiNode<DataType> *bt = NULL;
    DataType ch;
    cout<<"Enter Data:"<<endl;
    cin >> ch;
    if(ch == -1)
        bt = NULL;
    else
    {
        bt = new BiNode<DataType>();
        bt->data = ch;
        bt->left = Create();
        bt->right = Create();
    }
    return bt;
}

template<class DataType>
BiTree<DataType>::BiTree(DataType a[],int len) : root(NULL)
{
    queue< BiNode<DataType> *>que;
    int i = 0;
    BiNode<DataType> *tmp_root,*tmp_left,*tmp_right;
    root = new BiNode<DataType>();
    root->data = a[0];
    que.push(root);
    while(!que.empty() && ++i < len)
    {
        tmp_root = que.front();
        que.pop();
        tmp_left = new BiNode<DataType>();
        tmp_left->data = a[i];
        tmp_root->left = tmp_left;
        que.push(tmp_left);
        i++;
        if(i >= len)
            break;
        tmp_right = new BiNode<DataType>();
        tmp_right->data = a[i];
        tmp_root->right = tmp_right;
        que.push(tmp_right);
    }

}


template<class DataType>
void BiTree<DataType>::Release(BiNode<DataType> *bt)
{
    if(bt != NULL)
    {
        Release(bt->left);
        Release(bt->right);
        delete bt;
    }
}

template<class DataType>
void BiTree<DataType>::_PreOrder(BiNode<DataType> *bt)
{
    if(bt != NULL)
    {
        cout<<bt->data<<'\t';
        _PreOrder(bt->left);
        _PreOrder(bt->right);
    }
}

template<class DataType>
void BiTree<DataType>::NRPreOrder(/*BiNode<DataType> *bt*/)
{
    stack<BiNode<DataType> * > tree_stack;
    BiNode<DataType> * p = NULL;
    //if(bt == NULL)
    if(this->root == NULL)
        return ;
    p = this->root;
    while(p != NULL || !tree_stack.empty())
    {
        while(p != NULL)
        {
            cout<<p->data<<'\t';
            tree_stack.push(p);
            p = p->left;
        }
        if( !tree_stack.empty())
        {
            p = tree_stack.top();
            p = p->right;
            tree_stack.pop();
        }
    }
}

template<class DataType>
void BiTree<DataType>::_InOrder(BiNode<DataType> *bt)
{
    if(bt != NULL)
    {
        _InOrder(bt->left);
        cout<<bt->data<<'\t';
        _InOrder(bt->right);
    }
}

template<class DataType>
void BiTree<DataType>::_NRInOrder(BiNode<DataType> *bt)
{
    stack<BiNode<DataType> *> tree_stack;
    BiNode<DataType> * p = NULL;
    if(bt == NULL)
        return ;
    p = bt;
    while(p != NULL || !tree_stack.empty())
    {
        while(p != NULL)
        {
            tree_stack.push(p);
            p = p->left;
        }
        if( !tree_stack.empty())
        {
            p = tree_stack.top();
            cout<< p->data <<'\t';
            p = p->right;
            tree_stack.pop();
        }
    }
}

template<class DataType>
void BiTree<DataType>::_PostOrder(BiNode<DataType> *bt)
{
    if(bt != NULL)
    {
        _PostOrder(bt->left);
        _PostOrder(bt->right);
        cout<<bt->data<<'\t';
    }
}

template<class DataType>
struct PNode
{
    BiNode<DataType> *ptr;
    int flag;
    PNode():ptr(NULL),flag(0){};
};

template<class DataType>
void BiTree<DataType>::_NRPostOrder(BiNode<DataType> *bt)
{
    stack<PNode<DataType> > tree_stack;
    BiNode<DataType> * p = NULL;
    PNode<DataType> pnode;
    if(bt == 0)
        return ;
    p = bt;
    while( p != NULL || !tree_stack.empty())
    {
        while(p != NULL)
        {
            pnode.ptr = p;
            pnode.flag = 1;
            tree_stack.push(pnode);
            p = p->left;
        }
        while( !tree_stack.empty() && tree_stack.top().flag == 2)//第二次访问的时候才访问
        {
            p = tree_stack.top().ptr;
            tree_stack.pop();
            cout<< p->data <<'\t';
        }
        if( !tree_stack.empty())
        {
            tree_stack.top().flag = 2;
            p = tree_stack.top().ptr->right;
        }
        else
            break;
    }
}

template<class DataType>
void BiTree<DataType>::LevelOrder()
{
    if(root == NULL)
        return ;
    queue<BiNode<DataType> *> que;
    que.push(root);
    while(!que.empty())
    {
        BiNode<DataType> *tmp = que.front();
        que.pop();
        cout<<tmp->data<<'\t';
        if(tmp->left != NULL)
            que.push(tmp->left);
        if(tmp->right != NULL)
            que.push(tmp->right);
    }
}

template<class DataType>
BiNode<DataType> * BiTree<DataType>::_search(BiNode<DataType> *bt , DataType x)
{
    if(bt == NULL)
        return NULL;
    BiNode<DataType> *p = bt;
    BiNode<DataType> *p1 = NULL;//注意 p1 的引入
    if(p != NULL)
    {
        if(p->data == x)
            return p;
        if(p->left != NULL)
        {
            p1 = _search(p->left,x);//返回值不能把p覆盖了，所以要使用p1来保存
            if(p1 != NULL)
                return p1;
        }
        if(p->right != NULL)
        {
            p1 = _search(p->right,x);
            if(p1 != NULL)
            return p1;
        }
    }
    return NULL;
}

template<class DataType>
int BiTree<DataType>::_Count_Leaf(BiNode<DataType> *bt)
{
    if(bt == NULL)
        return 0;
    BiNode<DataType> *p = bt;
    if(p->left == NULL && p->right == NULL)
        return 1;
    return (_Count_Leaf(p->left) + _Count_Leaf(p->right));
}

int main()
{
    int a[] = {1,2,3,4,5,6,7};
    BiTree<int> bt(a,sizeof(a)/sizeof(a[0]));
    /*
    cout<<"PreOrder: "<<endl;
    bt.NRPreOrder();
    cout<<endl;
    cout<<"InOrder: "<<endl;
    bt.NRInOrder();
    cout<<endl;
    cout<<"PostOrder: "<<endl;
    bt.NRPostOrder();
    cout<<endl;
    cout<<"LevelOrder"<<endl;
    bt.LevelOrder();
    cout<<endl;
    */
//----------------------------
    cout<<"PreOrder: "<<endl;
    bt.NRPreOrder();
    cout<<endl;

    cout<<"LevelOrder: "<<endl;
    bt.LevelOrder();
    cout<<endl;
    BiNode<int> *p = bt.search(5);
    if(p != NULL)
        cout<<p->data<<endl;
    else
        cout<<"can not find!"<<endl;
    cout<<"Leaf Number: "<<endl;
    cout<<bt.Count_leaf()<<endl;

    return 0;
}

这两天把常用的数据结构写了一下。