求二叉树根到给定节点的路径设计报告(内容清晰)

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

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

3、 i栈中元素依次输出程序运行结束第四章 界面设计：图 1 程序运行开始界面 PAGE 6甲类研制#图 2 创建二叉树的界面 PAGE 7甲类研制#是供参考图 3 输出顺序存储的二叉树的界面夏忒C: Progra. Fil es 夏i cr os of t Visual Studi o y Pr o j ects d De ，目回Ei111245尸入要查找的结点：G良节点到G的路往：A-E-E-GPress any key to continue0C,BH-lO1?.3456?脆C0 D1 E1 F2 G4 H5以下就是节点数8 的二叉村A-1-开始箱入-D/天天天巨日 PAGE 13甲类研制#

4、图 4 求到给定节点路径的界面第五章 核心算法及说明：我们利用二叉树的双亲存储表示法建立二叉树，然后在树的叶子节点中找到给定的节点， 利用双亲指针找出该节点所有祖先并入栈，直至根节点，然后再让栈中元素依次出栈， 得到二叉树到该节点的路径定义数据类型struct PTNode/定义树的节点类型char data;/节点数据int parent;/双亲指针;typedef struct/定义树结构struct PTNode nodes100;/定义存放节点的数组int r,n;/根的位置与节点数PTree;创建二叉树void CreatPTree(PTree *PT)/采用双亲表存储构建树cout

5、请输入二叉树根节点的位置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+)/输出顺序存储的二叉树coutinodesi.datanodesi.parentendl;求根节点到给定节点的路径void path(PTree *PT , char e)/求根节点到给定节点的路径int s100,top=-1;/建栈for(int

6、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第六章 结论、运行结果：算法分析：经过不断的上机调试,源程序运行正确,实现了用双亲表示存储的方法创建二叉树并通过 path()函数实现了求根节点到给定节点路径的功能并且实现算法要求的功能,程序中二叉树有 n 个节点，因此创建树所用时间为O(n)，实现根

7、节点到指定节点的路径问题时所用时间为O（n*n）所以算法的时间复杂度为O（n*n）.第七章 后记：1、通过本设计实验将数据结构中的二叉树和栈的知识复习到，并且能够自己设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。2、在试验中遇到了很多的问题，都是以前没有发现的，这些问题设计的方面很多，有以前的 C+基础的，也有最近学习的数据结构的知识。通过实验的设计，让我发现了自己的不足。自己在学习知识上面的漏洞。自己在细节方面的考虑还不够全面，很多细节都是通过调试才发现的，希望通过弥补这些发现的漏洞，提高自己的专业知识水平。第八章 附录：#include #include

8、#include #define MAXSIZE 100;struct PTNode/定义树节点类型char data;/节点数据int parent;/双亲指针;typedef struct/定义树结构struct PTNode nodes100;/定义存放节点的数组int r,n;/根的位置与节点数PTree;void CreatPTree(PTree *PT)/采用双亲表示存储法构建树cout请输入二叉树根节点的位置r 和节点数n：n ; coutPT-r;coutPT-n;char d; int p;cout /*请输入节点和双亲指针n; cout /*格式如下：n;cout /* A

9、-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+)coutinodesi.datanodesi.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;Crea