目的： 掌握二叉树遍历算法的应用，熟练使用先序、中序、后序3种递归和非递归遍历算法及层次遍历算法进行二叉树问题求解。 功能： （1）采用先序遍历算法方法输出所有从叶子结点高根结点的逆路径； （2）采用先序遍历方法输出第一条最长的逆路径； （3）采用后序非递归遍历方法输出所有从叶子结点到根结点的逆路径； （4）采用层次遍历方法输出所有从叶子结点到根结点的逆路径。 源代码：
#include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTree(BTNode *&b,char *str) { BTNode *St[MaxSize],*p; int top=-1,k,j=0;char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(':top++;St[top]=p;k=1;break; case ')':top--;break; case ',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++;ch=str[j]; } } void DestroyBTree(BTNode *&b) { if(b!=NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p; if(b==NULL) return NULL; else if(b->data==x) return b; else { p=FindNode(b->lchild,x); if(p!=NULL) return p; else return FindNode(b->rchild,x); } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh,rchildh; if(b==NULL)return(0); else { lchildh=BTHeight(b->lchild); rchildh=BTHeight(b->rchild); return (lchildh>rchildh)?(lchildh+1):(rchildh+1); } } void DispBTree(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(")"); } } } void AllPath1(BTNode *b,ElemType path[],int pathlen) { if(b!=NULL) { if(b->lchild==NULL&&b->rchild==NULL) { printf("%c到根结点逆路径：%c->",b->data,b->data); for(int i=pathlen-1;i>0;i--) printf("%c->",path[i]); printf("%c\n",path[0]); } else { path[pathlen]=b->data; pathlen++; AllPath1(b->lchild,path,pathlen); AllPath1(b->rchild,path,pathlen); } } } void LongPath1(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen) { if(b==NULL) { if(pathlen>longpathlen) { for(int i=pathlen-1;i>=0;i--) longpath[i]=path[i]; longpathlen=pathlen; } } else { path[pathlen]=b->data; pathlen++; LongPath1(b->lchild,path,pathlen,longpath,longpathlen); LongPath1(b->rchild,path,pathlen,longpath,longpathlen); } } void AllPath2(BTNode *b) { BTNode *st[MaxSize]; int top=-1; BTNode *p,*r; bool flag; p=b; do { while(p!=NULL) { top++; st[top]=p; p=p->lchild; } r=NULL; flag=true; while(top>=-1&&flag) { p=st[top]; if(p->rchild==r) { if(p->lchild==NULL&&p->rchild==NULL) { printf("%c到根结点逆路径：",p->data); for(int i=top;i>0;i--) printf("%c->",st[i]->data); printf("%c\n",st[0]->data); } top--; r=p; } else { p=p->rchild; flag=false; } } }while(top>-1); } void AllPath3(BTNode *b) { struct snode { BTNode *node; int parent; }Qu[MaxSize]; int front,rear,p; front=rear=-1; rear++; Qu[rear].node=b; Qu[rear].parent=-1; while(front<rear) { front++; b=Qu[front].node; if(b->lchild==NULL&&b->rchild==NULL) { printf("%c到根结点逆路径：",b->data); p=front; while(Qu[p].parent!=-1) { printf("%c->",Qu[p].node->data); p=Qu[p].parent; } printf("%c\n",Qu[p].node->data); } if(b->lchild!=NULL) { rear++; Qu[rear].node=b->lchild; Qu[rear].parent=front; } if(b->rchild!=NULL) { rear++; Qu[rear].node=b->rchild; Qu[rear].parent=front; } } } int main() { BTNode *b; ElemType path[MaxSize],longpath[MaxSize]; int i,longpathlen=0; CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树b：");DispBTree(b);printf("\n"); printf("先序遍历方法：\n");AllPath1(b,path,0); LongPath1(b,path,0,longpath,longpathlen); printf("第一条最长逆路径长度：%d\n",longpathlen); printf("第一条最长逆路径："); for(i=longpathlen-1;i>=0;i--) printf("%c",longpath[i]); printf("\n"); printf("后序非递归遍历方法：\n");AllPath2(b); printf("层次遍历方法：\n");AllPath3(b); DestroyBTree(b); return 1; }备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！
