1、课程设计任务书课程设计任务书 学 院 信息学院 专 业 计算机科学与技术 学 生 姓 名 学 号 题 目 求二叉树根结点到指定结点的路径 内容及要求：内容及要求： 设计内容： 按先序遍历的次序输入二叉树的各个结点，并输出根节点到指定结点的路径，分别建 立二叉树存储结构的输入函数以及输出指定结点路径的函数，求二叉树的指定结点路 径。 要求： (1)定义二叉树的存储结构，采用先序序列递归建立二叉树，每个结点中设置三个 域，即值域、左指针域、右指针域。要建立二叉树的链式存储结构，即建立二叉链表。 (2)采用先序序列递归建立二叉树,要求在程序运行窗口中提示信息输入要求路径 的结点值，并输出根结点到指定
2、结点路径。 函数接口说明: Status CreateBiTree(BinTree typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; 函数调用关系如下图所示： 函数接口说明: Status CreateBiTree(BinTree typedef char DataType; typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; int found; BinTNode
3、*p; Status CreateBiTree(BinTree printf(“ch=“); scanf(“%c“, getchar(); if (ch=) bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; /生成根结点 CreateBiTree(bt-lchild); /构造左子树 CreateBiTree(bt-rchild); /构造右子树 return OK; void NodePath(BinTree bt,BinTNode *ch) /求二叉树根结点到给定结点*p 的路径 typedef enum F
4、ALSE,TRUEboolean; BinTNode *stacknum; /定义栈 int tagnum; int i,top; boolean find; BinTNode *s; find=FALSE; top=0; s=bt; do while(s!=NULL) /扫描左子树 stacktop=s; tagtop=0; s=s-lchild; if(top0) s=stacktop; if(tagtop=1) if(s=ch) /找到 ch,则显示从根结点到 ch的路径 for(i=1;i%c“,stacki-data); find=TRUE; else top-; s=stackto
5、p; /endif if(top0 /扫描右子树 tagtop=1; else s=NULL; /endif /endlif while(!find void FindBT(BinTree bt,DataType x) if(bt!=NULL) found=1; else FindBT(bt-lchild,x); /遍历查找左子树 FindBT(bt-rchild,x); /遍历查找右子树 BinTNode *Findx(BinTree bt,DataType x) /按给定值查找结点 int found=0; /用 found 来作为是否查找到的标志 BinTree p=NULL; /置空指
6、针 FindBT(bt,x); return(p); void main() BinTree bt; char ch1; int xz=1; while(xz) printf(“建立二叉树并求指定结点路径n“); printf(“ 欢 迎 光 临n“); printf(“=n“); printf(“1.建立二叉树的存储结构 n“); printf(“n“); printf(“2.求二叉树指定结点的路径 n“); printf(“n“); printf(“0. 退 出 系 统 n“); printf(“=n“); printf(“请选择:(0-2) n“); scanf(“%d“, getchar(); switch(xz) /输入:
