Ⅰ.說明：1.采用左孩子右兄弟的方式，轉化為二叉樹來實現(xiàn)。2.樹的后根遍歷與二叉樹的中根遍歷即有聯(lián)系又有區(qū)別，請讀者注意分析體會。Ⅱ.功能：1.創(chuàng)建樹并寫入數(shù)據(jù)2.先根遍歷樹3.計算樹高4.后根遍歷樹5.層次遍歷樹6.搜索數(shù)據(jù)域為某值的結點7.刪除數(shù)據(jù)域為某值的結點及其子樹8.銷毀樹Ⅲ.代碼：//.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> //輔助隊列，計算樹高 Quefh：queue for high struct Quefh {Node<T>* nodrs; //node's adressint leve; //levelQuefh<T>* hnext;Quefh(Node<T>* nds, int lel, Quefh<T>* hnxt); };template<typename T> //Quefh構造函數(shù) Quefh<T>::Quefh(Node<T>* nds, int lel, Quefh<T>* hnxt) {nodrs = nds;leve = lel;hnext = hnxt; }template<typename T> //輔助隊列，查找結點 Quefs：queue for search struct Quefs //此隊列同時用于層次遍歷 {Node<T>* snodrs; //Quefs::node's adressQuefs<T>* snext;Quefs(Node<T>* snds, Quefs<T>* snxt); };template<typename T> //Quefs構造函數(shù) Quefs<T>::Quefs(Node<T>* snds, Quefs<T>* snxt) {snodrs = snds;snext = snxt; }template<typename T> //輔助隊列，刪除結點 Quefd：queue for delete struct Quefd //此隊列同時在后根遍歷中做臨時堆棧 {T ddata;Quefd<T>* dnext;Quefd(const T& ddt, Quefd<T>* dnxt); };template<typename T> //Quefd構造函數(shù) Quefd<T>::Quefd(const T& ddt, Quefd<T>* dnxt) {ddata = ddt;dnext = dnxt; }template<typename T> //樹類 class Tree { private:Node<T>* root;Quefh<T> *hhead, *htail;Quefs<T> *shead, *stail;Quefd<T> *dhead, *dtail,*top;int size;int hsize;int ssize;int dsize; public:Tree();~Tree();void Operate(); private:Node<T>* Creat(Node<T>* &rt);void Destory(Node <T>* t);void Addqh(Node<T>* pn, int levl);void Addqs(Node<T>* spn); void Addqd(const T& dedata);void Outqh(Node<T>* &pn, int &levl);Node<T>* Outqs();void Delqh();void Delqs();void Delqd();int Couhg(Node<T>* t);Node<T>* GetFather(Node<T>* t, Node<T>* p);void Search(Node<T>* t, const T& item, bool& sign);void Del(Node<T>* t);void D_ShowAll(Quefd<T>* dheader);void FiRoTra(Node<T>* rt, int& ct);void MiRoTra(Node<T>* rt, int& ct);void LeveTra(Node<T>* t);void ShowAll(Quefs<T>* header);Node<T>* Push(Node<T>* t);void PopAll(int& ct); };template<typename T> //類構造函數(shù) Tree<T>::Tree() {root = NULL;hhead = NULL;htail = NULL;shead = NULL;stail = NULL;dhead = NULL;dtail = NULL;top = NULL;size = 0;hsize = 0;ssize = 0;dsize = 0; }template<typename T> //類析構函數(shù) Tree<T>::~Tree() {Destory(root); }template<typename T> //Quefh入隊一個結點 void Tree<T>::Addqh(Node<T>* pn, int levl) {if (!hhead){ hhead = htail = new Quefh<T>(pn, levl, NULL); hsize = 1; }else{htail->hnext = new Quefh<T>(pn, levl, NULL);htail = htail->hnext;hsize++;} }template<typename T> //Quefh出隊一個結點 void Tree<T>::Outqh(Node<T>* &pn, int &levl) {pn = hhead->nodrs; levl = hhead->leve;Quefh<T>* itemph;itemph = hhead;hhead = hhead->hnext;delete itemph;hsize--; }template<typename T> //清空隊列Quefh void Tree<T>::Delqh() {while (hhead){Quefh<T>* itemphd;itemphd = hhead; hhead = hhead->hnext; delete itemphd;} }template<typename T> //Quefs入隊一個結點 void Tree<T>::Addqs(Node<T>* spn) {if (!shead){ shead = stail = new Quefs<T>(spn, NULL); ssize = 1; }else{stail->snext = new Quefs<T>(spn, NULL);stail = stail->snext;ssize++;} }template<typename T> //Quefs出隊一個結點 Node<T>* Tree<T>::Outqs() {Node<T>* pn;pn = shead->snodrs;Quefs<T>* itemps;itemps = shead;shead = shead->snext;delete itemps;ssize--;return pn; }template<typename T> //輸出隊列Quefs內全部元素 void Tree<T>::ShowAll(Quefs<T>* header) {Quefs<T>* p = header;for (int i = 1; i <= ssize; i++){cout << p->snodrs << " ";if (i % 5 == 0)cout << endl;p = p->snext;}cout << endl; }template<typename T> //清空隊列Quefs void Tree<T>::Delqs() {Quefs<T>* itempsd;while(shead){ itempsd = shead; shead = shead->snext; delete itempsd; } }template<typename T> //Quefd入隊一個結點 void Tree<T>::Addqd(const T& dedata) {if (!dhead){ dhead = dtail = new Quefd<T>(dedata, NULL); dsize = 1; }else{dtail->dnext = new Quefd<T>(dedata, NULL);dtail = dtail->dnext;dsize++;} }template<typename T> //輸出隊列Quefd內全部元素 void Tree<T>::D_ShowAll(Quefd<T>* dheader) {Quefd<T>* dp = dheader;for (int i = 1; i <= dsize; i++){cout << setiosflags(ios::left);cout << setw(10) << dp->ddata;if (i % 5 == 0)cout << endl;dp = dp->dnext;}cout << endl; }template<typename T> //利用結構體Quefd構造的臨時堆棧的入隊操作 Node<T>* Tree<T>::Push(Node<T>* t) {while (!t->right){top = new Quefd<T>(t->data, top);t = t->left;}return t; }template<typename T> //一次性彈出隊列中所有元素 void Tree<T>::PopAll(int& ct) {while (top){cout << setiosflags(ios::left);cout << setw(10) << top->ddata;ct++;if (ct % 5 == 0)cout << endl;Quefd<T>* itemp4;itemp4 = top; top = top->dnext; delete itemp4;} } template<typename T> //清空隊列Quefs void Tree<T>::Delqd() {Quefd<T>* itempdd;while (dhead){ itempdd = dhead; dhead = dhead->dnext; delete itempdd; } }template<typename T> //創(chuàng)建樹 Node<T>* Tree<T>::Creat(Node<T>* &rt) {int choice; bool flag;if (size > 0){cout << "是否繼續(xù)創(chuàng)建子樹？是請按1，否請按0：" << endl;cin >> choice;flag = true;}if (size == 0){cout << "請輸入根結點數(shù)據(jù);" << endl;T data; cin >> data;rt = new Node<T>(data);if (!rt){ cout << "根結點創(chuàng)建失敗！" << endl; return NULL; }size++;flag = false;cout << "根結點創(chuàng)建成功！" << endl;cout << "目前樹中共有結點" << size << "個。" << endl;}if (flag){if (choice == 0)return 0;else{cout << "請輸入子結點數(shù)據(jù);" << endl;T data; cin >> data;rt = new Node<T>(data);if (!rt){ cout << "子結點創(chuàng)建失敗！" << endl; return NULL; }size++;cout << "子結點創(chuàng)建成功！" << 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> //層次遍歷 LeveTra是level traversal的縮寫 void Tree<T>::LeveTra(Node<T>* t) {int count=0;Node<T>* pt;Addqs(t);while (ssize>0){pt = Outqs();count++;cout << setiosflags(ios::left);cout << setw(10) << pt->data;if (count % 5 == 0)cout << endl;pt = pt->left;while (pt){Addqs(pt);pt = pt->right;}} } template<typename T> //計算樹高 int Tree<T>::Couhg(Node<T>* t) {int level = 0, lev, max = 0;Node<T>* pt;Addqh(t, level);while (hsize>0){Outqh(pt, lev);level = lev + 1;if (max < lev)max = lev;while (pt){if (pt->left)Addqh(pt->left, level);pt = pt->right;}}hhead = htail = NULL;return max; }template<typename T> //搜索數(shù)據(jù)域為某值的結點 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 == item){ sign = true; Addqs(t); }} }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);Addqd(t->data);delete t;size--;} }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 << "請您選擇操作（輸入操作前的數(shù)字進行選擇）：" << endl;cout << "1.創(chuàng)建樹并寫入數(shù)據(jù)" << endl;cout << "2.先根遍歷樹" << endl;cout << "3.計算樹高" << endl;cout << "4.后根遍歷樹" << endl;cout << "5.層次遍歷樹" << endl;cout << "6.搜索數(shù)據(jù)域為某值的結點" << endl;cout << "7.刪除數(shù)據(jù)域為某值的結點及其子樹" << endl;cout << "8.銷毀樹" << endl;int choice;cin >> choice;switch (choice){//由用戶創(chuàng)建樹case 1:{if (root){ cout << "樹已經(jīng)創(chuàng)建，無需再建！若想新建，請您先銷毀舊樹！" << endl; break; }Creat(root);cout << "樹創(chuàng)建完成！" << endl;cout << "此樹中共有結點" << size << "個！" << endl;break;}//先根遍歷樹case 2:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法執(zhí)行遍歷操作，請您先創(chuàng)建樹！" << endl; break; }int counter2 = 0;FiRoTra(root, counter2);cout << endl;break;}//計算樹高 case 3:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法計算樹高，請您先創(chuàng)建樹！" << endl; break; }int high;high= Couhg(root); cout << "樹的高度為：" <<high<< endl;break;}//后根遍歷樹case 4:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法執(zhí)行遍歷操作，請您先創(chuàng)建樹！" << endl; break; }Node<T>* pt4 = Push(root);int counter4 = 0;MiRoTra(pt4, counter4);PopAll(counter4);cout << endl;break;}//層次遍歷樹case 5:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法執(zhí)行遍歷操作，請您先創(chuàng)建樹！" << endl; break; } LeveTra(root);cout << endl;shead = stail = NULL;break;}//搜索數(shù)據(jù)域為某值的結點 case 6:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法執(zhí)行搜索操作，請您先創(chuàng)建樹！" << endl; break; }cout << "請您輸入數(shù)據(jù)域的值;" << endl;T indata; cin >> indata;bool flag = false;Search(root, indata, flag);if (!flag){ cout << "該樹中沒有數(shù)據(jù)域為" << indata << "的結點！" << endl; break; }else cout << "該樹中數(shù)據(jù)域為" << indata << "的結點共有" << ssize << "個。" << endl;cout << "是否輸出這些結點的地址？是請按1，否則按0：" << endl;int choice6; cin >> choice6;if (choice6 == 1) ShowAll(shead);Delqs(); shead = stail = NULL; ssize = 0;break;}//刪除數(shù)據(jù)域為某值的結點及其子樹case 7:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀，無法執(zhí)行刪除操作，請您先創(chuàng)建樹！" << endl; break; }T data7; bool flag7 = false; bool sign7 = true; int choice7;cout << "請您輸入結點數(shù)據(jù)的值：" << endl;cin >> data7;Search(root, data7, flag7);if (!flag7){ cout << "目前樹中無數(shù)據(jù)域為" << data7 << "的結點！" << endl; break; }while (sign7){Node<T> *p7, *fp7;Quefs<T> *item7;p7 = shead->snodrs;item7 = shead; shead = shead->snext; delete item7; ssize--;if (p7 == root){cout << "數(shù)據(jù)域為" << data7 << "的結點為根結點，若執(zhí)行刪除操作將會銷毀整棵樹！" << endl;cout << "是否確定執(zhí)行刪除操作？確定請按1，取消請按0：" << endl;cin >> choice7;if (choice7 == 0){ Delqs(); shead = stail = NULL; ssize = 0; goto mark7; }else{Destory(p7); root = NULL; size = 0;cout << "刪除成功！同時整棵樹也被銷毀！" << endl;Delqs(); shead = stail = NULL; ssize = 0;goto mark7;}}fp7 = GetFather(root, p7);if (p7->right) //其實這兩個if可以合成一個，但考慮到程序的可讀性，分開來寫{if (fp7->left == p7)fp7->left = p7->right;if (fp7->right == p7) fp7->right = p7->right;p7->right = NULL;}if (!p7->right){if (fp7->left == p7)fp7->left = NULL;if (fp7->right == p7)fp7->right = NULL;}Del(p7);cout << "刪除成功！" << endl;if (ssize == 0){ cout << "此時樹中已無數(shù)據(jù)域為" << data7 << "的結點及其子樹！" << endl; sign7 = false; }if (ssize > 0){ cout << "但此時樹中數(shù)據(jù)域為" << data7 << "的結點還有" << ssize << "個！" << endl; }cout << "此次共刪除結點" << dsize << "個，" << "目前樹中還有結點" << size << "個。" << endl;cout << "是否顯示被刪除的各結點的值？是請按1，否則請按0：" << endl;cin >> choice7;if (choice7 == 1)D_ShowAll(dhead);Delqd(); dhead = dtail = NULL; dsize = 0;if (ssize > 0){cout << "是否繼續(xù)刪除數(shù)據(jù)域為" << data7 << "的結點及其子樹？是請按1，否則按0：" << endl;cin >> choice7;if (choice7 == 0)sign7 = false;}}Delqs(); shead = stail = NULL; ssize = 0;mark7:break;}//銷毀樹case 8:{if (!root){ cout << "樹還未創(chuàng)建或已被銷毀！" << endl; break; }cout << "您確定銷毀該樹嗎？確定請按1，取消請按0：" << endl;int choice8; cin >> choice8;if (choice8 == 0)break;else Destory(root);root = NULL;size = 0;cout << "樹已銷毀！" << endl;break;}//處理用戶的錯誤輸入 default:{cout << "您的輸入有誤，無法進行操作！" << endl;break;}}//switch結束//控制循環(huán)cout << "是否繼續(xù)？繼續(xù)請按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 << "敬告;請您務必按提示要求操作，如果您進行了規(guī)定以外的操作，由此造成的一切后果，將全部由您個人承擔，程序開發(fā)者概不負責！" << endl;cout << "是否進入程序？進入請按1，否則按0;" << endl;cin >> uscho;if (uscho == 0) return 0;//用戶選擇類型while (flag){cout << "請選擇您所要創(chuàng)建樹的數(shù)據(jù)類型，輸入類型前的數(shù)字進行選擇;" << 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; }Ⅳ.結語：代碼已經(jīng)過測試，在VS2013上成功運行！發(fā)此文有兩大目的：1.和大家交流經(jīng)驗，供需要的人參考。2.在下菜鳥，代碼中難免有不妥之處，懇求大神批評指正。您的批評就是在下提高的起點，對于您的批評，在下將不勝感激！

轉載于:https://www.cnblogs.com/zhangyuhang3/p/6872680.html

總結

以上是生活随笔為你收集整理的C++实现树的基本操作，界面友好，操作方便，运行流畅，运用模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。