求二叉树根到给定节点的路径设计报告

1、题目：求二叉树根到给定节点的路径摘要：本程序设计题要求出二叉树的根节点到给定节点的路径，我们利用二叉树的双亲存储表示法建立二叉树，然后在树的叶子节点中找到给定的节点，利用双亲指针找出该节点所有祖先并入栈，直至根节点，然后再让栈中元素依次出栈，得到二叉树到该节点的路径，使程序得以实现。关键字：二叉树 双亲指针 栈 路径 目 录1、题目要求-42、设计思想-43、系统完成功能及框图-44、界面设计-65、核心算法及说明-86、结论-107、后记-118、附录-11第一章 题目要求：在采用顺序表存储结构存储的二叉树上，以bt指向根接点，p指向任一给定的接点，编程实现求出从根接点到给定接点之间的路径。

2、第二章 设计思想：首先输入要查找的二叉树的各个节点和双亲指针，采用双亲表示法存储结构创建一棵二叉树，然后通过path()函数在树中找到要查找的节点，再利用树的双亲指针逐层向上找到该节点的所有祖先，让其进栈，最后依次输出栈中的节点数据即为二叉树根到给定节点的路径。第三章 系统完成功能及框图：3.1系统完成功能：系统功能包括创建二叉树和求二叉树根结点到给定结点的路径两部分。3.2功能框图：3.2.1整体框图：求二叉树根到给定节点的路径构建二叉树求根节点到给定节点的路径3.2.2求路径算法的流程图：进入程序输入节点位置r和节点数n判断i的值是否为e输入节点和双亲指针创建二叉树i进栈s+top=i否是

3、双亲指针赋给i栈中元素依次输出程序运行结束第四章 界面设计：图1 程序运行开始界面图2 创建二叉树的界面图3 输出顺序存储的二叉树的界面图4 求到给定节点路径的界面第五章 核心算法及说明：我们利用二叉树的双亲存储表示法建立二叉树，然后在树的叶子节点中找到给定的节点，利用双亲指针找出该节点所有祖先并入栈，直至根节点，然后再让栈中元素依次出栈，得到二叉树到该节点的路径5.1 定义数据类型struct ptnode /定义树的节点类型 char data; /节点数据int parent; /双亲指针 ; typedef struct /定义树结构struct ptnode nodes100; /定

4、义存放节点的数组int r,n; /根的位置与节点数ptree;5.2 创建二叉树void creatptree(ptree *pt) /采用双亲表存储构建树 cout 请输入二叉树根节点的位置r和节点数n：n ;coutpt-r;coutpt-n;char d;int p;cout /*请输入节点和双亲指针n;for(int i=0;in;i+) cindp; pt-nodesi.data=d; pt-nodesi.parent=p;cout 以下就是节点数是n的二叉树endl;for(i=0;in;i+) /输出顺序存储的二叉树couti nodesi.data nodesi.parent

5、endl; 5.3 求根节点到给定节点的路径void path(ptree *pt , char e) /求根节点到给定节点的路径 int s100,top=-1; /建栈 for(int i=0;in;i+) /找到给定节点并且祖先依次进栈 if(pt-nodesi.data=e)break; while(i!=pt-r) s+top=i; i=pt-nodesi.parent; s+top=i; cout根节点到e0;-top) /从根节点到给定结点依次输出coutnodesstop.data;coutnodesstop.datan;/path第六章 结论6.1、运行结果：6.2 算法分析

6、：经过不断的上机调试,源程序运行正确,实现了用双亲表示存储的方法创建二叉树并通过path()函数实现了求根节点到给定节点路径的功能并且实现算法要求的功能,程序中二叉树有n个节点，因此创建树所用时间为o(n)，实现根节点到指定节点的路径问题时所用时间为o（n*n）所以算法的时间复杂度为o（n*n）.第七章 后记：1、通过本设计实验将数据结构中的二叉树和栈的知识复习到，并且能够自己设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。 2、在试验中遇到了很多的问题，都是以前没有发现的，这些问题设计的方面很多，有以前的c+基础的，也有最近学习的数据结构的知识。通过实验的设计

7、，让我发现了自己的不足。自己在学习知识上面的漏洞。自己在细节方面的考虑还不够全面，很多细节都是通过调试才发现的，希望通过弥补这些发现的漏洞，提高自己的专业知识水平。 第八章 附录：#include #include #include #define maxsize 100;struct ptnode /定义树节点类型 char data; /节点数据int parent; /双亲指针 ;typedef struct /定义树结构struct ptnode nodes100; /定义存放节点的数组int r,n; /根的位置与节点数ptree;void creatptree(ptree *pt)

8、 /采用双亲表示存储法构建树 cout 请输入二叉树根节点的位置r和节点数n：n ;coutpt-r;coutpt-n;char d;int p;cout /*请输入节点和双亲指针n;cout /*格式如下：n;cout /* a-1endl;cout /* b0endl;cout /* c0endl;cout /* d1endl;cout /* .endl;cout 开始输入endl;for(int i=0;in;i+) cindp; pt-nodesi.data=d; pt-nodesi.parent=p;cout 以下就是节点数是n的二叉树endl;for(i=0;in;i+)couti

9、 nodesi.data nodesi.parentendl; void path(ptree *pt , char e) /求根节点到给定节点的路径 int s20,top=-1; /建栈for(int i=0;in;i+) /找到给定节点并且祖先依次进栈 if(pt-nodesi.data=e) break; while(i!=pt-r) s+top=i; i=pt-nodesi.parent; s+top=i; cout根节点到e0;-top) /从根节点到给定结点依次输出coutnodesstop.data;coutnodesstop.datan;/pathvoid main()cout*求二叉树根到给定节点的路径*endl;cout *先创建一棵二叉树，再求这棵树的一个叶子节点到根的路径* endl;cout *endl;ptree *pt1=new ptree;creatptr