二叉树的链式实现

binaryTree.h

#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H

#include<iostream>
using namespace std;

template<typename T>
class BinTreeNode{
public:
    T data;
    BinTreeNode<T> *leftChild,*rightChild;
    BinTreeNode():leftChild(NULL),rightChild(NULL){}
    BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T>*r=NULL)
        :data(x),leftChild(l),rightChild(r){}
};

template<typename T>
class BinaryTree{
public:
    BinaryTree():root(NULL){}
    BinaryTree(T value):RefValue(value),root(NULL){}
    BinaryTree(BinaryTree<T>& s);
    ~BinaryTree(){destroy(root);}
    bool IsEmpty(){
        return root==NULL?true:false;
    }
    BinTreeNode<T> *Parent(BinTreeNode<T>* current){
        return (root==NULL||root==current)?
                    NULL:Parent(root,current);
    }
    BinTreeNode<T> *LeftChild(BinTreeNode<T>* current){
        return current!=NULL?current->leftChild:NULL;
    }
    BinTreeNode<T> *rightChild(BinTreeNode<T>* current){
        return current!=NULL?current->rightChild:NULL;
    }
    int Height(){
        return Height(root);
    }
    int Size(){
        return Size(root);
    }
    BinTreeNode<T> *getRoot()const{
        return root;
    }
    void preOrder(void(* visit)(BinTreeNode<T> *p)){
        preOrder(root,visit);
    }
    void inOrder(void(* visit)(BinTreeNode<T> *p)){
        inOrder(root,visit);
    }
    void postOrder(void(* visit)(BinTreeNode<T> *p)){
        postOrder(root,visit);
    }
    void levelOrder(void(* visit)(BinTreeNode<T> *p));
    int Insert(const T& item);
    BinTreeNode<T> *Find(T& item)const;
protected:
    BinTreeNode<T> *root;
    T RefValue;//数据输入停止标志
    void createBinTree(istream& in,BinTreeNode<T>*& subTree);
    bool Insert(BinTreeNode<T> *& subTree,const T& x);
    void destroy(BinTreeNode<T> *& subTree);
    bool Find(BinTreeNode<T> * subTree,const T& x)const;
    BinTreeNode<T> *Copy(BinTreeNode<T> *orignode);
    int Height(BinTreeNode<T> *subTree)const;
    int Size(BinTreeNode<T> *subTree)const;
    BinTreeNode<T> *Parent(BinTreeNode<T>* subTree,
                           BinTreeNode<T>* current);
    //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>& Tree,
                   void (*visit)(BinTreeNode<T> *p));
    friend istream& operator>>(istream& in,BinaryTree<T>& Tree);
    friend ostream& operator<<(ostream& out,BinaryTree<T>& Tree){
        out << "preOrder" << endl;
        Tree.Traverse(Tree.root,out);
        out << endl;
        return out;
    }
};

#endif // LINKEDBINARYTREE_H

binaryTree.cpp

#include"LinkedBinaryTree.h"
#include<iostream>
#include<stdlib.h>
#include"../T3/Stack.h"
using namespace std;

template<typename T>
void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree)
{
    if(subTree!=NULL){
        destroy(subTree->leftChild);//递归删除左子树
        destroy(subTree->rightChild);//递归删除右子树
        delete subTree;
    }
}

/*
  从subTree向下搜索current的父结点
  */
template<typename T>
BinTreeNode<T>*
BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
{
    if(subTree==NULL)
        return NULL;
    if(subTree->leftChild||subTree->rightChild==current)
        return subTree;
    BinTreeNode<T> *p;
    if((p=Parent(subTree->leftChild,current))!=NULL)
        return p;
    else
        return Parent(subTree->rightChild,current);
}

template<typename T>
void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream &out)
{
    if(subTree!=NULL){
        out << subTree->data << ",";
        Traverse(subTree->leftChild,out);
        Traverse(subTree->rightChild,out);
    }
}

template<typename T>
void BinaryTree<T>::createBinTree(istream &in, BinTreeNode<T> *&subTree)
{
    Stack<BinTreeNode<char>*> s;
    subTree = NULL;
    BinTreeNode<char> *p,*t;
    int k;
    char ch;
    in >> ch;
    while(ch!=RefValue){
        switch(ch){
        case '(':
            s.Push(p);
            k=1;
            break;
        case ')':
            s.Pop(t);
            break;
        case ',':
            k=2;
            break;
        default:
            p=new BinTreeNode<char>(ch);
            if(subTree==NULL)
                subTree=p;
            else if(k==1){
                s.getTop(t);
                t->leftChild=p;
            }else{
                s.getTop(t);
                t->rightChild=p;
            }
        }
        in>>ch;
    }
}

template<typename T>
void BinaryTree<T>::inOrder(BinTreeNode<T>& subTree,
             void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        InOrder(subTree->leftChild,visit);
        visit(subTree);
        InOrder(subTree->rightChild,visit);
    }
}

template<typename T>
void BinaryTree<T>::preOrder(BinTreeNode<T>& subTree,
              void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        visit(subTree);
        PreOrder(subTree->leftChild,visit);
        PreOrder(subTree->rightChild,visit);
    }
}

/*
  后序遍历
  */
template<typename T>
void BinaryTree<T>::postOrder(BinTreeNode<T>& subTree,
               void (*visit)(BinTreeNode<T> *p))
{
    if(subTree!=NULL){
        postOrder(subTree->leftChild,visit);
        postOrder(subTree->rightChild,visit);
        visit(subTree);
    }
}

template<typename T>
int BinaryTree<T>::Size(BinTreeNode<T> *subTree)const
{
    if(subTree==NULL)
        return 0;
    return 1+Size(subTree->leftChild)+Size(subTree->rightChild);
}

template<typename T>
int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const
{
    if(subTree==NULL)
        return 0;
    int leftHeight = Height(subTree->leftChild);
    int rightHeight = Height(subTree->rightChild);
    int height = leftHeight>rightHeight?leftHeight:rightHeight;
    height = height+1;
    return height;
}

template<typename T>
BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode)
{
    if(orignode==NULL)
        return NULL;
    BinTreeNode<T> *temp = new BinTreeNode<T>;
    temp->data = orignode->data;
    temp->leftChild = Copy(orignode->leftChild);
    temp->rightChild = Copy(orignode->rightChild);
    return temp;
}

template<typename T>
BinaryTree<T>::BinaryTree(BinaryTree<T> &s)
{
    root = Copy(s.root);
}

//template<typename T>
//void BinaryTree<T>::CreateBinTree(ifstream& in,BinTreeNode<T>*& subTree)
//{
//    T item;
//    if(!in.eof()){
//        in>>item;
//        if(item!=RefValue){
//            subTree = new BinTreeNode<T>(item);
//            assert(subTree!=NULL);
//            CreateBinTree(in,subTree->leftChild);
//            CreateBinTree(in,subTree->rightChild);
//        }else{
//            subTree=NULL;
//        }
//    }
//}

template<typename T>
void PrintBTree(BinTreeNode<T> *BT)
{
    if(BT!=NULL){
        cout << BT->data;
        if(BT->leftChild!=NULL||BT->rightChild!=NULL){
            cout << '(';
            PrintBTree(BT->leftChild);
            cout << ',';
            if(BT->rightChild!=NULL)
                PrintBTree(BT->rightChild);
            cout << ')';
        }
    }
}