打印二叉树(二叉链表表示)的所有叶子结点到根结点的路径.doc

一 课题内容和要求:课题内容：打印二叉树（二叉链表表示）的所有叶子结点到根结点的路径。课题要求：要求掌握二叉树链式存储的类型定义及实现。要求掌握二叉树链式存储的各类基本运算方法要求掌握二叉树用不同方法标识所对应的不同输入形式。要求掌握二叉树中各个重要性质在解决实际问题中的应用。要求掌握二叉树的分析方法，解决方法，从而提高实际编程能力及程序调试能力等。二、设计思路分析:1) 创建一棵二叉树：使用void CreateBiTNode(BiTNode *&b)函数，设置最大容量Maxsize，输入一个格式为A(B,C)的二叉树，设置#为结束符，当ch0=#，停止读入。2) 对top变量递归，求出根节点到叶子节点的路径。三、概要设计：1.创建结构体：typedef struct node BiTNode;2.创建二叉树：void CreateBiTNode(BiTNode *&b)创建一个以格式为A(B,C)的二叉树，以“#”结束的二叉树3.按照格式读入二叉树：void DispBiTNode(BiTNode *b)4.输出路径：void Path（BiTNode *b,ElemType path,int pathlen）四、详细设计：#include #include #include #define MaxSize 100typedef char ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BiTNode;void CreateBiTNode(BiTNode *&b);void DispBiTNode(BiTNode *b);void Path(BiTNode *b,ElemType path,int pathlen);void main() BiTNode*b; ElemType pathMaxSize; int i=0; CreateBiTNode(b); printf(二叉树b:); DispBiTNode(b); printf(n); Path(b,path,0);void CreateBiTNode(BiTNode *&b)/创建二叉树BiTNode *StMaxSize,*p=NULL;int top=-1,k,j=0,a;char ch0,ch;char strMaxSize;b=NULL; printf(请输入一个格式为A(B,C)的二叉树：n以#结束n);ch0=getchar();for(a=0;ch0!=#;a+) stra=ch0; ch0=getchar();ch=strj;while(ch!=#) switch(ch) case(:top+;Sttop=p;k=1;break; case):top-;break; case,:k=2;break; default:p=(BiTNode *)malloc(sizeof(BiTNode); p-data=ch;p-lchild=p-rchild=NULL; if(b=NULL) b=p; else switch(k) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+; ch=strj;void DispBiTNode(BiTNode *b)if(b!=NULL) printf(%c,b-data);if (b-lchild!=NULL|b-rchild!=NULL) printf();DispBiTNode(b-lchild);if (b-rchild!=NULL)printf(,);DispBiTNode(b-rchild);printf();void Path(BiTNode *b,ElemType path,int pathlen) int i; if (b!=NULL) if(b-lchild=NULL&b-rchild=NULL) printf(%c到根结点路径:%c,b-data,b-data); for(i=pathlen-1;i=0;i-) printf(%c,pathi); printf(n); else pathpathlen=b-data; pathlen+; Path(b-lchild,path,pathlen); Path(b-rchild,path,pathlen); pathlen-; 五、测试数据及其结果分析/*编译结果：请输入一个格式为A(B,C)的二叉树：以#结束A(B,C(D,E)#二叉树b:A(B,C(D,E)B到根结点路径:BAD到根结点路径:DCAE到根结点路径:ECAPress any key to continue*/六、调试过程中的问题：在调试的过程中，对于输入的方式上有好几种设计，最后决定用括号和“，”结合来读入数据。七、专业课程设计总结：这道题考查对二叉树遍历方式的理解。如果把二叉树看成图，就是图的深度遍历。使用变量存放当前遍历的路径和，当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要