//.h文件 #ifndef TREE_H #define TREE_H #include<iostream> #include<iomanip> using namespace std; template<typename T> struct Node            //树结点{  T data;  Node<T> *left, *right;  Node(const T& item); }; template<typename T> Node<T>::Node(const T& item)   //树结点初始化{  data = item;  left = NULL;  right = NULL; } template<typename T>          //队列结点struct QNode {  Node<T>* pdata;  QNode<T>* next;  QNode( Node<T>* &pd,  QNode* tp); }; template<typename T>           //队列结点初始化QNode<T>::QNode( Node<T>* &pd,  QNode* tp)    {  pdata = pd;  next = tp; } template<typename T>            //放删除元素的队列结点struct DQNode {  T d_data;  DQNode<T>* dnext;  DQNode(const T& ditem, DQNode<T>* dp); }; template<typename T>                                 //放删除元素的队列结点初始化DQNode<T>::DQNode(const T& ditem, DQNode<T>* dp) {  d_data = ditem;  dnext = dp; } template<typename T>           //二叉树类class Tree { private:  Node<T>* root;  QNode<T>* head, *tail;  DQNode<T>*dhead, *dtail;  int size;//记录二叉树结点长度 int qsize;//记录队列长度 int dsize;//记录DQNode队列长度public:  Tree();  ~Tree();  void Operate(); private:  Node<T>* Creat(Node<T>* &rt);  void Destory(Node<T>* t);  void Del(Node<T>* t);  void FiRoTra(Node<T>* rt ,int& ct);  void MiRoTra(Node<T>* rt, int& ct);  void LaRoTra(Node<T>* rt, int& ct);  void LeveTra(Node<T>* rt, int& ct);  void Addq( Node<T>* &pt);  Node<T>* Outq();  void AddDq(const T& tdata);  void Delq();  void Deld();  void ShowAll(QNode<T>* header);  void D_ShowAll(DQNode<T>* dheader);  Node<T>* GetFather(Node<T>* t, Node<T>* p);  void Search(Node<T>* t, const T& item, bool& sign); }; template<typename T>           //类构造函数Tree<T>::Tree() {  root = NULL;  head = NULL;  tail = NULL;  dhead = NULL;  dtail = NULL;  size = 0;  qsize = 0;  dsize = 0; } template<typename T>          //类析构函数Tree<T>::~Tree() {  Destory(root); } template<typename T>          //入队一个元素void Tree<T>::Addq( Node<T>* &pnode) {  if (!head){ head = tail = new QNode<T>(pnode,NULL); qsize = 1; }  else  {   tail->next = new QNode<T>(pnode, NULL);   tail = tail->next;   qsize++;  } } template<typename T>          //出队一个元素Node<T>* Tree<T>::Outq() {  Node<T>* p;  QNode<T>* item;  p = head->pdata;  item = head;  head = head->next;  delete item;  qsize--;  return p; } template<typename T>            //DQNode入队一个元素void Tree<T>:: AddDq(const T& tdata) {  if (!dhead){ dhead = dtail = new DQNode<T>(tdata, NULL); dsize = 1; }  else  {   dtail->dnext = new DQNode<T>(tdata, NULL);   dtail = dtail->dnext;   dsize++;  } } template<typename T>           //清空队列void Tree<T>::Delq() {   while (head)  {   QNode<T>* temp;   temp = head; head = head->next; delete temp;  } } template<typename T>           //清空DQNode队列void Tree<T>::Deld() {   while (dhead)  {   DQNode<T>* dtemp;   dtemp = dhead; dhead = dhead->dnext; delete dtemp;  } } template<typename T>               //输出队列内全部元素void Tree<T>::ShowAll(QNode<T>* header) {  QNode<T>* p = header;  for (int i = 1; i <= qsize;i++)  {   cout << p->pdata << "  ";   if (i % 5 == 0 )cout << endl;   p = p->next;  }  cout << endl; } template<typename T>               //输出DQNode队列内全部元素void Tree<T>::D_ShowAll(DQNode<T>* dheader) {  DQNode<T>* dp = dheader;  for (int i = 1; i <= dsize; i++)  {   cout << setiosflags(ios::left);   cout<<setw(10) << dp->d_data;   if (i % 5 == 0 )cout << endl;   dp = dp->dnext;  }  cout << endl; } template<typename T>                         //得到某结点（以地址为关键值）的父结点的地址Node<T>* Tree<T>::GetFather(Node<T>* t, Node<T>* p) {  Node<T>* q;  if (t == NULL)return NULL;  if (t->left == p || t->right == p)return t;  q = GetFather(t->left, p);  if (q!= NULL)return q;  else return GetFather(t->right, p); } template<typename T>             //在树中删除以某结点为根的树void Tree<T>::Del(Node<T>* t) {  if (t != NULL)  {   Del(t->left);   Del(t->right);   AddDq(t->data);   delete t;   size--;  } } template<typename T>           //创建二叉树Node<T>* Tree<T>::Creat(Node<T>* &rt) {  int choice; bool flag;  if (size > 0)  {   cout << "是否继续创建子树？是请按1，否请按0：" << endl;    cin >> choice;     flag = true;  }  if (size == 0)  {   cout << "请输入根结点数据;" << endl;   T data; cin >> data;   rt = new Node<T>(data);   if (!rt){ cout << "根结点创建失败！" << endl; return NULL; }   size++;      flag = false;   cout << "根结点创建成功！" << endl;   cout << "目前树中共有结点" << size << "个。" << endl;  }  if (flag)  {   if (choice == 0)return 0;   else   {    cout << "请输入子结点数据;" << endl;    T data; cin >> data;    rt = new Node<T>(data);    if (!rt){ cout << "子结点创建失败！" << endl; return NULL; }    size++;    cout << "子结点创建成功！" << endl;    cout << "目前树中共有结点" << size << "个。" << endl;   }  }  Creat(rt->left);  Creat(rt->right);  return root; } template<typename T>              //先根递归遍历 FiRoTra是first root traversal的缩写void Tree<T>::FiRoTra(Node<T>* rt ,int& ct) {  if (rt)  {   cout << setiosflags(ios::left);   cout<<setw(10) << rt->data;   ct++;    if (ct % 5 == 0)    cout << endl;   FiRoTra(rt->left,ct);   FiRoTra(rt->right,ct);  } } template<typename T>              //中根递归遍历 MiRoTra是middle root traversal的缩写void Tree<T>::MiRoTra(Node<T>* rt, int& ct) {  if (rt)  {   MiRoTra(rt->left, ct);   cout << setiosflags(ios::left);   cout <<setw(10)<< rt->data ;   ct++;   if (ct % 5 == 0)    cout << endl;   MiRoTra(rt->right, ct);  } } template<typename T>              //后根递归遍历 LaRoTra是last root traversal的缩写void Tree<T>::LaRoTra(Node<T>* rt, int& ct) {  if (rt)  {   LaRoTra(rt->left, ct);   LaRoTra(rt->right, ct);   cout << setiosflags(ios::left);   cout<<setw(10) << rt->data ;   ct++;   if (ct % 5 == 0)    cout << endl;   } } template<typename T>              //层次遍历 LeveTra是level traversal的缩写void Tree<T>::LeveTra(Node<T>* rt, int& ct) {  Addq(rt);  Node<T>* lt;  while (qsize>0)  {   lt=Outq();   ct++;   cout << setiosflags(ios::left);   cout <<setw(10)<< lt->data ;   if (ct % 5 == 0)    cout << endl;   if (lt->left != NULL)Addq(lt->left);   if (lt->right != NULL)Addq(lt->right);  } } template<typename T>            //搜索数据域为某值的结点void Tree<T>::Search(Node<T>* t, const T& item, bool& sign) {  if (t)  {   Search(t->left, item, sign);   Search(t->right, item, sign);   if (t->data =http://www.mamicode.com/= item){sign = true; Addq(t);}  } } template<typename T>           //销毁二叉树void Tree<T>::Destory(Node<T>* t) {   if (t!=NULL)  {   Destory(t->left);   Destory(t->right);   delete t;   size--;  } } //封装操作template <typename T> void Tree<T>::Operate() {  bool flager = true;  while (flager)  {   cout << "请您选择操作（输入操作前的数字进行选择）：" << endl;   cout << "1.创建二叉树并写入数据" << endl;   cout << "2.先根遍历二叉树" << endl;   cout << "3.中根遍历二叉树" << endl;   cout << "4.后根遍历二叉树" << endl;   cout << "5.层次遍历二叉树" << endl;   cout << "6.搜索数据域为某值的结点" << endl;   cout << "7.删除数据域为某值的结点及其子树" << endl;   cout << "8.判断是否为完全二叉树" << endl;   cout << "9.销毁二叉树" << endl;   int choice;   cin >> choice;   switch (choice)   {   //由用户创建二叉树  case 1:   {       if (root){ cout << "二叉树已经创建，无需再建！若想新建，请您先销毁旧树！" << endl; break; }       Creat(root);       cout << "二叉树创建完成！" << endl;       cout << "此二叉树中共有结点" << size << "个！" << endl;       break;   }   //先根遍历二叉树  case 2:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行遍历操作，请您先创建二叉树！" << endl; break; }       int counter2=0;       FiRoTra(root,counter2);       cout << endl;       break;   }   //中根遍历二叉树    case 3:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行遍历操作，请您先创建二叉树！" << endl; break; }       int counter3 = 0;       MiRoTra(root, counter3);       cout << endl;       break;   }   //后根遍历二叉树  case 4:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行遍历操作，请您先创建二叉树！" << endl; break; }       int counter4 = 0;       LaRoTra(root, counter4);       cout << endl;       break;   }   //层次遍历二叉树  case 5:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行遍历操作，请您先创建二叉树！" << endl; break; }       int counter5 = 0;       LeveTra(root, counter5);       cout << endl;       head = tail = NULL;       break;   }   //搜索数据域为某值的结点    case 6:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行搜索操作，请您先创建二叉树！" << endl; break; }       cout << "请您输入数据域的值;" << endl;       T indata;  cin >> indata;       bool flag = false;       Search(root, indata, flag);       if (!flag){ cout << "该二叉树中没有数据域为" << indata << "的结点！" << endl; break; }       else cout << "该二叉树中数据域为" << indata << "的结点共有"<<qsize<<"个。" << endl;       cout << "是否输出这些结点的地址？是请按1，否则按0：" << endl;       int choice6; cin >> choice6;       if (choice6 == 1)    ShowAll(head);       Delq(); head = tail = NULL; qsize = 0;       break;   }   //删除数据域为某值的结点及其子树  case 7:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法执行删除操作，请您先创建二叉树！" << endl; break; }       T data7; bool flag7 = false; bool sign7 = true; int choice7;       cout << "请您输入结点数据的值：" << endl;       cin >> data7;       Search(root, data7, flag7);       if (!flag7){ cout << "目前二叉树中无数据域为" << data7 << "的结点！" << endl; Delq(); head = tail = NULL; qsize = 0; break; }       while (sign7)       {        Node<T> *p7, *fp7;        QNode<T> *item7;        p7 = head->pdata;        item7 = head; head = head->next; delete item7; qsize--;        if (p7 == root)        {         cout << "数据域为"<<data7<<"的结点为根结点，若执行删除操作将会销毁整棵二叉树！" << endl;         cout << "是否确定执行删除操作？确定请按1，取消请按0：" << endl;         cin >> choice7;         if (choice7 == 0){ Delq(); head = tail = NULL; qsize = 0; goto mark7; }         else         {          Destory(p7); root = NULL; size = 0;          root = NULL;          cout << "删除成功！同时整棵二叉树也被销毁！" << endl;          Delq(); head = tail = NULL; qsize = 0;                   goto mark7;         }        }        fp7 = GetFather(root, p7);        if (fp7->left == p7)fp7->left = NULL;        else fp7->right = NULL;        Del(p7);        cout << "删除成功！" << endl;        if (qsize == 0){ cout << "此时树中已无数据域为" << data7 << "的结点及其子树！" << endl; sign7 = false; }        if (qsize > 0){ cout << "但此时树中数据域为" << data7 << "的结点还有" <<qsize<<"个！"<< endl; }        cout << "此次共删除结点" << dsize << "个，" << "目前树中还有结点" << size << "个。" << endl;        cout << "是否显示被删除的各结点的值？是请按1，否则请按0：" << endl;        cin >> choice7;        if (choice7 == 1)D_ShowAll(dhead);        Deld(); dhead = dtail = NULL; dsize = 0;        if (qsize > 0)        {         cout << "是否继续删除数据域为" <<data7<<"的结点及其子树？是请按1，否则按0："<< endl;         cin >> choice7;         if (choice7 == 0)sign7 = false;        }       }       Delq(); head = tail = NULL; qsize = 0;      mark7:break;   }   //判断是否为完全二叉树  case 8:   {       if (!root){ cout << "二叉树还未创建或已被销毁，无法进行判断，请您先创建二叉树！" << endl; break; }       bool branch=false;       Addq(root);       while (qsize>0)       {        Node<T>* pt;        pt = Outq();        if (!branch)        {         if (pt->left == NULL&&pt->right != NULL)         {          cout << "目前的二叉树不是完全二叉树！" << endl;          Delq(); head = tail = NULL; qsize = 0;          goto mark8;         }         if (pt->right==NULL)         {          branch = true;         }        }        else        {         if (pt->left != NULL || pt->right != NULL)         {          cout << "目前的二叉树不是完全二叉树！" << endl;          Delq(); head = tail = NULL; qsize = 0;          goto mark8;         }        }        if (pt->left != NULL)Addq(pt->left);        if (pt->right != NULL)Addq(pt->right);       }       cout << "目前的二叉树是完全二叉树！" << endl;       head = tail = NULL;      mark8:break;   }   //销毁二叉树  case 9:   {       if (!root){ cout << "二叉树还未创建或已被销毁！" << endl; break; }       cout << "您确定销毁该二叉树吗？确定请按1，取消请按0：" << endl;       int choice9; cin >> choice9;       if (choice9 == 0)break;       else Destory(root);       root = NULL;       size = 0;       cout << "二叉树已销毁！" << endl;       break;   }   //处理用户的错误输入    default:   {        cout << "您的输入有误，无法进行操作！" << endl;        break;   }   }//switch结束  //控制循环  cout << "是否继续？继续请按1，退出请按0：" << endl;   int ifgoon;   cin >> ifgoon;   if (ifgoon == 0)flager = false;  }//while结束} #endif //.cpp文件 #include"Tree.h" #include<iostream> using namespace std; int main() {  //是否进入程序 int uscho ;   bool flag = true;//uscho：user choice的缩写 cout << "敬告;请您务必按提示要求操作，如果您进行了规定以外的操作，由此造成的一切后果，将全部由您个人承担，程序开发者概不负责！" << endl;  cout << "是否进入程序？进入请按1，否则按0;" << endl;  cin >> uscho;  if (uscho == 0) return 0;  //用户选择类型 while (flag)  {   cout << "请选择您所要创建二叉树的数据类型，输入类型前的数字进行选择;" << endl;   cout << "1.整型  2.浮点  3.字符" << endl;   cin >> uscho;   if (uscho != 1 && uscho != 2 && uscho != 3)   {    cout << "您的输入有误！重新输入请按1，退出请按0：" << endl;    cin >> uscho;    if (uscho == 0)return 0;    else  flag = false;   }   if (flag) flag = false;   else flag = true;  }  switch (uscho)  {  case 1:  {      Tree<int> tree_int;      tree_int.Operate();      break;  }  case 2:  {      Tree<float> tree_float;      tree_float.Operate();      break;  }  case 3:  {      Tree<char> tree_char;      tree_char.Operate();      break;  }  default:   cout << "您的输入有误！" << endl;   break;  }  return 0; } 代码已经过测试，在VS2013上成功运行！ 发此文有两大目的： 1.和大家交流经验，供需要的人参考。 2.在下菜鸟，代码中难免有不妥之处，恳求大神批评指正。您的批评就是在下提高的起点，对于您的批评，在下将不胜感激！