本文是數據結構基礎系列(6)：樹和2叉樹中第11課時2叉樹遍歷非遞歸算法和第12課時層次遍歷算法的例程。
問題：設計算法輸出從根節點到每一個葉子節點的路徑之逆。
解法1：利用2叉樹后序遍歷非遞歸算法中，每個葉子節點出現時，棧中從棧頂到棧底，正好是葉子節點到根節點的逆序的性質編寫。
［參考解答］（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
",St[0]->data);
}
top--;
p=b; //p指向剛訪問過的節點
}
else
{
b=b->rchild; //b指向右孩子節點
flag=0;
}
}
}
while (top!=-1);
printf("
");
}
}
int main()
{
BTNode *b;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("2叉樹b: ");
DispBTNode(b);
printf("
");
printf("從根節點到每一個葉子節點的路徑之逆:
");
AllPath1(b);
DestroyBTNode(b);
return 0;
}解法2：利用2叉樹層次遍歷算法的思路解決。
［參考解答］（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
",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("2叉樹b: ");
DispBTNode(b);
printf("
");
printf("從根節點到每一個葉子節點的路徑之逆:
");
AllPath2(b);
DestroyBTNode(b);
return 0;
}注：在main函數中，創建的用于測試的2叉樹以下――
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
