二叉树实现

二叉树实现（Ｃ＋＋）

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

废话不说，源码如下：

#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

作者：丿feng
链接：https://www.jianshu.com/p/fed7468bd698