本系列文章為浙江大學(xué)陳越、何欽銘數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記，系列文章鏈接如下：
數(shù)據(jù)結(jié)構(gòu)(陳越、何欽銘)學(xué)習(xí)筆記
一、題目描述
題目描述： 給定一棵樹，按照從上到下、從左到右的順序列出所有葉結(jié)點。
輸入格式： 每個輸入文件包含一個測試用例。對于每種情況，第一行給出一個正整數(shù)N(≤10)，為樹中的結(jié)點總數(shù)，結(jié)點編號從0到N-1。接著是N行，每一行對應(yīng)一個結(jié)點，并給出該結(jié)點的左、右子結(jié)點的索引。如果子結(jié)點不存在，則在相應(yīng)位置上給出“-”。任何一對子結(jié)點都用一個空格隔開。
輸出格式： 對于每個測試用例，在一行中按從上到下、從左到右的順序打印所有的葉結(jié)點索引。相鄰數(shù)字之間必須有一個空格，行尾不能有多余的空格。
輸入樣例：
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
輸出樣例：
4 1 5
二、整體思路與實現(xiàn)代碼
思路分析
①建樹：讀取各個節(jié)點，存放在一個數(shù)組中，建立一棵樹。
②找到這棵樹的根節(jié)點：把數(shù)組從頭到尾掃描一遍，然后看看有沒有哪個結(jié)點不存在其他結(jié)點指向他。如果沒人指向他，他就是根結(jié)點了，非根結(jié)點肯定有人指向他了。
③層序輸出葉節(jié)點：層序輸出在前面文章已經(jīng)將講解過，首先將根結(jié)點入隊，然后開始執(zhí)行循環(huán)：結(jié)點出隊、訪問該結(jié)點、其左右兒子入隊。在此基礎(chǔ)上，我們加上對節(jié)點屬性的判定，如果是葉子節(jié)點則將節(jié)點編號保存在一個數(shù)組中。最后通過便利保存節(jié)點編號的數(shù)組，將葉子節(jié)點編號輸出。
整體代碼文章來源：http://www.zghlxwxcb.cn/news/detail-672828.html
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MaxTree 10
#define Null -1 //子樹為空時定義為Null
#define Tree int
//定義樹節(jié)點
struct TreeNode {
Tree left; //左子樹的下標(biāo)
Tree right; //右子樹的下標(biāo)
}T[MaxTree];
//定義一個隊列，用于中序遍歷時進(jìn)行入隊出隊操作
struct Queue {
Tree data[MaxTree]; //保存Tree節(jié)點
int front; //隊首
int rear; //隊尾
}Q;
//建立一棵樹，并返回根節(jié)點
Tree BuildTree(struct TreeNode T[])
{
int n; //輸入n個節(jié)點
int i;
Tree Root; //最后找到的根節(jié)點
int check[MaxTree]; //記錄當(dāng)前各個節(jié)點是否已訪問
char cl, cr; //保存輸入的左、右節(jié)點
scanf("%d", &n); //輸入的n
getchar();//讀取回車
if (n) {
for (i = 0; i < n; i++) check[i] = 0; //初始化各個節(jié)點均未被訪問
for (i = 0; i < n; i++) {
scanf("%c %c", &cl, &cr); //輸入的左、右節(jié)點
getchar();//讀取回車
/*對cl的對應(yīng)處理 */
if (cl != '-') {
T[i].left = cl - '0';
check[T[i].left] = 1;
}
else T[i].left = Null;
/*對cr的對應(yīng)處理 */
if (cr != '-') {
T[i].right = cr - '0';
check[T[i].right] = 1;
}
else T[i].right = Null;
}
//n個節(jié)點中沒有被check的就是根節(jié)點
for (i = 0; i < n; i++)
if (!check[i]) break;
Root = i;
}
return Root;
}
void LevelOrderTraversal(Tree root)
{
if (!root) return; //若是空樹則直接返回
Tree leaves[MaxTree]; //保存葉子節(jié)點
/*初始化隊列 根結(jié)點放到隊列里面去*/
Q.front = -1;
Q.rear = -1;
Q.data[++Q.rear] = root;
int t = 0; //用于記錄葉節(jié)點數(shù)量
/*
然后接下來是一個循環(huán)
循環(huán)做三件事情:
第一件事情 從隊列里面拋出一個元素
第二件事情 把隊列剛拋出元素的Data print出來
第三件事情 是把它的左右兒子放到隊列里去
*/
while (Q.front != Q.rear) { //隊列不為空時
int i = Q.data[++Q.front]; //出隊
if (T[i].left == Null && T[i].right == Null) { //葉節(jié)點
leaves[t++] = i;
}
else { //非葉節(jié)點，左右子樹若存在就入隊
if(T[i].left != Null)
Q.data[++Q.rear] = T[i].left;
if (T[i].right != Null)
Q.data[++Q.rear] = T[i].right;
}
}
//實現(xiàn)最后一個節(jié)點后面沒有空格，其它節(jié)點后面有空格
for (int i = 0; i < t; i++) {
if(i < t - 1)
printf("%d ", leaves[i]);
else
printf("%d", leaves[i]);
}
}
int main()
{
Tree A = BuildTree(T);
LevelOrderTraversal(A);
return 0;
}
運行，輸入測試樣例，結(jié)果正確
文章來源地址http://www.zghlxwxcb.cn/news/detail-672828.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)：P3-樹(上)----編程作業(yè)02：List Leaves的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
