二叉树的遍历与求结点路径

课程设计项目研究报告目录TOC\o"1-5"\h\z摘要11、弓I言21.1课题设计背景・21.2课题设计的目的和意义21.3课题的内容22、课程设计计划表32.1人员分配表32.2课程设计完成进度表・33、总体设计43.1课程设计的方案设计论证・43.2主要数据存储结构设计43.3模块的划分及功能描述・44、程序设计54.1程序流程图54.2重要函数•64.3程序详细分析75、源程序166、程序运行及结果216.1程序运行环境216.2运行结果217、课程设计心得体会248、参考文献24摘要《数据结构》是一种基于C程序建立的一种专业的算法技术，是一门基础的结构知识，是为了解决抽象问题设计的一种数学模型的算法，然后进行运行调试，以达到目的。这是一门基础课，在日常生活、学习中，运用的范围非常广泛，这要求我们能够掌握并应用。本次课程设计目的在于检验学生在《数据结构》课程一学期中的学习成果，从而加深学生对所学知识的进一步理解与巩固。本次课程设计过程中我们主要根据课本中的实现思想及算法编写程序，体现以课本知识的应用为主，在学习了线性表、栈、队列、二叉树、树和图等结构的基础上，以能够更加熟练的应用所学知识，并能更为深刻理解数据结构的内涵，熟悉它们各自的应用场合及方法。有些在平时做实验报告中没有掌握的内容在这次课程设计中都是先通过看课本学懂了，然后再在课程设计中加深印象，实现算法的应用和扩展。这次的课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。我们主要做了建立二叉树以及对二叉树的遍历与求结点路径这个课题。本文利用C语言编写程序，分别实现了先序建立二叉树的存储结构以及对二叉树的先序遍历、中序遍历、后序遍历以及对指定结点路径的输出。树结构的应用主要模块：建立二叉树、对二叉树的不同方法进行遍历、求指定结点路径等，以及对指针数组的应用为基础对树结构的操作和应用。几个功能模块已经通过全面的测试，能够很好的运行，达到了预期的效果。关键字：数据结构二叉树遍历结点路径引言1.1课题设计背景《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐•欧•克努特教授开创了数据结构的最初体系，目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。《数据结构》在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论数据结构，已成为一种新的趋势，越来越被人们所重视。在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续结点数可以是一个也可以是多个。课题设计的目的和意义树形结构是一类很重要的非线性数据结构，树中结点之间具有明确的层次关系，并且结点之间有分支，它非常类似于实际的树。树形结构在客观世界中大量存在，如行政组织机构和人类社会的家谱关系等都可用树形结构形象地表示。在计算机应用领域，树结构也被广泛地应用。例如在编译程序中，用树结构来表示源程序的语法结构；在数据库系统中，用树结构来表示组织信息；在计算机图形学中，用数结构来表示图像关系等。课题设计的内容利用一个简单的菜单，通过菜单项进行选择，实现和完成如下功能：建立二叉树存储结构、求二叉树的前序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求指定结点的路径。

课程设计计划表2.1人员分配表指导老师：分组成员安排成员座号项目内容序号20号1、先序遍历程序模块以及分析2、界面设计程序模块3、Word相关排版0115号1、求结点路径程序模块以及分析2、查找函数3、结构功能模块描述0221号1、创建二叉树存储结构2、中序遍历程序模块以及分析3、调试程序0313号1、后序遍历模块以及分析2、画程序流程图3、心得体会04课程设计完成进度表日期完成的工作2011.01.15整体规划，合理分配任务项目2011.01.16设计并划分模块，并设计流程图2011.01.17子模块程序设计，并调试2011.01.18系统整合程序模块，并调试2011.01.19综合分析源程序，并调试成功2011.01.20完成课程设计，并撰写课程设计报告总体设计3.1课程设计的方案设计论证本设计中，在二叉树的上无论采用哪种遍历方法，都能够访问完二叉树中的所有结点。但是考虑到时间复杂度以及空间复杂度，由于非递归遍历二叉树的时间复杂度和空间复杂度都复杂于递归遍历二叉树，因此我们采用递归遍历二叉树，其时间复杂度最小为O（），无需采用复杂的入栈出栈等。而对于求结点的路（n），径，考虑到栈和队列的存储结构比较繁琐，从而定义一指针数组来一一存储该二叉树先序遍历过的结点，并对该结点进行判断是否为指定的目标结点，并进行输出等操作，此方法操作简单，容易理解。主要数据存储结构设计本设计中，对二叉树采用链式存储结构，其结构定义如下：typedefstructnode{datatypedata;structnode*lchild,*rchild;}bintnode;每个结点中设置三个域，即值域data,左指针域*lchild和右指针域*rchild。模块的划分及功能描述本程序分为7大模块：全局变量定义、创建结构体、创建二叉链表存储表示对二叉树三种不同的遍历、查找目标结点、求结点路径、主函数。（1）全局变量定义（2）创建结构体（3）创建二叉链表存储表示：定义二叉树的链式存储结构,输入数据生成二叉树。（4）二叉树三种不同的遍历：先序遍历：采用二叉链表作为存储结构先序遍历，先访问根结点，再依次访问左右子树。中序遍历：采用二叉链表作为存储结构中序遍历，先访问左子树，再访问根结点，最后访问右子树。C.后序遍历：采用二叉链表作为存储结构后序遍历，先访问左右子树，再访问根结点。（5）查找目标结点：采用二叉链表作为存储结构，利用后序遍历二叉树方法，对各个结点进行判断改结点是否在二叉树中。（6）求结点路径：采用二叉链表作为存储结构，利用先序遍历二叉树方法以及指针数组的存储结构方法，对结点路径的遍历查找及输出。（7）主函数核心算法的设计；二叉树是n个结点的有穷个集合，它或者是空集（n=0）,或者同时满足以下两个条件；（1）：有且仅有一个称为根的结点；（2）：其余结点分为两个互不相交的集合T],T2，并且T]，T2，都是二叉树，分别称为根的左子树和右子树。程序设计4.1程序流程图（1）主程流程图主函数f建立二叉树「卩11Jf1r先序遍历中序遍历后序遍历査找/判断结点求结点路径<丿1JX.丿

(2)可控界面流程图:(2)可控界面流程图:4.2重要函数主函数voidmain（）输入函数scanf（）输出函数printf（）二叉树的先序建立函数createbintree（）二叉树的先序遍历函数preorder（）二叉树的中序遍历函数inorder（）二叉树的后序遍历函数postorder（）结点查找函数findx（）求结点路径函数nodepath（）4.3程序详细分析定义二叉树用链式存储结构存储二叉树。其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过100个，把bintree构造成bintnode类型。具体实现方法如下：typedefchardatatype;typedefstructnode{/******构造数据结构*********/datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;建立二叉树创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中“#”表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树T,“#”符号表示空树。具体实现方法如下：voidcreatebintree(bintree*bt)/***先序创建二叉树***/{charch;fflush(stdin);if((ch=getchar())=='#')*bt=NULL;/***连续读取输入的字符***/else{*bt=(bintree)malloc(sizeof(bintnode));(*bt)->data=ch;createbintree(&((*bt)->lchild));createbintree(&((*bt)->rchild));}递归先序遍历二叉树：函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。算法思想：若二叉树为空，则结束遍历操作；否则访问根结点；数据元素调用函数visit()；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下：voidVisit(charch)/***在遍历时输出遍历的路径(遍历输出函数)***/{printf("%c",ch);}voidpreorder(bintreeroot)/***先序遍历二叉树***/{if(root!=NULL){Visit(root->data);preorder(root->lchild);preorder(root->rchild);}}递归中序遍历二叉树：函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。算法思想：若二叉树为空，则结束遍历操作；否则中序遍历根的左子树；数据元素调用函数visit()；访问根结点；中序遍历根的右子树。具体实现方法如下：voidVisit(charch)/***在遍历时输出遍历的路径(遍历输出函数)***/{printf("%c",ch);}voidinorder(bintreeroot)/***中序遍历二叉树***/{if(root!=NULL){inorder(root->lchild);Visit(root->data);inorder(root->rchild);}}递归后序遍历二叉树：函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。算法思想：若二叉树为空，则结束遍历操作；否则后序遍历根的左子树；后序遍历根的右子树；数据元素调用函数Visit()；访问根结点。具体实现方法如下：voidVisit(charch)/***在遍历时输出遍历的路径(遍历输出函数)***/{printf("%c",ch);}voidpostorder(bintreeroot)/***后序遍历二叉树***/{if(root!=NULL){postorder(root->lchild);postorder(root->rchild);Visit(root->data);}}6)查找函数函数功能是用递归方法对二叉树进行先序遍历查找，调用此函数可以返回二叉树中指定目标结点。算法思想：若找到目标结点，则返回该目标结点；否则访问二叉树的根结点；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下：voidfindbt(bintreebt,datatypex)/*递归查找目标结点x*/{if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;/*找到目标结点，令found=1，跳出递归查找函数*/}else{findbt(bt->lchild,x);findbt(bt->rchild,x);}}}bintnode*findx(bintreebt,datatypex)/*调用findbt函数，以指针类型返回p*/{found=0;p=NULL;findbt(bt,x);return(p);}7）求指定结点路径：该函数功能是根据已创建的二叉树和输入的目标结点，调用此函数可以查找并输出目标结点的路径。算法思想：根据先序遍历二叉树的递归定义，采用一个指针数组来保存返回的结点。先扫描根结点的左子树上的结点并写入指针数组。判断该结点是否与指定目标结点相等，若不相等，然后扫描该结点的右结点并写入指针数组，再扫描该右结点的所有左结点写入指针数组。当一个结点的左孩子树均访问完后再访问该结点，并与给定的结点比较。若相等，则循环输出指针数组中的所有元素，而这个顺序值就是要求的路径。若不相等，则继续上述过程。具体实现方法如下：voidnodepath（bintreebt,bintnode*ch）/***在二叉树中查找目标结点，并输出目标结点的路劲***/{typedefenum{FALSE,TRUE}boolean;bintnode*stack[num];/*****定义指针数组*****/inttag[num];/*****标志数组*****/inti,top;booleanfind;bintnode*s;find=FALSE;top=0;s=bt;do{while（s!=NULL）/***只要s不为空，把s以及s的左孩子（递归）写入stack[top]***/{top++;stack[top]=s;/**用来存储标记查找目标数据时走过的路径（结点）**/tag[top]=0;/***第top个的结点为左孩子，记tag[top]为0***/s=s->lchild;}if(top>0)/***s不为空，即有写入数组，数组不为空***/{s=stack[top];/*s为最后的左孩子(其孩子结点没有左孩子了)*/if(tag[top]==1){if(s==ch){for(i=1;i<=top;i++)printf("->%c",stack[i]->data);/***找到与输入相符的目标数据，即输出路径***/find=TRUE;}elsetop--;/*没有找到相符的数据，即删除该结点，把结点往上移*/s=stack[top];}if(top>0&&!find){if(tag[top]!=1){s=s->rchild;/****最后一个的左结点没有左孩子了，开始往右查找目标结点，第top个结点为右孩子记为1***/tag[top]=1;}elses=NULL;}

}while(!find&&top!=0);/***当查找该二叉树时有找到目标结点或都查找完该二叉树没有找到目标结点，则退出循环***/}(8)主函数：该函数为程序的主函数功能是循环输出菜单，功能界面；从界面获取功能菜单中对应的字符，通过switch()语句实现对函数的调用，进而实现功能。具体代码如下：/*****主函数*****/voidmain()/*****主函数*****/{bintree*bt;intxz=1;charch1;printf("\t**********************************************************\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t*\t\tWELCOMCOMEHERE\t\t*\n");printf("\t*KindlyReminder:Firstyoushouldcreateabinarytree!*\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\twhile(xz){/*****输出菜单,功能*****/printf("\nAbinarytreetraverseandbegnodepath!\n");printf("================================================\n");printf("1.Createabinarytreestorageprintf("structure!\n");printf("traverse!\n");printf("2.Forbinarytree'spreorderto3.Forbinarytreeinordertotraverse!\n");printf("4.Forbinarytreepostordertotraverse!\n");printf("5.Foraspecifiednodepath!\n");printf("0.ExitSystem!\n");printf("================================================\n");printf("Pleasechooseastraw:(0-5)\n");scanf("%d",&xz);/*****通过switch语句选择相应的方法实现相应的功能*****/switch(xz){case1:printf("Inputsomevalueofbinarytreenode:\n");createbintree(&bt);printf("Abinarytreechainstructureestablishcomplete!\n\n");break;case2:printf("Abinarytreepreordertotraversis:\n");preorder(bt);printf("\n");break;case3:printf("Abinarytreeinordertotraversis:\n");inorder(bt);printf("\n");break;case4:printf("Abinarytreepostordertotraversis:\n");postorder(bt);printf("\n");break;case5:printf("pleaseinputanode:\n");ch1=getchar();ch1=getchar();findx(bt,ch1);if(p!=NULL){printf("thenode'spathis:\n");nodepath(bt,p);printf("\n");}else/*当输入的目标结点不存在，输出错误提示*/printf("!ERROR!\nthenodeisunfound!\n");break;/***当输入的字符不与菜单的功能对应，提示错误，返回菜单界面**/default:printf("thecommandisunfound!tryagain!\n");}}}源程序#include<stdio.h>#include<stdlib.h>#definenum100typedefchardatatype;typedefstructnode{/******构造结构体*********/datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;intfound;bintnode*p;voidcreatebintree(bintree*bt)/*****先序创建二叉树******/{charch;fflush(stdin);if((ch=getchar())=='#')*bt=NULL;/*****连续读取输入的字符*****/else{*bt=(bintree)malloc(sizeof(bintnode));(*bt)->data=ch;createbintree(&((*bt)->lchild));createbintree(&((*bt)->rchild));}}voidVisit(charch)/***在遍历时输出遍历的路径(遍历输出函数)***/{printf("%c",ch);}voidpreorder(bintreeroot)/***先序遍历二叉树***/{if(root!=NULL){Visit(root->data);preorder(root->lchild);preorder(root->rchild);}}

/***中序遍历二叉树***//***后序遍历二叉树***/voidinorder(bintreeroot)/***中序遍历二叉树***//***后序遍历二叉树***/{if(root!=NULL){inorder(root->lchild);Visit(root->data);inorder(root->rchild);}}voidpostorder(bintreeroot){if(root!=NULL){postorder(root->lchild);postorder(root->rchild);Visit(root->data);}}voidfindbt(bintreebt,datatypex)/***递归查找目标结点x***/{if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;/***找到目标结点，令found=l,跳出递归查找函数***/}else{findbt(bt->lchild,x);findbt(bt->rchild,x);}}}bintnode*findx(bintreebt,datatypex)/*****调用findbt函数，以扌旨针类型返回p*****/{found=0;p=NULL;findbt(bt,x);return(p);

/*****在二叉树中查找目标结点，/*****定义指针数组*****//*****标志数组*****/void/*****在二叉树中查找目标结点，/*****定义指针数组*****//*****标志数组*****/并输出目标节结点的路径*****/{typedefenum{FALSE,TRUE}boolean;bintnode*stack[num];inttag[num];inti,top;booleanfind;bintnode*s;find=FALSE;top=0;s=bt;do{while（s!二NULL）/*只要s不为空，把s以及s的左孩子（递归）写入stack[top]*/{top++;stack[top]=s;/***用来存储标记查找目标数据时走过的路径（结点）***/tag[top]=0;/***第top个的结点为左孩子，记tag[top]为***/s=s->lchild;}if(top>0){s=stack[top];/***s不为空，即有写入数组，数组不为空***//***s为最后的左孩子（其孩子结点没有左孩子了）***/if(tag[top]==1){if(s==ch)for(i=1;i<=top;i++)printf("->%c",stack[i]->data);/******找到与输入相符的目标数据，即输出路径******/find=TRUE;}elsetop--;/**没有找到相符的数据，即删除该结点，把结点往上移**/s=stack[top];}if（top>0&&!find）{if（tag[top]!=1）{s=s->rchild;/***最后一个的左结点没有左孩子了，开始往右

查找目标结点，第top个结点为右孩子记为***/tag[top]=1;}elses=NULL;}}}while(!find&&top!=0);/***当查找该二叉树书时有找到目标结点或都查找完该二叉树没有找到目标结点，则退出循环***/}/*****主函数*****/voidmain()/*****主函数*****/{bintree*bt;intxz=1;charch1;printf("\t**********************************************************\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t*\t\tWELCOMCOMEHEARE\t\t*\n");printf("\t*KindlyReminder:Firstyoushouldcreateabinarytree!*\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t**********************************************************\n");while(xz){while(xz){/*****输出菜单*****/printf("\nAbinarytreetraverseandbegnodepath!\n");printf("================================================\n");printf("1.Createabinarytreestoragestructure!\n");printf("2.Forbinarytree'spreordertotraverse!\n");printf("3.Forbinarytreeinordertotraverse!\n");printf("4.Forbinarytreepostordertotraverse!\n");printf("5.Foraspecifiednodepath!\n");printf("0.ExitSystem!\n");printf("================================================\n");printf("Pleasechooseastraw:(0-5)\n");scanf("%d",&xz);switch(xz){/***通过switch语句选择相应的方法实现相应的功能***/case1:printf("Inputsomevalueofbinarytreenode:\n");createbintree(&bt);printf("Abinarytreechainstructureestablishcomplete!\n\n");break;case2:printf("Abinarytreepreordertotraversis:\n");preorder(bt);printf("\n");break;case3:printf("Abinarytreeinordertotraversis:\n");inorder(bt);printf("\n");break;case4:printf("Abinarytreepostordertotraversis:\n");postorder(bt);printf("\n");break;case5:printf("pleaseinputanode:\n");ch1=getchar();ch1=getchar();findx(bt,ch1);if(p!=NULL){printf("thenode'spathis:\n");nodepath(bt,p);printf("\n");}elseprintf("!ERROR!\nthenodeisunfound!\n");break;default:printf("thecommandisunfound!tryagain!\n");/*****当输入的字符不与菜单的功能对应，提示错误，返回菜单界面*****/}}}

程序运行及结果6.1程序运行环境个人PC机；windowsxp系统；win-tc编程软件。6.2运行结果(1)输入元素数据：ABC##DE#G##F###运行结果为：Abinarytreechainstructureestablishcomplete!Abinarytreechainstructureestablishcomplete?Abinarytreetraverseandbegnodepath?Createabinarytreestoragestructure?Forbin日厂vtree!spreordertotraverse?Forbin日厂vtreeino厂de厂totraverse?Forbinarytreepostordertotraverse?Foraspecifiednodepath?0.ExitSystem