二叉树类模板

 参考
主要参考如上地址写了一个类模板，删除节点的部分还是没弄清楚，参考中的删除部分的代码有问题。应该是删除指定节点的左子树或右子树。如果只删除单个节点的话，父指针（pra）不知道如何设置。

系统：ubuntu 9.04   gcc 4.3.3

/////////////binary.h////////////////
/////////////////////////////////////////////
#include
#include
using namespace std;

template
class node
{
public:
    node(const T &v ,node *L = NULL,node *R = NULL ,node *P = NULL): left(L),right(R),par(P)
    {
        value = v;
    }
public:
    T value;
    node *left,*right,*par;
};

template
class Binary
{
public:
    Binary(node *R = NULL):root(R)
    {}
    ~Binary()
    {
        if(root!=NULL)
        {
            delall();
        }
    }
public:
    node* findby(const T& v);
    void Insert(const T& v);
    node* findleave(node* cur);
    void delall();
    void Display(node * r);

public:
    void Inorder(const node* r);
    void Preorder(const node* r);
    void Postorder(const node* r);
    void Levelorder( node* r);
public:
    node* root;
};



template
node*  Binary :: findby(const T& v)
{
   
    deque*> Q;
    bool find = false;
    node *temp = NULL;
    if(root != NULL)
    {
        Q.push_back(root);
    }
    else
    {
        return NULL;
    }
    while(!Q.empty() && !find)
    {
        temp = Q.front();
        Q.pop_front();
        if(temp->value == v)
        {
            find = true;
        }
        else
        {
            if(temp->left != NULL)
                Q.push_back(temp->left);
            if(temp->right != NULL)
                Q.push_back(temp->right);
        }
    }
    if(!find)
        return NULL;
   
    return temp;
}


template
void Binary :: Insert(const T &v)
{
    deque *> Q;
    node* cur;
    if(root !=NULL)
    {
        Q.push_back(root);
    }
    else
    {
        root = new node(v , NULL , NULL , NULL);
        return;
    }
    while(!Q.empty())
    {
        cur = Q.front();
        Q.pop_front();
        if(cur->left != NULL)
            Q.push_back(cur->left);
        else
        {   
            cur->left = new node(v , NULL , NULL , cur);
            return;
        }
        if(cur->right != NULL)
            Q.push_back(cur->right);
        else
        {
            cur->right = new node(v, NULL, NULL , cur);
            return;
        }
    }
}

template
void Binary :: Display(node *r)
{
    if(r != NULL)
       {
            cout << r->value << ' ';
            Display(r->left);
            Display(r->right);
        }
}

template
void Binary :: delall()
{
    deque*> Q;
    node* temp;
    if(root)
        Q.push_back(root);
    while(!Q.empty())
    {
        temp=Q.front();
        Q.pop_front();
        if(temp->left !=NULL)
            Q.push_back(temp->left);
        if(temp->right != NULL)
            Q.push_back(temp->right);
        delete temp;
        temp = NULL;
    }
}

template
node* Binary :: findleave(node* cur)
{
   
    deque*> Q;
    node* temp = NULL;
    bool find = false;
    if(cur == NULL)
        return NULL;
    else       
        Q.push_back(cur);
    while(!Q.empty() && (!find))
    {
        temp = Q.front();
        Q.pop_front();
        if(temp->left == NULL && temp->right == NULL)
            find = true;
        if (temp->left != NULL)
            Q.push_back(temp->left);
        if (temp->right != NULL)
            Q.push_back(temp->right);       
    }
   
    if(!find)
        return NULL;
    return temp;   
}

template
void Binary :: Preorder(const node* r)
{
    if(NULL != r)
    {
        cout<value<<' ';
    }
    if(r->left != NULL)
    {
        Preorder(r->left);
    }
    if(r->right != NULL)
    {
        Preorder(r->right);
    }
}

template
void Binary :: Inorder(const node* r)
{
    if(r->left != NULL)
    {
        Inorder(r->left);
    }
    if(NULL != r)
    {
        cout<value<<' ';
    }
    if(r->right != NULL)
    {
        Inorder(r->right);
    }
}

template
void Binary :: Postorder(const node* r)
{
    if(r->left != NULL)
    {
        Postorder(r->left);
    }
   
    if(r->right != NULL)
    {
        Postorder(r->right);
    }
    if(NULL != r)
    {
        cout<value<<' ';
    }
}

template
void Binary :: Levelorder( node* r)
{
    deque*> Q;
    if(r != NULL)
    {
        Q.push_back(r);
    }
    while(!Q.empty())
    {
        node* temp = Q.front();   
        Q.pop_front();
        if(temp->left != NULL)
        {
            Q.push_back(temp->left);
        }

        if(temp->right != NULL)
        {
            Q.push_back(temp->right);
        }
        cout<value<<' ';
    }
}


////////////main.cc///////////
//////////////////////////////////////////
#include"binary.h"
int main(void)
{
    Binary BT;
    int a[]={1,2,3,4,5,6,7,8,9};

    for(int i=0 ; i < sizeof(a)/sizeof(a[0]) ; i++)
    {
        BT.Insert(a[i]);
    }
    BT.Display(BT.root);
    cout<<'\n'<<(BT.findby(6))->value<    cout<<(BT.findleave(BT.root))->value<    BT.Preorder(BT.root);
    cout<    BT.Inorder(BT.root);
    cout<    BT.Postorder(BT.root);
    cout<    BT.Levelorder(BT.root);
    return 0;
}

////////////////////Makefile//////////
//////////////////////////////////////
CC=g++
main:main.o

main.o:binary.h
    $(CC) -c main.cc
.PHONY:clean
clean:
    -rm -f main *.o

////////////////结果/////////
///////////////////////////////////
1 2 4 8 9 5 3 6 7
6
5
1 2 4 8 9 5 3 6 7
8 4 9 2 5 1 6 3 7
8 9 4 5 2 6 7 3 1
1 2 3 4 5 6 7 8 9
////////////////////////////////////////////////////////////////////////