使用免费的代码做网站,做动漫网站如何应用数据绑定,佛山网络公司哪家最好,主流的外贸平台Ⅰ.说明#xff1a;1.采用左孩子右兄弟的方式#xff0c;转化为二叉树来实现。2.树的后根遍历与二叉树的中根遍历即有联系又有区别#xff0c;请读者注意分析体会。Ⅱ.功能#xff1a;1.创建树并写入数据2.先根遍历树3.计算树高4.后根遍历树5.层次遍历树6.搜索数据域为某值… Ⅰ.说明1.采用左孩子右兄弟的方式转化为二叉树来实现。2.树的后根遍历与二叉树的中根遍历即有联系又有区别请读者注意分析体会。Ⅱ.功能1.创建树并写入数据2.先根遍历树3.计算树高4.后根遍历树5.层次遍历树6.搜索数据域为某值的结点7.删除数据域为某值的结点及其子树8.销毁树Ⅲ.代码//.h文件#ifndef TREE_H
#define TREE_H#includeiostream
#includeiomanip
using namespace std;templatetypename T //树结点
struct Node
{T data;NodeT *left, *right;Node(const T item);
};templatetypename T //树结点初始化
NodeT::Node(const T item)
{data item;left NULL;right NULL;
}templatetypename T //辅助队列计算树高 Quefhqueue for high
struct Quefh
{NodeT* nodrs; //nodes adressint leve; //levelQuefhT* hnext;Quefh(NodeT* nds, int lel, QuefhT* hnxt);
};templatetypename T //Quefh构造函数
QuefhT::Quefh(NodeT* nds, int lel, QuefhT* hnxt)
{nodrs nds;leve lel;hnext hnxt;
}templatetypename T //辅助队列查找结点 Quefsqueue for search
struct Quefs //此队列同时用于层次遍历
{NodeT* snodrs; //Quefs::nodes adressQuefsT* snext;Quefs(NodeT* snds, QuefsT* snxt);
};templatetypename T //Quefs构造函数
QuefsT::Quefs(NodeT* snds, QuefsT* snxt)
{snodrs snds;snext snxt;
}templatetypename T //辅助队列删除结点 Quefdqueue for delete
struct Quefd //此队列同时在后根遍历中做临时堆栈
{T ddata;QuefdT* dnext;Quefd(const T ddt, QuefdT* dnxt);
};templatetypename T //Quefd构造函数
QuefdT::Quefd(const T ddt, QuefdT* dnxt)
{ddata ddt;dnext dnxt;
}templatetypename T //树类
class Tree
{
private:NodeT* root;QuefhT *hhead, *htail;QuefsT *shead, *stail;QuefdT *dhead, *dtail,*top;int size;int hsize;int ssize;int dsize;
public:Tree();~Tree();void Operate();
private:NodeT* Creat(NodeT* rt);void Destory(Node T* t);void Addqh(NodeT* pn, int levl);void Addqs(NodeT* spn); void Addqd(const T dedata);void Outqh(NodeT* pn, int levl);NodeT* Outqs();void Delqh();void Delqs();void Delqd();int Couhg(NodeT* t);NodeT* GetFather(NodeT* t, NodeT* p);void Search(NodeT* t, const T item, bool sign);void Del(NodeT* t);void D_ShowAll(QuefdT* dheader);void FiRoTra(NodeT* rt, int ct);void MiRoTra(NodeT* rt, int ct);void LeveTra(NodeT* t);void ShowAll(QuefsT* header);NodeT* Push(NodeT* t);void PopAll(int ct);
};templatetypename T //类构造函数
TreeT::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;
}templatetypename T //类析构函数
TreeT::~Tree()
{Destory(root);
}templatetypename T //Quefh入队一个结点
void TreeT::Addqh(NodeT* pn, int levl)
{if (!hhead){ hhead htail new QuefhT(pn, levl, NULL); hsize 1; }else{htail-hnext new QuefhT(pn, levl, NULL);htail htail-hnext;hsize;}
}templatetypename T //Quefh出队一个结点
void TreeT::Outqh(NodeT* pn, int levl)
{pn hhead-nodrs; levl hhead-leve;QuefhT* itemph;itemph hhead;hhead hhead-hnext;delete itemph;hsize--;
}templatetypename T //清空队列Quefh
void TreeT::Delqh()
{while (hhead){QuefhT* itemphd;itemphd hhead; hhead hhead-hnext; delete itemphd;}
}templatetypename T //Quefs入队一个结点
void TreeT::Addqs(NodeT* spn)
{if (!shead){ shead stail new QuefsT(spn, NULL); ssize 1; }else{stail-snext new QuefsT(spn, NULL);stail stail-snext;ssize;}
}templatetypename T //Quefs出队一个结点
NodeT* TreeT::Outqs()
{NodeT* pn;pn shead-snodrs;QuefsT* itemps;itemps shead;shead shead-snext;delete itemps;ssize--;return pn;
}templatetypename T //输出队列Quefs内全部元素
void TreeT::ShowAll(QuefsT* header)
{QuefsT* p header;for (int i 1; i ssize; i){cout p-snodrs ;if (i % 5 0)cout endl;p p-snext;}cout endl;
}templatetypename T //清空队列Quefs
void TreeT::Delqs()
{QuefsT* itempsd;while(shead){ itempsd shead; shead shead-snext; delete itempsd; }
}templatetypename T //Quefd入队一个结点
void TreeT::Addqd(const T dedata)
{if (!dhead){ dhead dtail new QuefdT(dedata, NULL); dsize 1; }else{dtail-dnext new QuefdT(dedata, NULL);dtail dtail-dnext;dsize;}
}templatetypename T //输出队列Quefd内全部元素
void TreeT::D_ShowAll(QuefdT* dheader)
{QuefdT* 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;
}templatetypename T //利用结构体Quefd构造的临时堆栈的入队操作
NodeT* TreeT::Push(NodeT* t)
{while (!t-right){top new QuefdT(t-data, top);t t-left;}return t;
}templatetypename T //一次性弹出队列中所有元素
void TreeT::PopAll(int ct)
{while (top){cout setiosflags(ios::left);cout setw(10) top-ddata;ct;if (ct % 5 0)cout endl;QuefdT* itemp4;itemp4 top; top top-dnext; delete itemp4;}
}
templatetypename T //清空队列Quefs
void TreeT::Delqd()
{QuefdT* itempdd;while (dhead){ itempdd dhead; dhead dhead-dnext; delete itempdd; }
}templatetypename T //创建树
NodeT* TreeT::Creat(NodeT* 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 NodeT(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 NodeT(data);if (!rt){ cout 子结点创建失败 endl; return NULL; }size;cout 子结点创建成功 endl;cout 目前树中共有结点 size 个。 endl;}}Creat(rt-left);Creat(rt-right);return root;
}templatetypename T //先根递归遍历 FiRoTra是first root traversal的缩写
void TreeT::FiRoTra(NodeT* 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);}
}templatetypename T //中根递归遍历 MiRoTra是middle root traversal的缩写 这里用来进行树的后根遍历
void TreeT::MiRoTra(NodeT* 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);}
}templatetypename T //层次遍历 LeveTra是level traversal的缩写
void TreeT::LeveTra(NodeT* t)
{int count0;NodeT* pt;Addqs(t);while (ssize0){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;}}
}
templatetypename T //计算树高
int TreeT::Couhg(NodeT* t)
{int level 0, lev, max 0;NodeT* pt;Addqh(t, level);while (hsize0){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;
}templatetypename T //搜索数据域为某值的结点
void TreeT::Search(NodeT* 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); }}
}templatetypename T //得到某结点以地址为关键值的父结点的地址
NodeT* TreeT::GetFather(NodeT* t, NodeT* p)
{NodeT* 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);
}templatetypename T //在树中删除以某结点为根的树
void TreeT::Del(NodeT* t)
{if (t ! NULL){Del(t-left);Del(t-right);Addqd(t-data);delete t;size--;}
}templatetypename T //销毁树
void TreeT::Destory(NodeT* t)
{if (t ! NULL){Destory(t-left);Destory(t-right);delete t;size--;}
}template typename T
void TreeT::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;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 high;high Couhg(root); cout 树的高度为 high endl;break;}//后根遍历树case 4:{if (!root){ cout 树还未创建或已被销毁无法执行遍历操作请您先创建树 endl; break; }NodeT* pt4 Push(root);int counter4 0;MiRoTra(pt4, counter4);PopAll(counter4);cout endl;break;}//层次遍历树case 5:{if (!root){ cout 树还未创建或已被销毁无法执行遍历操作请您先创建树 endl; break; } LeveTra(root);cout endl;shead stail 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 的结点共有 ssize 个。 endl;cout 是否输出这些结点的地址是请按1否则按0 endl;int choice6; cin choice6;if (choice6 1) ShowAll(shead);Delqs(); shead stail NULL; ssize 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; break; }while (sign7){NodeT *p7, *fp7;QuefsT *item7;p7 shead-snodrs;item7 shead; shead shead-snext; delete item7; ssize--;if (p7 root){cout 数据域为 data7 的结点为根结点若执行删除操作将会销毁整棵树 endl;cout 是否确定执行删除操作确定请按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 此时树中已无数据域为 data7 的结点及其子树 endl; sign7 false; }if (ssize 0){ cout 但此时树中数据域为 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 是否继续删除数据域为 data7 的结点及其子树是请按1否则按0 endl;cin choice7;if (choice7 0)sign7 false;}}Delqs(); shead stail NULL; ssize 0;mark7:break;}//销毁树case 8:{if (!root){ cout 树还未创建或已被销毁 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结束//控制循环cout 是否继续继续请按1退出请按0 endl;int ifgoon;cin ifgoon;if (ifgoon 0)flager false;}//while结束
}#endif//.cpp文件#includeTree.h
#includeiostream
using namespace std;
int main()
{//是否进入程序int uscho; bool flag true;//uschouser 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:{Treeint tree_int;tree_int.Operate();break;}case 2:{Treefloat tree_float;tree_float.Operate();break;}case 3:{Treechar tree_char;tree_char.Operate();break;}default:cout 您的输入有误 endl;break;}return 0;
}Ⅳ.结语代码已经过测试在VS2013上成功运行发此文有两大目的1.和大家交流经验供需要的人参考。2.在下菜鸟代码中难免有不妥之处恳求大神批评指正。您的批评就是在下提高的起点对于您的批评在下将不胜感激 转载于:https://www.cnblogs.com/zhangyuhang3/p/6872680.html
