題意：給出一棵字母二叉樹(shù)刪除葉子節(jié)點(diǎn)的序列，按刪除的順序排列。讓你輸出該棵二叉樹(shù)額前序遍歷的序列。
思路：先把一棵樹(shù)的所有刪除的葉子節(jié)點(diǎn)序列存儲(chǔ)下來(lái)，然后從最后一行字符串開(kāi)始建樹(shù)即可，最后遍歷輸出。
??? 這里為方便起見(jiàn)，將子母轉(zhuǎn)化成整數(shù)值存儲(chǔ)。

?

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> /* AC 題意：給出一棵字母二叉樹(shù)刪除葉子節(jié)點(diǎn)的序列，按刪除的順序排列。讓你輸出該棵二叉樹(shù)額前序遍歷的序列。 思路：先把一棵樹(shù)的所有刪除的葉子節(jié)點(diǎn)序列存儲(chǔ)下來(lái)，然后從最后一行字符串開(kāi)始建樹(shù)即可，最后遍歷輸出。這里為方便起見(jiàn)，將子母轉(zhuǎn)化成整數(shù)值存儲(chǔ)。 */ using namespace std; const int maxn=30; char str[30][30];struct node{int l,r; //左兒子的值、右兒子的值。若值為-1，表示不存在左/右兒子。 }node[maxn];void dfs(int u,int v){if(v<u){//當(dāng)u沒(méi)有左兒子時(shí)，v賦值給u的左兒子，否則遞歸u的左兒子if(node[u].l==-1){node[u].l=v;return;}else{dfs(node[u].l,v);}}else{//當(dāng)u沒(méi)有右兒子時(shí)，v賦值給u的右兒子，否則遞歸u的右兒子if(node[u].r==-1){node[u].r=v;return;}else{dfs(node[u].r,v);}} } void dlr_print(int u){if(node[u].l==-1&&node[u].r==-1){printf("%c",u+'A');return;}printf("%c",u+'A');if(node[u].l!=-1)dlr_print(node[u].l);if(node[u].r!=-1)dlr_print(node[u].r); } int main() {int m,u,v;while(scanf("%s",str[0])!=EOF){for(int i=0;i<maxn;i++){node[i].l=node[i].r=-1;}m=1;while(1){scanf("%s",str[m]);if(str[m][0]=='*' || str[m][0]=='$')break;m++;}int rootval=str[m-1][0]-'A'; //根節(jié)點(diǎn)的值。for(int i=m-2;i>=0;i--){for(int j=0;str[i][j]!='\0';j++){v=str[i][j]-'A';dfs(rootval,v);}}//前序遍歷輸出 dlr_print(rootval);printf("\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenxiwenruo/p/3349627.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1577 Falling Leaves (子母二叉树，给出叶子节点的删除序列，求前序遍历)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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