編程練習題目集目錄

題目

??Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

輸入格式

??Each input file contains one test case. For each case, the first line gives a positive integer $N(\le 10)$ which is the total number of nodes in the tree $??$ and hence the nodes are numbered from $0$ to $N?1$. Then $N$ lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a $"?"$ will be put at the position. Any pair of children are separated by a space.

輸出格式

??For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

輸入樣例

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

輸出樣例

4 1 5

題解

解題思路

??找到樹的根結點，根據樹的根結點以及其它一系列結點構建樹，按照從上到下，從左到右的順序（層次遍歷）輸出這棵樹的葉子結點。

完整代碼

#include <iostream>         // 包含標準輸入輸出流庫
#include <queue>            // 包含隊列數據結構庫using namespace std;        // 使用標準命名空間#define MaxN  10            // 定義最大節點數量// 定義二叉樹節點結構
struct TreeNode
{int Data;           // 節點存儲的數據int Left;           // 左子節點的索引，若無左子節點則為-2int Right;          // 右子節點的索引，若無右子節點則為-2
} TN[MaxN];             // TN[]為全局變量，存儲所有節點信息，最多MaxN個節點int buildTree(TreeNode T[], int n);         // 構建二叉樹，并返回根節點索引
void Traversal(int root);                   // 層序遍歷二叉樹，并輸出葉節點值int main(void)
{int N, root;                            // N表示樹的節點數量，root表示根節點索引cin >> N;root = buildTree(TN, N);                // 構建樹并獲取根節點索引Traversal(root);                        // 層序遍歷并輸出葉節點值return 0;
}// 構建二叉樹
int buildTree(TreeNode T[], int n)
{int i, check[MaxN];                  // 檢查數組，用于標記是否為子節點char left, right;                    // 用于存儲左右子節點的輸入字符if (n == 0) {                        // 如果節點數量為0，返回-2表示空樹return -2;}for (i = 0; i < n; i++) {           // 初始化所有節點，初始時假設所有節點都不是子節點check[i] = -1;                  // -1表示非子節點TN[i].Data = i;                 // 每個節點的編號即為自己的數據}for (i = 0; i < n; i++) {           // 根據輸入構建樹cin >> left >> right;           // 輸入當前節點的左右子節點信息if (left != '-') {                  // 如果有左子節點T[i].Left = left - '0';         // 將字符轉換為索引check[T[i].Left] = 1;           // 標記左子節點對應的索引為子節點}else {T[i].Left = -2;                 // 表示無左子節點}if (right != '-') {                 // 如果有右子節點T[i].Right = right - '0';       // 將字符轉換為索引check[T[i].Right] = 1;          // 標記右子節點對應的索引為子節點}else {T[i].Right = -2;                // 表示無右子節點}}// 查找根節點（未被標記為子節點的節點）for (i = 0; i < n; i++) {if (check[i] == -1) break;          // 找到根節點}return i;                               // 返回根節點索引
}
// 層序遍歷二叉樹并輸出葉節點值
void Traversal(int root)
{queue<struct TreeNode> Q;               // 定義一個隊列用于層序遍歷struct TreeNode T;                      // 臨時存儲隊列中的節點if (root == -2) {                       // 如果根節點不存在，直接返回return;}Q.push(TN[root]);                       // 將根節點入隊int flag = 0;                           // 標志變量，用于控制輸出格式while (!Q.empty()) {                    // 當隊列非空時T = Q.front();                      // 取出隊列頭部節點Q.pop();                            // 出隊if (T.Left == -2 && T.Right == -2) {        // 如果當前節點是葉節點if (flag == 1) cout << " ";             // 如果不是第一個葉節點，輸出空格else flag = 1;                          // 標記已經輸出過葉節點printf("%d", T.Data);             // 輸出葉節點的值}if (T.Left != -2) {Q.push(TN[T.Left]);                     // 如果有左子節點，將左子節點入隊}if (T.Right != -2) {                        // 如果有右子節點，將右子節點入隊Q.push(TN[T.Right]);}}
}