【路徑問題】

問題描述：采用先序遍歷方法輸出所有從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的逆路徑。

二叉樹 b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

先序遍歷方法:

D 到根結(jié)點(diǎn)逆路徑: D->B->A

J 到根結(jié)點(diǎn)逆路徑: J->H->E->B->A

L 到根結(jié)點(diǎn)逆路徑: L->K->H->E->B->A

N 到根結(jié)點(diǎn)逆路徑: N->M->K->H->E->B->A
F 到根結(jié)點(diǎn)逆路徑: F->C->A

I 到根結(jié)點(diǎn)逆路徑: I->G->C->A

第一條最長逆路徑長度:7

第一條最長逆路徑:N M K H E B A

dfs和bfs都可以輸出路徑，但是二者也有所不同。bfs主要是隊(duì)列，先進(jìn)先出。而dfs則可以回來，用一個數(shù)組存儲就可以了。寫這個題目的時候，我想到了深搜的入門題，素?cái)?shù)環(huán)。。可以來參考一下
代碼如下：

#include<bits/stdc++.h> using namespace std;typedef struct node{char data;struct node *lchild;struct node *rchild;int vis; } *Bitree;void creatree(Bitree &t) {char c;cin>>c;if(c=='#') t=NULL;else{t=(node *)malloc(sizeof(node));t->data=c;t->vis=0;creatree(t->lchild);creatree(t->rchild);} }char s[1010]; char s1[1010]; int cnt=0; int maxx=-1;void dfs(Bitree &t) {if(t!=NULL){s[cnt++]=t->data;if(t->lchild==NULL&&t->rchild==NULL){printf("從%c到%c的路徑為:\n",s[cnt-1],s[0]);for(int i=cnt-1;i>=0;i--){cout<<s[i];if(i) cout<<"->";}if(maxx<cnt){maxx=cnt;strcpy(s1,s);}cnt--;//cnt為全局變量，在這里需要減一。cout<<endl;return ;}dfs(t->lchild);dfs(t->rchild);cnt--;//當(dāng)一個節(jié)點(diǎn)以下的走完了以后，就cnt--，去找尋上面的節(jié)點(diǎn)、} }int main() {Bitree t;creatree(t); dfs(t);cout<<"第一條最長逆路徑長度:"<<maxx<<endl;for(int i=maxx-1;i>=0;i--) cout<<s1[i]<<" "; } //ABD##EHJ##KL##M#N###CF##G#I##

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的二叉树的操作4的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。