2022年2022年关于树的初始化 .pdf

关于树的初始化 /（1）能进行初始化；即在算法中用双亲数组完成树的存储/（2）输入任一结点，求其在数组中的存储位置/（3）输入一结点，求其双亲/（4）输入一结点，求其孩子/（5）输入一结点，求其度(选作 ) 帮我写写 希望有注释 补充一下：typedef char elemtype; typedef struct elemtype data; int parent; pnode; typedef struct pnode nodesmaxsize; int num; psqtree; 后面不知道了 这个代码我写过，你可以参考下，提醒你代码还是自己写比较好：#ifndef PTREE_H #define PTREE_H #include #include #includeLinkedStack.h #includeLinkedQueue.h #define defaultSize 20 / /采用父结点表示法的树的结点结构/ template struct PTreeNode T data; /结点的数据域int parent; /父结点的指针PTreeNode(T val=-2,int par=-2) / 构造函数data=val;parent=par; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - ; /树的结点结构定义结束/ /PTree类模板用父结点表示法实现的树类/ template class PTree public: PTreeNode* NodeList; / 树的顺序存储的结点数组int size; /当前树的结点的最后位置int current; /当前结点的指针int maxSize; /默认的最大数组空间public: PTree(char* s,int n); / 构造函数 ,通过广义表描述字符串创建PTree() /析构函数 ,释放结点数组的内存空间delete NodeList; void Display(); / 显示当前树的存储结构的内容int FindParent(int i) / 找出当前结点的父结点指针return NodeListi.parent; int FindFirstChild(int i); /找出当前结点i 的长子结点int FindNextSibling(int i); /找出当前结点的相邻的兄弟结点int NearestCommonAncestor(int p,int q);/ 找 p 和 q 的最近公共祖先结点int CountLeaf(); / 计算当前树的叶子结点的个数int Depth(); / 求出当前树的深度; /PTree类模板声明结束/ /构造函数通过广义表描述字符串创建树/ template PTree:PTree(char* s,int n) /计算要开辟的内存空间的个数maxSize=ndefaultSize?n:defaultSize; /为结点数组开辟内存空间,需要结点结构默认构造函数NodeList=new PTreeNodemaxSize; /初始化数据成员current=0; size=-1; /标志名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - int flag=0; /结点指针堆栈LinkedStack LS; /用于存放栈顶的指针int top; /通过描述字符串建立一棵树int i=0; while(si!=#) switch(si) case (: /进入子树 ,把父结点的指针入栈 LS.Push(size); flag=1; break; case ,: /表示是从栈顶获取的父结点指针 flag=1; break; case ): /退栈 LS.Pop(top); flag=1; break; default: /数组指针向后推进一格 size+; /送入数据域 NodeListsize.data=si; /如果是根结点 ,则父结点为 -1 if(flag=0) NodeListsize.parent=-1; /如果是分支结点 ,从堆栈中获取父结点指针 else if(flag=1) LS.getTop(top); NodeListsize.parent=top; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - i+; ; / 通过广义表描述字符串创建树/ /Display() 公有成员函数/ template void PTree:Display() for(int i=0;i=size;i+) couti:NodeListi.data NodeListi.parentendl; ; /Display()公有成员函数/ /FindFirstChild() 公有成员函数/找出当前结点i 的长子结点的指针,如果没有就返回-1 / template int PTree:FindFirstChild(int i) /因为结点的顺序是前序序列,所以如果有长子结点/那肯定就在i 结点的下个相邻结点/如果该结点没有子结点if(NodeListi+1.parent!=i) return -1; else /否则下个结点就是其长子结点 return i+1; ; /FindFirstChild()函数结束/ /FindNextSibling() 公有成员函数/找出当前结点i 的下个兄弟结点 ,如果没有就返回-1 / template int PTree:FindNextSibling(int i) /寻找第一个和当前结点i 有相同父结点的结点for(int j=i+1;j=size;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - if(NodeListj.parent=NodeListi.parent) return j; /没有找到return -1; ; /FindNextSibling()函数结束/ /NearestCommonAncestor()公有成员函数/找结点 p 和结点 q 的最近公共祖先结点/ template int PTree:NearestCommonAncestor(int p,int q) /定义两个堆栈 ,存放 p,q 两个结点的所有祖先结点LinkedStack S1,S2; /保证 p 在前if(pq) int t;t=p;p=q;q=t; ; /寻找结点 p 和 q 的最近公共祖先结点/首先找出 p 的所有祖先结点while(p!=-1) /p 指针向上指向其父结点 p=NodeListp.parent; /把每次的父结点指针压入队列Q1 S1.Push(p); /再找出 q 的所有的祖先结点coutendl; while(q!=-1) /q 指指针向上指向其父结点 q=NodeListq.parent; /把每次的父结点压入队列Q2 S2.Push(q); ; /从队列 Q1 和 Q2 头部开始找最先相同的结点指针do /分别从对头取两个指针 S1.Pop(p); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - S2.Pop(q); while(p=q & !S1.IsEmpty() & !S2.IsEmpty(); /最后得到的是两者的最近公共祖先return p; ; /NearestCommonAncestor() 函数结束/ /CountLeaf() 公有成员函数/计算当前树中叶子结点的个数/作于 09年 1.16 / template int PTree:CountLeaf() int p=0; /计数器int f=1; /是否是叶子结点的标记变量for(int i=0;i=size;i+) /遍历数组的所有结点 f=1; for(int j=0;j=size;j+) if(NodeListj.parent=i) f=0; / 不是叶子结点break; ; ; if(f=1) p+; /是叶子结点; return p; ; /CountLeaf()函数结束/ /Depth()公有成员函数/求出当前二叉树的深度,算法思想 :从每个结点出发, /向根结点迈进 ,计算每个结点的最大层次数就是深度/ template int PTree:Depth() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - int depth=0; for(int i=0;i=size;i+) /遍历结点数组里的所有结点 int p=i,count=1; while(p!=0) / 从结点 i 往根迈进 p=NodeListp.parent;/ 求出结点 i 所在的层次 count+; ; if(deptht1.num; /输入树中第i 个结点的数据元素的值：/cint1.nodesi.data /输入第 i 个元素的双亲的下标#includeiostream.h typedef char elemtype; #define maxsize 10 typedef struct elemtype data;/数据元素的值int parent;/双亲结点下标位置pnode;/ 一个数据结点的类型typedef struct 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - pnode nodesmaxsize;/结构体数组，每一个元素有两个成员，data，parent int num;/树中结点的个数psqtree;/树的顺序存储结构类型void createtree(psqtree &t1) coutt1.num; for(int i=1;it1.nodesi.data; cint1.nodesi.parent; int arraylocation(psqtree &t1,elemtype e)/ 输入任一结点e，求其在数组中的存储位置i int i=1; while(t1.nodesi.data!=e) i+; return i; void getparent(psqtree &t1,elemtype e)/ 输入一结点，求其双亲 int i=1; while(t1.nodesi.data!=e) i+; coutt1.nodest1.nodesi.parent.data; void getsons(psqtree &t1,elemtype e)/输入一结点，求其孩子 int i=1; while(t1.nodesi.data!=e) i+; for(int j=1;j=t1.num;j+) if(t1.nodesj.parent=i) coutt1.nodesj.data; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - void getdu(psqtree &t1) int max=0;/结点子树的个数int i=-1;/ 结点的下标 while(it1.num) int num=0; for(int j=1;j=t1.num;j+) if(t1.nodesj.parent=i) num+; if(maxnum) max=num; i+; coutmax; void dislist(psqtree &t1) for(int i=1;i=t1.num;i+) coutt1.nodesi.data; / coutt1.nodesi.parent; void main() psqtree t1; createtree(t1); dislist(t1); elemtype e; coutendl; coute; cout数据的位置 :arraylocation(t1,e); coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - coute; getparent(t1,e); coutendl; coute; getsons(t1,e); coutendl; coutt1.num; /输入树中第i 个结点的数据元素的值：/cint1.nodesi.data /输入第 i 个元素的双亲的下标#includeiostream.h #define maxsize 20 typedef char elemtype; typedef char tsbnode; typedef struct /双亲存储结构 elemtype data; /数据元素的值int parent; /双亲结点下标pnode; /一个结点结构typedef struct /孩子链存储结构 pnode nodesmaxsize; /结构体数组，每一个元素有两个成员，data，parent int num; /树中结点的个数psqtree; /树的顺序存储结构类型void createtree(psqtree &t1) /能进行初始化；即在算法中用双亲数组完成树的存储 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - int i; for(i=1;i=t1.num;i+) /依次输入元素的值，初始化数组nodes cout输出第 it1.nodesi.data; cint1.nodesi.parent; void gettree(psqtree &t1,elemtype e) / 输入任一结点值，求其在数组中的存储位置 int i=1; while(e!=t1.nodesi.data) i+; if(it1.num) cout无此结点 !endl; else coutiendl; void gettreel(psqtree &t1,elemtype e) /输入一结点值，求其双亲 int i; coute; while(e!=t1.nodesi.data) i+; if(t1.nodesi.data=t1.nodes0.data) cout此结点为根节点，没有双亲!t1.num) cout无此结点 !endl; else cout其双亲元素的值为：endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - coutt1.nodest1.nodesi.parent.dataendl; void gettree2(psqtree &t1,elemtype e) / 输入一结点，求其孩子 int i=1; coute; int j=0; while(t1.nodesi.data!=e) i+; while(jt1.num) if(t1.nodesj.parent=i) cout子结点 :t1.nodesj.dataendl; j+; void main() psqtree t1; /定义树变量elemtype e; coutt1.num; createtree(t1); coute; cout存储的位置是：endl; gettree(t1,e); gettreel(t1,e); gettree2(t1,e); 较经典的：#includeiostream.h 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - #include typedef char elemtype; class pnode public: elemtype data; int parent; ;/ 一个结点结构class psqtree pnode nodes50; int num; public: void init();/ 初始化int locateelem(char p);/求结点位置void findparent(char p);/ 求双亲void findchild(char p);/ 求孩子和度;/ 树的顺序存储结构类型void psqtree:init() int i,m; char e; coutnum; for(i=0;inum;i+) cout请输入节点 i+1e;nodesi.data=e; cout请输入节点 i+1m;nodesi.parent=m; coutnum) cout无此值的结点，自己看清楚点啊- -|n;return 0; else cout 节点的位置 :i+1endl;return 1; void psqtree:findparent(char p) int i=0; while(nodesi.data!=p) i+; if(nodesi.data=nodes0.data) coutnum) cout 无此值的结点，自己看清楚点啊- -|n; else cout双亲求到啦 :nodesnodesi.parent-1.dataendl; void psqtree:findchild(char p) int i=0,j=0,m=0; while(nodesi.data!=p) i+; i+; while(jnum) if(nodesj.parent=i) cout子结点 :nodesj.dataendl;m+; j+; if(!m) coutsorry, 这个结点没有孩子n; cout 该结点的度 :mendl; int main() psqtree s; s.init(); char reply=y; while(reply=y) system(cls); coutp; /s.locateelem(p); if(s.locateelem(p) s.findparent(p); s.findchild(p); coutreply; coutendl; return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -