本文是数据结构基础系列(6)：树和二叉树中第11课时二叉树遍历非递归算法和第12课时层次遍历算法的例程。
问题：设计算法输出从根节点到每个叶子节点的路径之逆。 解法1：利用二叉树后序遍历非递归算法中，每一个叶子节点出现时，栈中从栈顶到栈底，正好是叶子节点到根节点的逆序的性质编写。
［参考解答］（btreee.h见算法库）
AllPath1(BTNode *b){BTNode *St[MaxSize];BTNode *p;int flag,i,top=-1; //栈指针置初值if (b!=NULL){do{while (b!=NULL) //将*b的所有左节点进栈{top++;St[top]=b;b=b->lchild;}p=NULL;flag=1;while (top!=-1 && flag){b=St[top];//取出当前的栈顶元素if (b->rchild==p){if (b->lchild==NULL && b->rchild==NULL){//若为叶子节点,输出栈中所有节点值for (i=top; i>0; i–)printf(“%c->”,St[i]->data);printf(“%c\n”,St[0]->data);}top–;p=b;//p指向刚访问过的节点}else{b=b->rchild;//b指向右孩子节点flag=0;}}}while (top!=-1);printf(“\n”);}}int main(){BTNode *b;CreateBTNode(b,”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”);printf(“二叉树b: “);DispBTNode(b);printf(“\n”);printf(“从根节点到每个叶子节点的路径之逆:\n”);AllPath1(b);DestroyBTNode(b);return 0;}
解法2：利用二叉树层次遍历算法的思路解决。
［参考解答］（btreee.h见算法库）
AllPath2(BTNode *b){struct snode{BTNode *node; //存放当前节点指针int parent;//存放双亲节点在队列中的位置} qu[MaxSize];//定义非环形队列BTNode *q;int front,rear,p; //定义队头和队尾指针front=rear=-1;//置队列为空队列rear++;qu[rear].node=b; //根节点指针进入队列qu[rear].parent=-1; //根节点没有双亲节点while (front!=rear) //队列不为空{front++;//front是当前节点*q在qu中的位置q=qu[front].node; //队头出队列,该节点指针仍在qu中if (q->lchild==NULL && q->rchild==NULL){p=front;//输出*q到根节点的路径序列while (qu[p].parent!=-1){printf(“%c->”,qu[p].node->data);p=qu[p].parent;}printf(“%c\n”,qu[p].node->data);}if (q->lchild!=NULL) //*q节点有左孩子时将其进列{rear++;qu[rear].node=q->lchild;qu[rear].parent=front; //*q的双亲位置为front}if (q->rchild!=NULL)//*q节点有右孩子时将其进列{rear++;qu[rear].node=q->rchild;qu[rear].parent=front; //*q的双亲位置为front}}}int main(){BTNode *b;CreateBTNode(b,”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”);printf(“二叉树b: “);DispBTNode(b);printf(“\n”);printf(“从根节点到每个叶子节点的路径之逆:\n”);AllPath2(b);DestroyBTNode(b);return 0;}
注：在main函数中，创建的用于测试的二叉树如下——
，曾经一直想让别人知道自己的心情，那些沉重，
