《数据结构》算法设计问题：假设二叉树采用二叉链存储结构，设计算法输出从根结点到每个叶子结点的路径逆序列。
二叉树从叶节点到根节点的路由可以采用正向扫描、后向扫描、分层扫描等方法。 本算法采用了后序遍历非递归和先序遍历递归的方法。 将程序使用的二叉树的基本运算写入文件btree.h，实现以下功能。
createbtree(Btnode*b，char *str ) :用二叉树括号列创建二叉树存储结构b。 括号表示的形式：根(左边的子树，右边的子树) dispbtree ) Btnode*b ) )二叉树destroybtree ) Btnode*b ) )用括号表示输出：废弃二叉树。
//文件名： btree.h # include stdio.h # include malloc.h # define maxsize 100 typedefcharelemtype； typedef struct node{ElemType data； //数据元素struct node *lchild； //指向左子代的struct node *rchild； //指向右边的子级(} BTNode； voidcreatebtree(Btnode*b，char *str ) { BTNode *St[MaxSize]，*p=NULL； int top=-1，k，j=0； char ch； b=空； //创建的二叉树初始为空ch=str[j]； 威尔(ch！=' ' ()//str未扫描时循环(switch(ch ) case ) ) :ST[top]=p； k=1； 黑； //左节点case ' ) ' :--top； 黑； case '，' :k=2； 黑； //右节点default:p=(Btnode* ) malloc ) sizeof ) Btnode )； p-data=ch； p-lchild=p-rchild=NULL； if(b==null )/p指的是二叉树的根节点b=p； else //二叉树的根节点{switch(k ) { case 1:St[top]-lchild=p； 黑； case 2:St[top]-rchild=p； 黑； } } } ch=str[ j]； }voiddestroybtree(Btnode*b ) ) if ) b！=null(destroybtree(B-lchild ) )； EstroyBtree(B-Rchild )； free(b )； }voiddispbtree(Btnode*b ) /用括号表示输出二叉树(if ) b！=null(printf('%c '，b-data )； if(B-Lchild！=NULL || b-rchild！=NULL () {printf (' ) )； dispbtree(B-lchild； if(B-Rchild！=null(printf )，)； dispbtree(B-rchild； printf () )； } }
#include 'btree.h' //包含二叉树的基本运算算法voidpostorder(Btnode*b )//后行遍历的递归算法) if ) b！=null(postorder(B-lchild ) )； //递归访问左子树Postorder(B-Rchild )//递归访问右子树printf('%c '，b-data )； //访问根节点}}voidpostorder1(Btnode*b ) )//稍后使用非递归算法BTNode *St[MaxSize]； int top=-1； //堆栈指针初始值BTNode *p=b； BTNode *r=NULL； whil
e (p||top>-1) { if(p){ St[++top]=p; p=p->lchild; } else { p=St[top]; //取出当前的栈顶元素 if (p->rchild &&p->rchild!=r) //右子树不存在或已被访问,访问之 { p=p->rchild; St[++top]=p; p=p->lchild; } else //弹出节点并访问 { printf("%c ",St[top]->data); top--; r=p; //r指向则被访问的节点 p=NULL; } } }}void AllPath1(BTNode *b){ //后序遍历非递归算法输出每个叶子结点到根结点的路径序列 BTNode *St[MaxSize]; int top=-1; //栈指针置初值 BTNode *p=b; BTNode *r=NULL; while (p||top>-1) { if(p) //扫描结点p的所有左下结点并进栈 { St[++top]=p; //结点p进栈 p=p->lchild; //移动到左孩子 } else { p=St[top]; //取出当前的栈顶元素 if (p->rchild &&p->rchild!=r) //右子树不存在或已被访问,访问之 { p=p->rchild; St[++top]=p; p=p->lchild; } else //弹出节点并访问 { if (p->lchild==NULL && p->rchild==NULL) //若为叶子 { //输出栈中所有结点值 for (int i=top;i>0;i--) printf("%c->",St[i]->data); printf("%cn",St[0]->data); } top--; r=p; //r指向则被访问的节点 p=NULL; } } } }void Allpath2(BTNode *b,ElemType path[],int pathlen){ //先序遍历方法输出每个叶子结点到根结点的路径序列 if(b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) //b为叶子 { //输出栈中所有结点值 printf("%c->",b->data); for (int i=pathlen-1;i>0;i--) printf("%c->",path[i]); printf("%cn",path[0]); } else { path[pathlen++]=b->data; Allpath2(b->lchild, path, pathlen); Allpath2(b->rchild, path, pathlen); } }} void MaxPath(BTNode *b,ElemType path[],int pathlen,ElemType maxpath[],int &maxpathlen){ //先序遍历方法输出一条最长路径 if(b==NULL)//pathlen和maxpathlen的初值均为0 { if(pathlen>maxpathlen) //通过比较求最长路径 { for(int i=pathlen-1;i>=0;i--) maxpath[i]=path[i]; maxpathlen=pathlen; } } else { path[pathlen]=b->data; //将当前节点放入路径中 pathlen++; //路径长度增1 MaxPath(b->lchild,path,pathlen,maxpath,maxpathlen); //递归扫描左子树 MaxPath(b->rchild,path,pathlen,maxpath,maxpathlen); //递归扫描右子树 }}int main(){ BTNode *b; CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树b:");DispBTree(b);printf("n"); printf("后序遍历序列:n"); printf(" 递归算法:");PostOrder(b);printf("n"); printf(" 非递归算法:");PostOrder1(b);printf("n"); printf("Allpath1:n");AllPath1(b);printf("n"); ElemType path[MaxSize],maxpath[MaxSize]; int maxpathlen =0; printf("Allpath2:n"); Allpath2(b,path,0);printf("Maxpath:n"); MaxPath(b,path,0,maxpath,maxpathlen); for(int i=0;i<maxpathlen-1;i++) printf("%c->",maxpath[i]); printf("%cn",maxpath[maxpathlen-1]); DestroyBTree(b);}执行结果：