二叉树实现（Ｃ＋＋）

二叉树真是磨人,历时两天才勉强写出了一个较为完整的二叉树及算法

废话不说，源码如下：

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <iostream>
#include <stack>

template<class T>
class BinTreeNode {
public:
  T data;
  BinTreeNode<T> *leftChild;
  BinTreeNode<T> *rightChild;
  // BinTreeNode<T> *parent;
  BinTreeNode(){
    leftChild=NULL;
    rightChild=NULL;
  }
  BinTreeNode(T x,BinTreeNode<T> *left=NULL,BinTreeNode<T> *right=NULL){
    data=x;
    leftChild=left;
    rightChild=right;
  }
  BinTreeNode(BinTreeNode<T> &s){
    data=s->data;
    leftChild=s.leftChild;
    rightChild=s.rightChild;
  }
  friend bool equal(BinTreeNode<T> *p,BinTreeNode<T> *q){
    if (p==NULL && q==NULL) {
      return true;
    }
    bool flag=(p!=NULL)&&(q!=NULL)&&(p->data==q->data)&&(equal(p->leftChild,q->leftChild))&&
              (equal(p->rightChild,q->rightChild));
    if (flag) {
      return true;
    } else {
      return false;
    }
  }
};

template<class T>
class StackNode {
public:
  BinTreeNode<T> *ptr;
  bool tag;
  StackNode():ptr(NULL){}
  StackNode(BinTreeNode<T> *p=NULL):ptr(p),tag(1){}
  virtual ~StackNode (){}
};

template<class T>
class BinaryTree {
protected:
  BinTreeNode<T> *root;//根指针
  T RefValue;//数据输入停止标志

public:
  BinaryTree ():root(NULL){}//构造函数
  BinaryTree(T value):RefValue(value),root(NULL){}//构造函数
  BinaryTree(BinaryTree<T> &s){root=copy(s.root);}//复制构造函数
  virtual ~BinaryTree (){remove(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> *getLeftChild(BinTreeNode<T> *current){
    return (current!=NULL)?current->leftChild:NULL;
  }//返回左子女
  BinTreeNode<T> *getRightChild(BinTreeNode<T> *current){
    return (current!=NULL)?current->rightChild:NULL;
  }//返回右子女
  BinTreeNode<T> *getRoot()const{return root;}//返回根结点
  int getHeight(){return getHeight(root);}//计算树高度
  int getSize(){return getSize(root);}//计算结点数
  bool search(T item){search(root,item);}//查找
  void input(){input(root);}//前序遍历输入
  void output(){output(root);}//前序遍历输出
  friend bool operator==(const BinaryTree<T> &p,const BinaryTree<T> &q){return (equal(p.root,q.root))?true:false;}//重载＝＝
  friend bool operator!=(const BinaryTree<T> &p,const BinaryTree<T> &q){return (equal(p.root,q.root))?false:true;}//重载!＝
  friend std::istream &operator>>(std::istream &is,BinaryTree<T> *p){input();}//前序遍历输入
  friend std::ostream &operator<<(std::ostream &os,BinaryTree<T> *p){output();}//前序遍历输出
  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 exchangeLeftandRight(){exchangeLeftandRight(root);}//左右子树交换

protected:
  BinTreeNode<T> *Parent(BinTreeNode<T> *subTree,BinTreeNode<T> *current);//返回父节点
  int getHeight(BinTreeNode<T> *subTree);//计算树高度
  int getSize(BinTreeNode<T> *subTree);//计算结点数
  void remove(BinTreeNode<T> *&subTree);//删除
  bool search(BinTreeNode<T> *subTree,T item);//查找
  BinTreeNode<T> *copy(BinTreeNode<T> *subTree);//复制
  void input(BinTreeNode<T> *&subTree);//前序遍历输入
  void output(BinTreeNode<T> *subTree);//先序遍历输出
  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 exchangeLeftandRight(BinTreeNode<T> *subTree);//左右子树交换
};


template<class T>
BinTreeNode<T> *BinaryTree<T>::Parent(BinTreeNode<T> *subTree,BinTreeNode<T> *current){
  if (subTree==NULL) {
    return NULL;
  }
  if (subTree->leftChild==current||subTree->rightChild==current) {
    return subTree;
  }
  BinTreeNode<T> *p;
  if ((p=Parent->leftChild!=NULL)) {
    return p;
  } else {
    return Parent(subTree->rightChild,current);
  }
}

template<class T>
int BinaryTree<T>::getHeight(BinTreeNode<T> *subTree){
  if (subTree==NULL) {
    return 0;
  } else {
    int lh=getHeight(subTree->leftChild);
    int rh=getHeight(subTree->rightChild);
    return ((lh>rh)?lh:rh)+1;
  }
}

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

template<class T>
void BinaryTree<T>::remove(BinTreeNode<T> *&subTree){
  if (subTree!=NULL) {
    remove(subTree->leftChild);
    remove(subTree->rightChild);
    delete subTree;
  }
}

template<class T>
bool BinaryTree<T>::search(BinTreeNode<T> *subTree,T item){
  if (subTree!=NULL) {
    return subTree->data==item || search(subTree->leftChild,item) || search(subTree->rightChild,item);
  }
}

template<class T>
BinTreeNode<T> *BinaryTree<T>::copy(BinTreeNode<T> *subTree){
  if (subTree==NULL) {
    return NULL;
  } else {
    BinTreeNode<T> *p=subTree;
    return p;
  }
}

template<class T>
void BinaryTree<T>::input(BinTreeNode<T> *&subTree){
  T item;
  std::cin >> item;
  if (item!=RefValue) {
    subTree=new BinTreeNode<T>(item);
    if (subTree==NULL) {
      std::cerr << "存储分配错误" << '\n';
      exit(1);
    }
    input(subTree->leftChild);
    input(subTree->rightChild);
  } else {
    subTree==NULL;
  }
}

template<class T>
void BinaryTree<T>::output(BinTreeNode<T> *subTree){
  if (subTree!=NULL) {
    std::cout << subTree->data << " ";
    output(subTree->leftChild);
    output(subTree->rightChild);
  }
}

// template<class 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<class 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<class 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<class T>//前序遍历非递归实现
void BinaryTree<T>::preOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p)){
  std::stack<BinTreeNode<T>*> s;
  BinTreeNode<T> *p=subTree;
  s.push(p);
  while (!s.empty()) {
    p=s.top();
    visit(p);
    s.pop();
    if (p->leftChild!=NULL) {
      s.push(p->leftChild);
    }
    if (p->rightChild!=NULL) {
      s.push(p->rightChild);
    }
  }
}

template<class T>//中序遍历非递归实现
void BinaryTree<T>::inOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p)){
  std::stack<BinTreeNode<T>*> s;
  BinTreeNode<T> *p=subTree;
  while (p!=NULL || !s.empty()) {
    while (p!=NULL) {
        s.push(p);
        p=p->leftChild;
    }
    if (!s.empty()) {
      p=s.top();
      visit(p);
      s.pop();
      p=p->rightChild;
    }
  }
}

template<class T>//后序遍历非递归实现
void BinaryTree<T>::postOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p)){
  std::stack<StackNode<T>> s;
  BinTreeNode<T> *p=subTree;
  StackNode<T> w(NULL);
  bool continueFlag;
  do {
    while (p!=NULL) {
      w=StackNode<T>(p);
      s.push(w);
      p=p->leftChild;
    }
    continueFlag=1;
    while (continueFlag && !s.empty()) {
      w=s.top();
      s.pop();
      p=w.ptr;
      if (w.tag) {
        w.tag=0;
        s.push(w);
        continueFlag=0;
        p=p->rightChild;;
      } else {
        visit(p);
      }
    }
  } while(!s.empty());
}

template<class T>
void BinaryTree<T>::exchangeLeftandRight(BinTreeNode<T> *subTree){
  if (subTree!=NULL && (subTree->leftChild!=NULL || subTree->rightChild!=NULL)) {
    BinTreeNode<T> *temp=subTree->leftChild;
    subTree->leftChild=subTree->rightChild;
    subTree->rightChild=temp;
    exchangeLeftandRight(subTree->leftChild);
    exchangeLeftandRight(subTree->rightChild);
  }
}

#endif