数据结构例程——从根节点到每个叶子节点的路径之逆

本文主要是介绍数据结构例程——从根节点到每个叶子节点的路径之逆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文是数据结构基础系列(6)：树和二叉树中第11课时二叉树遍历非递归算法和第12课时层次遍历算法的例程。

问题：设计算法输出从根节点到每个叶子节点的路径之逆。
解法1：利用二叉树后序遍历非递归算法中，每一个叶子节点出现时，栈中从栈顶到栈底，正好是叶子节点到根节点的逆序的性质编写。

［参考解答］（btreee.h见算法库）

#include <stdio.h>
#include "btree.h"void 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：利用二叉树层次遍历算法的思路解决。

采用非环形顺序队列qu
层次遍历二叉树
将所有已访问过的节点指针进队，并在队列中保存双亲节点的位置。
当找到一个叶子节点时，在队列中通过双亲节点的位置输出根节点到该叶子节点的路径之逆。

［参考解答］（btreee.h见算法库）

#include <stdio.h>
#include "btree.h"void 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;
}