实验3二叉树的应用完整代码

#include<iostream>
#include<Windows.h>
using namespace std;
//创建二叉树结构体；
typedef struct BiTNode {
  int data;
  struct BiTNode *lchild, *rchild;//左右孩子指针 
}BiTNode, *BiTree;
//构建一个循环队列
typedef struct Qnode {
  BiTNode *base;
  int front;//头
  int rear;//尾
}sqQueue;
class tree {
private:
  BiTree root;
  sqQueue q;
public:
  tree() {
    CreatBiTree(root);
  }
  BiTree get_root() {//得到root节点；
    return root;
  }
  //创建一个循环队列
  void InitQueue(sqQueue &q) {
    q.base = new BiTNode[5];
    q.front = q.rear = 0;
  }
  //创建二叉树
  BiTree CreatBiTree(BiTree &t) {
    int val;
    cin >> val;
    getchar();
    if (val <= 0) t = NULL;
    else {
      t = new BiTNode;
      t->data = val;
      CreatBiTree(t->lchild);
      CreatBiTree(t->rchild);
    }
    return t;
  }
  //先序遍历
  void PreOrderTraverse(BiTree &t) {
    if (!t) return;
    else {
      cout << t->data << " ";
      PreOrderTraverse(t->lchild);
      PreOrderTraverse(t->rchild);
    }
  }
  //中序排序
  void InOrderTraverse(BiTree &t) {
    if (!t) return;
    else {
      InOrderTraverse(t->lchild);
      cout << t->data << " ";
      InOrderTraverse(t->rchild);
    }
  }
  //后序遍历
  void PostOrderTraverse(BiTree &t) {
    if (!t) return;
    else {
      PostOrderTraverse(t->lchild);
      PostOrderTraverse(t->rchild);
      cout << t->data << " ";
    }
  }
  //层序遍历
  void LevelOrderTraverse(BiTree &t) {
    if (!t)return;
    else {
      InitQueue(q);
      q.base[q.rear] = *t;
      q.rear = (q.rear + 1) % 5;
    }
    while (q.front != q.rear) {
      BiTNode temp = q.base[q.front];
      cout << temp.data << " ";
      if (temp.lchild) {
        q.base[q.rear] = *temp.lchild;
        q.rear = (q.rear + 1) % 5;
      }
      if (temp.rchild) {
        q.base[q.rear] = *temp.rchild;
        q.rear = (q.rear + 1) % 5;
      }
      q.front = (q.front + 1) % 5;
    }
  }
  //统计节点的数目
  void Count_TreeEnds(BiTree &t, int &n) {
    if (t) {
      if (!t->lchild && !t->rchild)
        n++;
      Count_TreeEnds(t->lchild, n);
      Count_TreeEnds(t->rchild, n);
    }
  }
  //交换左右子树
  BiTree Exchange(BiTree &t) {
    if (!t)return NULL;
    BiTree lchild = Exchange(t->rchild);
    BiTree rchild = Exchange(t->lchild);
    t->lchild = lchild;
    t->rchild = rchild;
    return t;
  }
  //5. 计算并输出该二叉树的深度。
  int Depth(BiTree &t) {
    int l = 0, r = 0;
    if (t == NULL) return 0;
    l = Depth(t->lchild) + 1;
    r = Depth(t->rchild) + 1;
    return l > r ? l : r;
  }
};
int main() {
  tree T;
  int n = 0;//叶子结点
  int deep;//深度
  BiTree PT = T.get_root();
  cout << "先序遍历:";
  T.PreOrderTraverse(PT); cout << endl;
  cout << "中序遍历:";
  T.InOrderTraverse(PT); cout << endl;
  cout << "后序遍历:";
  T.PostOrderTraverse(PT); cout << endl;
  cout << "层序遍历:";
  T.LevelOrderTraverse(PT); cout << endl;
  cout << "叶子节点数：";
  T.Count_TreeEnds(PT, n);
  cout << n << endl;
  BiTree exT;
  exT = T.Exchange(PT);
  cout << "交换后的先序遍历:";
  T.PreOrderTraverse(exT); cout << endl;
  cout << "该二叉树的深度:";
  deep = T.Depth(exT); cout << deep << endl;
  system("pause");
  return 0;
}