类的声明及其相关结构的定义：
所有成员函数都通过测试了，大家只要通过CreateBinaryTree()函数用广义表字符串创建广义表后，就可以调用我写的任何一个成员函数了，可能还有其他更多的关于二叉树的算法，正在补充中，大家参考，共同学习共同交流。
呵呵，这也是我写的最长的抽象数据类型的实现了。
#ifndef BINARYTREE_H
#define BINARYTREE_H

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include"LinkedStack.h"
#include"LinkedQueue.h"
#include<string.h>

//////////////////////////////////////////////////
//二叉树结点类模板的定义
//////////////////////////////////////////////////
template<class T>
struct BinTreeNode
{
    T data;                     //数据域
    BinTreeNode<T>* leftChild;  //左子结点地址
    BinTreeNode<T>* rightChild; //右子结点地址

    BinTreeNode()               //构造函数
    {
        leftChild=NULL;
        rightChild=NULL;
    };
    BinTreeNode(T x,BinTreeNode<T>* l=NULL
        ,BinTreeNode<T>* r=NULL)               
    {                           //带参数的构造函数
        data=x;
        leftChild=l;
        rightChild=r;
    };
};
////////////////////////////////结点类模板定义结束

//////////////////////////////////////////////////
//stkNode结构
//后序非递归遍历中堆栈结点结构的定义
//////////////////////////////////////////////////
template<class T>
struct stkNode
{
    //指向树结点的指针
    BinTreeNode<T>* ptr;
    //该结点所处的左右子树的标志0:左1:右
    int tag;
    //构造函数
    stkNode(BinTreeNode<T>* N=NULL)
        :ptr(NULL),tag(1){};
};
///////////////////////////////stkNode结构定义结束

//////////////////////////////////////////////////
//二叉树类模板BinaryTree的声明和定义
//用二叉链表实现二叉树的抽象数据类型
//////////////////////////////////////////////////
template<class T>
class BinaryTree
{
public:
    //空构造函数
    BinaryTree():root(NULL){};
    //带参数的构造函数
    BinaryTree(T value):RefValue(value),root(NULL){};
    //以描述字符串为参数的构造函数
    BinaryTree(char* s,T value);
    //复制构造函数
    BinaryTree(BinaryTree<T>& bt);
    //析构函数
    ~BinaryTree()
    {Destroy(root);
    cout<<endl<<"二叉树内存空间释放完毕!"<<endl;};
    //判断二叉树是否为空
    bool IsEmpty(){return root==NULL;};
    //得到当前结点的根结点
    BinTreeNode<T>* getRoot()
    {return root;};
    //得到当前current结点的父结点
    BinTreeNode<T>* Parent(BinTreeNode<T>* current)
    {return (root==NULL||root==current)?
          NULL:Parent(root,current);};
    //返回当前结点的左子结点的指针
    BinTreeNode<T>* LeftChild(BinTreeNode<T>* current)
    {return (current->leftChild==NULL)?
            NULL:current->leftChild;};
    //返回当前结点的右子结点的指针
    BinTreeNode<T>* rightChild(BinTreeNode<T>* current)
    {return (current->rightChild==NULL)?
            NULL:current->rightChild;};
    //返回当前树的高度
    int Height()
    {return Height(root);};
    //返回当前树的总结点数
    int Size()
    {return Size(root);};
    //得到当前二叉树的树根
    BinTreeNode<T>* getRoot()const{return root;};
    //前序遍历当前二叉树
    void preOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"前序遍历:";preOrder(root,visit);};
    //前序遍历的非递归算法1
    void preOd1();
    //前序遍历的非递归算法2
    void preOd2();
    //前序遍历的非递归算法3
    void preOd3();
    //中序遍历当前二叉树
    void inOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"中序遍历:";inOrder(root,visit);};
    //中序非递归遍历的算法
    void inOd1(void(*visit)(BinTreeNode<T>* p));
    //后序遍历当前二叉树
    void postOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"后序遍历:";postOrder(root,visit);};
    //后序非递归遍历二叉树的算法实现
    void postOd(void(*visit)(BinTreeNode<T>* p));
    //按层次顺遍历当前二叉树
    void levelOrder(void(*visit)(BinTreeNode<T>* p));
    //在二叉树中item元素下，插入新元素item2
    bool Insert(const T item1,const T item2,char c);
    //在当前的二叉树中搜索值为T的结点,返回该结点的指针
    BinTreeNode<T>* Find(T item)const;
    //显示二叉树的广义表形式
    void PrintBinaryTree()
    {PrintBinaryTree(root);};
    //判断指定的结点在当前二叉树中是否存在
    bool Exist(const T& x)
    {return Exist(root,x);};
    //利用前序遍历递归创建一棵二叉树
    void CreateBinaryTree(istream& in)
    {CreateBinaryTree(in,root);};
    //通过二叉树的前序序列和中序序列建立一棵二叉树
    void CreateByprein(T* pre,T* in,int n);
    //统计二叉树中所有结点的个数
    int CountNode(){return CountNode(root);};
    //交换每个结点的左右子树
    void ChangeChild();
    //通过数组w[]中的数据元素建立一棵完全二叉树
    void CreateComBinTree(T* w,int n);
    //在当前的二叉树中寻找值为elem的结点的指针,并显示所有的父结点
    BinTreeNode<T>* FindAncestor(T elem)
    {return FindAncestor(root,elem);};
    //统计子当前二叉树中度为1的结点的个数
    int oneDegree()
    {return oneDegree(root);};
    //统计子当前二叉树中度为1的结点的个数
    int towDegree()
    {return twoDegree(root);};
    //统计子当前二叉树中度为0的结点的个数
    int zeroDegree()
    {return zeroDegree(root);};
    //计算指定结点p在当前二叉树中的深度
    int Depth(BinTreeNode<T>* p)
    {return Depth(p,root);};
    //计算当前二叉树的宽度
    int Width();
    //删除当前二叉树所有的叶子结点
    void deleteLeaf()
    {deleteLeaf(root);};
    //展出当前二叉树中的最大值
    T maxVal()
    {return maxVal(root);};
    //以前序方式显示当前二叉树中所有结点所在的层次
    void preDepth()
    {preDepth(root);};
    //双序遍历一棵二叉树
    void DoubleOrder()
    {DoubleOrder(root);};
    //前序显示二叉树每个结点及其深度
    void PrintDepth()
    {PrintDepth(root,1);};
    void SearchpreOrder(int k)
    {cout<<SearchpreOrder(k,root)->data;};
    //判断一棵二叉树是否是完全二叉树
    bool IsCompleteBinTree();
    //递归:求子二叉树subTree的宽度
    void FindWidth(BinTreeNode<T>* subTree
        ,int* count,int i);
    //求当前二叉树的宽度
    int FindWidth();
    //递归:求解指定结点的子孙的个数
    int NumOfSons(BinTreeNode<T>* p);
    //调用上面的函数
    int NumOfSons()
    {return NumOfSons(root);};
    //递归:通过前序遍历来统计二叉树中结点总个数
    int PreOrderCount(BinTreeNode<T>* subTree);
    //调用上面的函数
    int PreOrderCount()
    {return PreOrderCount(root);};
    //递归:通过前序序列来创建一棵二叉树
    int PreOrderCreate(char* s,
        int start,BinTreeNode<T>*& subTree);
    void PreOrderCreate(char* s)
    {PreOrderCreate(s,0,root);};
protected:
    //二叉树的根结点指针
    BinTreeNode<T>* root;
    //数据输入停止的标志
    T RefValue;
    
    //读入描述字符串建立二叉树
    void CreateBinTree(char* BinStr
        ,BinTreeNode<T>*& subTree);
    //用输描述字符串s递归创建一个二叉树
    void CreateBinaryTree(istream& in
        ,BinTreeNode<T>*& subTree);
    //删除子树操作
    void Destroy(BinTreeNode<T>*& subTree);
    //在指定的子树中查找元素x是否存在
    bool Exist(BinTreeNode<T>* subTree,const T& x);
    //复制操作
    BinTreeNode<T>* Copy(BinTreeNode<T>* orignode);
    //返回树subTree的高度
    int Height(BinTreeNode<T>* subTree);
    //返回树的总结点数
    int Size(BinTreeNode<T>* subTree);
    //返回树subTree中,current结点的父结点
    BinTreeNode<T>* Parent(BinTreeNode<T>* subTree
        ,BinTreeNode<T>* current);
    //在子树subTree中搜索值为x的结点的指针
    BinTreeNode<T>* Find(BinTreeNode<T>* subTree
        ,const T& x)const;    
    //搜索并前序遍历输出
    void Traverse(BinTreeNode<T>* subTree
        ,ostream& out);
    //前序遍历
    void preOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //中序遍历
    void inOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //后序遍历
    void postOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //显示二叉树的广义表形式
    void PrintBinaryTree(BinTreeNode<T>* subTree);
    //通过前序序列和中序序列建立一棵二叉树
    BinTreeNode<T>* CreateByprein1(T* pre,T* in,int n);
    //统计二叉树subTree子树中所有结点的个数
    int CountNode(BinTreeNode<T>* subTree);
    //把所有的结点读入到一个数组中
    void GetNode(BinTreeNode<T>**);
    //找具有指定值Elem的结点的指针,并显示其所有祖先结点
    BinTreeNode<T>* FindAncestor(
        BinTreeNode<T>* subTree,T elem);
    //递归统计子树subTree中度为1的结点的个数
    int oneDegree(BinTreeNode<T>* subTree);
    //递归统计子树subTree中度为2的结点的个数
    int twoDegree(BinTreeNode<T>* subTree);
    //递归统计子树subTree中度为0的结点的个数
    int zeroDegree(BinTreeNode<T>* subTree);
    //计算指定结点p在子树subTree中的深度
    int Depth(BinTreeNode<T>* p
        ,BinTreeNode<T>* subTree);
    //递归删除子树subTree里叶子结点
    void deleteLeaf(BinTreeNode<T>* subTree);
    //递归找出子树subTree中数据最大值
    T maxVal(BinTreeNode<T>* subTree);
    //以前序的序列显示每个结点所在的层次
    void preDepth(BinTreeNode<T>* subTree);
    //双序遍历一棵二叉树
    void DoubleOrder(BinTreeNode<T>* subTree);
    //以前序方式显示每个结点及其深度
    void PrintDepth(BinTreeNode<T>* subTree
        ,int depth);
    //递归:得到中序序列中第k个结点的指针
    BinTreeNode<T>* SearchpreOrder(int k
        ,BinTreeNode<T>* subTree);
    //递归:给定前序序列,创建所有可能的二叉树
    void CtreateBypre(char* s,int begin,int end);
    //递归:通过带#的前序序列来创建一棵二叉树
   
    //友元重载>>输入运算符输入二叉树
    friend istream& operator>>(istream& in
        ,BinaryTree<T>& Tree);
    //友元重载<<输出运算符输出二叉树
    friend ostream& operator<<(ostream& out
        ,BinaryTree<T>& Tree);
    //友元函数,判断两棵二叉树是否相等
    friend bool Equal(BinTreeNode<T>* a
        ,BinTreeNode<T>* b);
    //友元函数,判断两棵二叉树是否相等
    friend bool BinTreeEqual(BinaryTree<T>& BT1
        ,BinaryTree<T>& BT2);
    //友元重载==运算符
    friend bool operator==(BinaryTree<T>& BT1
        ,BinaryTree<T>& BT2);
};
////////////////////////////////BinaryTree声明结束

[[it] 本帖最后由 geninsf009 于 2008-12-4 22:18 编辑 [/it]]

构造函数：
//////////////////////////////////////////////////
//以描述字符串为参数的构造函数
//////////////////////////////////////////////////
template<class T>
BinaryTree<T>::BinaryTree(char* s,T value)
{
    //通过描述字符串创建一棵二叉树,
    //把根结点放入root
    CreateBinTree(s,root);
    RefValue=value;
};
//////////////////////////////////////构造函数结束

//////////////////////////////////////////////////
//复制构造函数
//通过已经存在的二叉树bt构造新二叉树
//////////////////////////////////////////////////
template<class T>
BinaryTree<T>::BinaryTree(BinaryTree<T>& bt)
{
    //复制二叉树root
    root=bt.Copy(bt.root);
    //结束符的复制
    RefValue=bt.RefValue;
};
//////////////////////////////////复制构造函数结束

前序遍历就写了好几种：
//////////////////////////////////////////////////
//preOd1()公又成员函数
//前序遍历的非递归算法的实现
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd1()
{
    //遍历过程中回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //把空指针放入堆栈底部
    LS.Push(NULL);
    //结点指针
    BinTreeNode<T>* p=root;
    //前序遍历的过程
    cout<<"前序非递归遍历方法1:";
    while(p!=NULL)
    {
        //显示结点
        cout<<p->data<<" ";
        //左不空,右不空
        if(p->leftChild!=NULL
            && p->rightChild!=NULL)
        {
            //把右子结点压入堆栈
            LS.Push(p->rightChild);
            //进入左子树
            p=p->leftChild;
        }
        //左不空,右空
        else if(p->leftChild!=NULL
            && p->rightChild==NULL)
            //进入左子树
            p=p->leftChild;
        //左空,右不空
        else if(p->leftChild==NULL
            && p->rightChild!=NULL)
            //进入右子树
            p=p->rightChild;
        //左空,右空
        else if(p->leftChild==NULL
            && p->rightChild==NULL)
            //回溯
            LS.Pop(p);
    }    
};
//////////////////////////////////preOd1()函数结束

//////////////////////////////////////////////////
//公有成员函数preOd2()
//第二种非递归前序遍历的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd2()
{
    //回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点遍历指针
    BinTreeNode<T>* p=root;
    //先把空指针入堆栈
    LS.Push(NULL);
    //遍历的过程
    cout<<"前序非递归遍历方法2:";
    while(p!=NULL)
    {
        cout<<p->data<<" ";         //访问当前结点
        if(p->rightChild!=NULL)     //如果右子结点不空
            LS.Push(p->rightChild); //把由子结点指针入栈
        
        if(p->leftChild!=NULL)      //如果左子结点不空
            p=p->leftChild;         //进入左子树
        else                        //如果左子树为空
            LS.Pop(p);              //回溯到右子树
    }
};
//////////////////////////////////preOd2()函数结束

//////////////////////////////////////////////////
//公有成员函数preOd3()
//第三种非递归前序遍历的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd3()
{
    //回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点遍历指针
    BinTreeNode<T>* p;
    //先把根结点指针入堆栈
    LS.Push(root);
    //遍历的过程
    cout<<"前序非递归遍历方法3:";
    while(!LS.IsEmpty())
    {
        //从堆栈取一个元素
        LS.Pop(p);
        //访问p结点
        cout<<p->data<<" ";
        //若右子树不空则入栈
        if(p->rightChild!=NULL)
            LS.Push(p->rightChild);
        //若左子树不空则入栈
        if(p->leftChild!=NULL)
            LS.Push(p->leftChild);
    };    
};
//////////////////////////////////////preOd3()函数

//////////////////////////////////////////////////
//公有成员函数levelOrder()函数
//按层次顺遍历当前二叉树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::levelOrder(
        void(*visit)(BinTreeNode<T>* p))
{
    //层次遍原始历用的队列
    LinkedQueue<BinTreeNode<T>* > Q;
    //指针
    BinTreeNode<T>* p=root;
    //先把根结点入栈
    Q.EnQueue(p);
    //层次遍历
    while(!Q.IsEmpty())
    {
        //先从队列中读取一个元素
        Q.DeQueue(p);
        //访问该结点
        visit(p);
        //把左子结点入队列
        if(p->leftChild!=NULL)
            Q.EnQueue(p->leftChild);
        //把右子结点入队列
        if(p->rightChild!=NULL)
            Q.EnQueue(p->rightChild);
    };
};
//////////////////////////////levelOrder()函数结束

//////////////////////////////////////////////////
//公又成员函数inOd1()
//非递归遍历二叉树的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::inOd1(
     void(*visit)(BinTreeNode<T>* p))
{
    //递归工作堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点指针变量
    BinTreeNode<T>* p=root;

    //遍历的过程
    cout<<"非递归中序遍历的第1种方法:";
    do
    {
        //向左递归
        while(p!=NULL)
        {
            //压入堆栈
            LS.Push(p);
            p=p->leftChild;
        };

        //如果堆栈不空
        if(!LS.IsEmpty())
        {
            //弹出堆栈
            LS.Pop(p);
            //访问结点
            visit(p);
            //进入右子树
            p=p->rightChild;
        };
    }
    while(p!=NULL || !LS.IsEmpty());
};
///////////////////////////////////inOd1()函数结束

//////////////////////////////////////////////////
//公又成员函数postOd()函数
//后序遍历二叉树的算法实现
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::postOd(
        void(*visit)(BinTreeNode<T>* p))
{
    LinkedStack<stkNode<T> > S;      //回溯用的堆栈
    stkNode<T> w;                    //结点变量
    BinTreeNode<T>* p=root;          //遍历用的指针

    do
    {
        while(p!=NULL)               //左子树经过的结点加标志"L"入栈
        {
            w.ptr=p;                 
            w.tag=0;
            S.Push(w);
            p=p->leftChild;          //向左子树的方向走下去
        };
        int continue1=1;             //继续循环的标志,用于R
        while(continue1!=0 && !S.IsEmpty())
        {
            S.Pop(w);p=w.ptr;        //堆栈不空就退栈
            switch(w.tag)            //判断从堆栈弹出元素的标志
            {
            case 0:
                w.tag=1;            
                S.Push(w);           //从左子树退回，修改tag
                continue1=0;
                p=p->rightChild;     //从右子树往下走
                break;
            case 1:
                visit(p);            //从右子树退回访问根结点
                break;
            }
        }
    }while(!S.IsEmpty());
    cout<<endl;
};
//////////////////////////////////postOd()函数结束

//////////////////////////////////////////////////
//Find()公有成员函数
//在当前的二叉树中搜索值为T的结点,返回该结点的指针
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Find(T item)const
{
    //寻找以root树根的子树中item项结点的指针
    return Find(root,item);
};
////////////////////////////////////Find()函数结束

//////////////////////////////////////////////////
//Insert()私有成员函数
//在二叉树中item元素下，插入新元素item2
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::Insert(const T item1,const T item2,char c)
{
    //找到item1的结点的指针
    BinTreeNode<T>* p=Find(item1);
    if(p==NULL)
    {
        cout<<"没有找到item1对应的结点!"<<endl;
        return false;
    }
    else
    {
        //在左子树位置插入
        if(c=='l')
        {
            //左子树为空可以插入
            if(p->leftChild==NULL)
            {
                BinTreeNode<T>* l=new
                    BinTreeNode<T>(item2);
                p->leftChild=l;
                return true;
            }
            else
            {
                cout<<"左子树不空，无法插入!"<<endl;
                return false;
            }
        }
        //在右子树的位置插入
        else if(c=='r')
        {
            //右子树为空可以插入
            if(p->rightChild==NULL)
            {
                BinTreeNode<T>* r=new
                    BinTreeNode<T>(item2);
                p->rightChild=r;
                return true;
            }
            else
            {
                cout<<"右子树不空,无法插入!"<<endl;
                return false;
            }
        }
        else
        {
            cout<<"位提示在左还是右插入!"<<endl;
            return false;
        }
    }
};
//////////////////////////////Insert()私有函数结束

//////////////////////////////////////////////////
//CreateBinTree()私有成员函数
//通过广义表描述字符串建立一棵二叉树,通过指针返回
//例如A(B,C(E,F))#
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateBinTree(char* BinStr
            ,BinTreeNode<T>*& subTree)
{
    //逐个读取字符串
    int i=0;               //游标
    int k=0;               //处理标志,0表示根结点,1表示左子树,2表示
    char s;                //存放每次取出的字符
    LinkedStack<BinTreeNode<char>*> LS;
                           //创建二叉树过程中用到的结点指针堆栈
    BinTreeNode<char>* p;  //结点指针变量
    BinTreeNode<char>* t;  //存放从堆栈中弹出的内容
    BinTreeNode<char>* top;//用于存放从堆栈中取出的栈顶元素
         
    while(BinStr[i]!='#')
    {
        s=BinStr[i];
        switch(s)
        {
        case '(':
            LS.Push(p);  //把当前p的内容入栈
            k=1;         //进入左子树的处理
            break;
        case ',':
            k=2;         //进入右子树的处理
            break;
        case ')':
            LS.Pop(t);   //弹出堆栈的内容
            break;
        default:
            //如果取出的字母
            {
                //如果处理的是根结点
                if(k==0)
                {
                    //新建一个结点
                    p=new BinTreeNode<char>(s);
                    //把该指针作为树的指针返回
                    subTree=p;
                }
                //如果处理的是右子树
                else if(k==1)
                {
                    //新建一个接点
                    p=new BinTreeNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->leftChild=p;
                }
                //如果处理的是左子树
                else
                {
                    //新建一个接点
                    p=new BinTreeNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->rightChild=p;
                };
                break;
            };
        };
        i++;
    }
};
///////////////////////////////CreateBinTree()结束