二叉树的相关操作

BiTree() { bt = Creat(bt); } //创建树
~BiTree() { ReleaseTree(bt); } //销毁树
void PreOrder() { PreOrder(bt); } //前序遍历
void InOrder() { InOrder(bt); } //中序遍历
void PostOrder() { PostOrder(bt); } //后序遍历
void levelOrder() { levelOrder(bt); }//层序遍历
void swapLR() { swapLR(bt); } //交换子树
int leafCount() { return leafCount(bt); } //计算叶子
int nodeCount() { return nodeCount(bt); } //计算结点
int highOfTree() { return highOfTree(bt); } //计算树高

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
template<class T>
struct Node
{
  T data;
  Node<T> *L, *R;
};
template<class T>
class BiTree
{
public:
  BiTree() { bt = Creat(bt); }    //创建树
  ~BiTree() { ReleaseTree(bt); }    //销毁树
  void PreOrder() { PreOrder(bt); }  //前序遍历
  void InOrder() { InOrder(bt); }    //中序遍历
  void PostOrder() { PostOrder(bt); }  //后序遍历
  void LevelOrder() { LevelOrder(bt); }//层序遍历
  void swapLR() { swapLR(bt); }        //交换子树
  int leafCount() { return leafCount(bt); }  //计算叶子
  int nodeCount() { return nodeCount(bt); }  //计算结点
  int highOfTree() { return highOfTree(bt); } //计算树高
private:
  Node<T> *bt;
  Node<T> *Creat(Node<T>* bt);
  void PreOrder(Node<T>* bt);
  void InOrder(Node<T>* bt);
  void PostOrder(Node<T>* bt);
  void LevelOrder(Node<T>* bt);
  void ReleaseTree(Node<T>* bt);
  void swapLR(Node<T>* bt);
  int leafCount(Node<T> *bt);
  int nodeCount(Node<T> *bt);
  int highOfTree(Node<T> *bt);
};
template<class T>
Node<T>* BiTree<T>::Creat(Node<T>* bt)
{
  char ch;
  cin >> ch;
  if (ch == '#') bt = NULL;
  else {
    bt = new Node<T>; bt->data = ch;
    bt->L = Creat(bt->L);
    bt->R = Creat(bt->R);
  }
  return bt;
}
template<class T>
void BiTree<T>::PreOrder(Node<T>* bt)
{
  if (bt == NULL) return;
  else {
    cout << bt->data;
    PreOrder(bt->L);
    PreOrder(bt->R);
  }
}
template<class T>
void BiTree<T>::InOrder(Node<T>* bt)
{
  if (bt == NULL) return;
  else {
    InOrder(bt->L);
    cout << bt->data;
    InOrder(bt->R);
  }
}
template<class T>
void BiTree<T>::PostOrder(Node<T>* bt)
{
  if (bt == NULL) return;
  else {
    PostOrder(bt->L);
    PostOrder(bt->R);
    cout << bt->data;
  }
}
template<class T>
void BiTree<T>::LevelOrder(Node<T>* bt)
{
  queue<Node<T> *> que;
  if (bt == NULL)
    return;
  que.push(bt);
  while (!que.empty())
  {
    Node<T> *q = que.front();
    que.pop();
    cout << q->data;
    if (q->L != NULL)
      que.push(q->L);
    if (q->R != NULL)
      que.push(q->R);
  }
  cout << endl;
}


template<class T>
void BiTree<T>::ReleaseTree(Node<T>* bt)
{
  if (bt != NULL)
  {
    ReleaseTree(bt->L);
    ReleaseTree(bt->R);
    delete bt;
  }
}
template<class T>
void BiTree<T>::swapLR(Node<T>* bt)
{
  if (bt->L == NULL && bt->R == NULL)
    return;
  else {
    swap(bt->L, bt->R);
  }
  if (bt->L)
    swapLR(bt->L);
  if (bt->R)
    swapLR(bt->R);
}
template<class T>
int BiTree<T>::leafCount(Node<T>* bt)
{
  int leaf = 0;
  if (bt == NULL)
    return 0;
  else if (bt->L == NULL && bt->R == NULL)
    return 1;
  else
    leaf = leafCount(bt->L) + leafCount(bt->R);
  return leaf;
}
template<class T>
int BiTree<T>::nodeCount(Node<T>* bt)
{
  int nodeNum = 0;
  if (bt == NULL)
    return 0;
  else {
    nodeNum = 1 + nodeCount(bt->L) + nodeCount(bt->R);
  }
  return nodeNum;
}
template<class T>
int BiTree<T>::highOfTree(Node<T>* bt)
{
  int hL = 0, hR = 0;
  if (bt == NULL)
    return 0;
  else {
    hL = highOfTree(bt->L);
    hR = highOfTree(bt->R);
    if (hL < hR)
      return hR + 1;
    else
      return hL + 1;
  }
  return 0;
}
int main()
{
  char cont;
    do
    {
      cout << "输入扩展的前序序列以创建树" << endl;
      BiTree<char> bt;//树的构建

      bt.PreOrder();//前序遍历
      cout << endl;
        bt.InOrder();//中序遍历
      cout << endl;
      bt.PostOrder();//后序遍历
      cout << endl;
      bt.LevelOrder();//层序遍历
      cout << endl;
      cout << bt.nodeCount() << endl//结点数
        << bt.leafCount() << endl//叶子数
        << bt.highOfTree() << endl;//树高度
      bt.swapLR();//交换子树
      bt.PreOrder();//交换后前序
      cout << endl;
      bt.InOrder();//交换后中序
      cout << endl;
      bt.PostOrder(); //交换后后序
      cout << endl;
      bt.LevelOrder();//交换后层序
      cout << endl;
      
      cin >> cont;
    } while (cont == 'Y');//再来一次
    return 0;
}

 

发表评论

电子邮件地址不会被公开。