二叉树实现(包括遍历等各种操作,递归与非递归)

时间:2021-12-25 12:19:23

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

#include <iostream>
#include <queue>
#include <stack>

#define max(x, y)  ((x) > (y) ? (x) :(y))
int countnode=0; /* the number of nodes */

using namespace std;

template <class T>
class BinaryTree;
template <class T>
class BSTree;
template <class T>
class AVLTree;

template <class T>
class BinaryTreeNode
{
 public:
  BinaryTreeNode():left(0), right(0) {}
  BinaryTreeNode(const T &e):key(e), left(0), right(0){ }
  BinaryTreeNode(const T &e, BinaryTreeNode *l, BinaryTreeNode *r):key(e),/
        left(l), right(r) {}
  T keyValue()
  {
   return key;
  }
  
  friend class BinaryTree<T>;
  friend class BSTree<T>;
  friend class AVLTree<T>;
 protected:
  T key;
  BinaryTreeNode  *left;
  BinaryTreeNode *right;  
};

template <class T>
class BinaryTree
{
 public:
  BinaryTree():root(0) {}
  BinaryTree(BinaryTreeNode<T> *r):root(r) {}
  BinaryTree(const T &t):root(new BinaryTreeNode<T>(t)) {}
  virtual ~BinaryTree()
  {
   destroyTree(root);
   root = 0;
  }
  void makeTree(const T &t, BinaryTree &left, BinaryTree &right);
  void preOrder(void (*visit)(BinaryTreeNode<T> *node))
  {
   preOrder(visit, root);
  }
  void inOrder(void (*visit)(BinaryTreeNode<T> *node))
  {
   inOrder(visit, root);
  }
  void postOrder(void (*visit)(BinaryTreeNode<T> *node))
  {
   postOrder(visit, root);
  }
  void levelOrder(void (*visit)(BinaryTreeNode<T> *node))
  {
   levelOrder(visit, root);
  }
  void nonRecurPre(void (*visit)(BinaryTreeNode<T> *node))
  {
   nonRecurPre(visit,root);
  }
  void nonRecurIn(void (*visit)(BinaryTreeNode<T> *node))
  {
   nonRecurIn(visit,root);
  };
  void nonRecurPost(void (*visit)(BinaryTreeNode<T> *node))
  {
   nonRecurPost(visit,root);
  }
  int height()
  {
   return height(root);
  }
  BinaryTreeNode<T> *copyTree()
  {
   return copyTree(root);
  }
  int countLeaf()
  {
   return countLeaf(root);
  }
  int countNode()
  {
   return countNode(root);
  };
  void destroyTree();
 protected:
  BinaryTreeNode<T> *root;
  void preOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
  void inOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
  void postOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
  void levelOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);

  void nonRecurPre(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
  void nonRecurIn(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
  void nonRecurPost(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);

  int height(BinaryTreeNode<T> *t);
  BinaryTreeNode<T> *copyTree(BinaryTreeNode<T> *node) ;
  int countLeaf(BinaryTreeNode<T> *t);
  void destroyTree(BinaryTreeNode<T> *t);
  int countNode(BinaryTreeNode<T> *t);
};

template <class T>
void BinaryTree<T>::makeTree(const T &t, BinaryTree &left, BinaryTree &right)
{
 root = new BinaryTreeNode<T>(t, left.root, right.root);
 if (root == NULL)
 {
  cout<<"malloc fails!"<<endl;
  return;
 }
 left.root = right.root = 0;
}

template <class T>
void BinaryTree<T>::preOrder(void (*visit)(BinaryTreeNode<T> *node), /
        BinaryTreeNode<T> *t)
{
 if(t)
 {
  visit(t);
  preOrder(visit, t->left);
  preOrder(visit, t->right);
 }
}

template <class T>
void BinaryTree<T>::inOrder(void (*visit)(BinaryTreeNode<T> *node),
       BinaryTreeNode<T> *t) {
 if(t){
  inOrder(visit, t->left);
  visit(t);
  inOrder(visit, t->right);
 }
}

template <class T>
void BinaryTree<T>::postOrder(void (*visit)(BinaryTreeNode<T> *node),
         BinaryTreeNode<T> *t)
{
 if(t)
 {
  postOrder(visit, t->left);
  postOrder(visit, t->right);
  visit(t);
 }
}

template <class T>
void BinaryTree<T>::levelOrder(void (*visit)(BinaryTreeNode<T> *node),
          BinaryTreeNode<T> *t)
{
    queue<BinaryTreeNode<T>*> q;
 BinaryTreeNode<T> *temp;
 q.push(t);
 while(!q.empty())
 {
  temp=q.front();
  visit(temp);
  q.pop();
  if(temp->left)
   q.push(temp->left);
  if(temp->right)
   q.push(temp->right);
 }
}

template <class T>
void BinaryTree<T>::nonRecurPre(void (*visit)(BinaryTreeNode<T> *node),
        BinaryTreeNode<T> *t)
{
 stack<BinaryTreeNode<T>*> s;
 BinaryTreeNode<T> *current = t;
 s.push(current);
 while (!s.empty() || current != NULL)
 {
  if(current == NULL)
  {
   current = s.top();
   s.pop();
   if (current->right) 
   {
    current = current->right;
    s.push(current);
   }
   else
   {
    current = NULL;
   }
  }
  else
  {
   visit(current);
   if (current->left)
   {  
    current = current->left;
    s.push(current);
   }
   else
    current = NULL;
  }
 }
}

template <class T>
void BinaryTree<T>::nonRecurIn(void (*visit)(BinaryTreeNode<T> *node),
          BinaryTreeNode<T> *t)
{
 stack<BinaryTreeNode<T>*> s;
 BinaryTreeNode<T> *current = t;
 s.push(current);
 while (!s.empty() || current != NULL)
 {
  if(current == NULL)
  {
   current = s.top();
   visit(current);
   s.pop();
   if (current->right) 
   {
    current = current->right;
    s.push(current);
   }
   else
   {
    current = NULL;
   }
  }
  else
  {
   if (current->left)
   {  
    current = current->left;
    s.push(current);
   }
   else
    current = NULL;
  }
 }
}
//后序非递归遍历二叉树
template <class T>
void BinaryTree<T>::nonRecurPost(void (*visit)(BinaryTreeNode<T> *node),
         BinaryTreeNode<T> *t)
{
 stack<BinaryTreeNode<T>*> s;
 stack<int> sf;
 int flag = 0;
 BinaryTreeNode<T> *current = t;
 while (!s.empty() || current != NULL)
 {
  if(current)
  { 
    flag = 0;
    s.push(current);
    sf.push(flag);
    current = current->left;
  }
  else
  {
   current = s.top();
   s.pop();
   flag = sf.top();
   sf.pop();
   if (flag == 0)
   {
    flag = 1;
    s.push(current);
    sf.push(flag);
    current = current->right;
   }
   else
   {
    visit(current);
    current = NULL;
   }
  }
  
 }

}

template <class T>
int BinaryTree<T>::height(BinaryTreeNode<T> *t)
{
 if(!t)
  return 0;
 else
  return 1 + max(height(t->left), height(t->right));
}

template <class T>
BinaryTreeNode<T> *BinaryTree<T>::copyTree(BinaryTreeNode<T> *node)
{
 BinaryTreeNode<T> *l, *r, *p;
 if(!node)
  return NULL;
 if(node->left)
  l = copyTree(node->left);
 else
  l = NULL;
 if (node->right)
  r = copyTree(node->right);
 else
  r = NULL;
 p = new BinaryTreeNode<T>(node->key, l, r);
 return p;
}

template <class T>
int BinaryTree<T>::countLeaf(BinaryTreeNode<T> *t)
{
 static count = 0;
 if(!t)
  return 0;
 else
 {
  if(t->left)
   countLeaf(t->left);
  if(t->right)
   countLeaf(t->right);
  if((t->left == NULL) && (t->right == NULL))
   count++;
 }
 return count;
}

template <class T>
void add1(BinaryTreeNode<T> *t)
{
 countnode++;
}

template <class T>
int BinaryTree<T>::countNode(BinaryTreeNode<T> *t)
{
 countnode = 0;
 inOrder(add1, t);
 return countnode;
}

//delete tree functions
template <class T>
static void Free(BinaryTreeNode<T> *t){
 delete t;
 t = NULL;
}

template <class T>
void BinaryTree<T>::destroyTree() {
 postOrder(Free);
 root = 0;
}

template <class T>
void BinaryTree<T>::destroyTree(BinaryTreeNode<T> *t)
{
 if (t)
 {
  if(t->left)
   destroyTree(t->left);
  if(t->right)
   destroyTree(t->right);
  Free(t);
 }
}

#endif