6-2 先序输出叶结点

假设我们有一个二叉树的数据结构，每个节点包含一个值和左右子节点的指针。以下是先序输出叶结点的实现：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorder(TreeNode* root) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) { // 如果当前节点是叶结点，则输出
        cout << root->val << " ";
    }
    preorder(root->left);
    preorder(root->right);
}

我们可以先判断当前节点是否为叶结点，如果是，则输出其值。然后递归遍历其左右子树。这样可以保证先输出叶结点。

相关问题

6-11 先序输出叶结点pta

本题需要使用二叉树的先序遍历算法，判断每个节点是否为叶子节点，如果是叶子节点则输出其值。

具体步骤如下：

1. 定义二叉树结构体和创建二叉树的函数。

#include <iostream>
using namespace std;

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* createTree() {
    char val;
    cin >> val;
    if (val == '#') {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

2. 定义先序遍历函数和判断叶子节点的函数。

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

bool isLeaf(TreeNode* root) {
    if (root == NULL) {
        return false;
    }
    if (root->left == NULL && root->right == NULL) {
        return true;
    }
    return false;
}

3. 在先序遍历的过程中，判断当前节点是否为叶子节点，如果是则输出其值。

void preOrderLeaf(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    if (isLeaf(root)) {
        cout << root->val << " ";
    }
    preOrderLeaf(root->left);
    preOrderLeaf(root->right);
}

4. 最后在主函数中调用创建二叉树和先序遍历叶子节点的函数。

int main() {
    TreeNode* root = createTree();
    preOrderLeaf(root);
    return 0;
}

完整代码如下：

6-3 先序输出叶结点 (15 分)

### 回答1：
先序遍历二叉树，输出叶子节点。

先序遍历二叉树的过程是：先访问根节点，然后访问左子树，最后访问右子树。在访问左子树和右子树的过程中，如果遇到叶子节点，就输出该节点的值。

具体实现可以使用递归或者栈来实现。递归的实现比较简单，可以按照上述过程来实现。栈的实现需要先将根节点入栈，然后循环执行以下操作：弹出栈顶节点，如果该节点是叶子节点，则输出该节点的值；否则，先将右子树入栈，再将左子树入栈。直到栈为空为止。

### 回答2：
本题要求我们编写一个程序，在二叉树的先序遍历中输出所有的叶结点。

首先，我们需要明确一下二叉树的先序遍历的过程。先序遍历的过程是：先遍历当前节点，然后遍历左子树，最后遍历右子树。因此，我们可以使用递归的方法，每次遍历到一个节点，判断其是否为叶子节点，如果是叶子节点，则输出其值。

具体的实现过程如下：

void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        cout << root->val << " ";  // 如果是叶子节点，则输出其值
    }
    preOrderTraversal(root->left);   // 遍历左子树
    preOrderTraversal(root->right);  // 遍历右子树
}

我们可以看到，这个函数的参数是二叉树的根节点，每次遍历一个节点，会先判断它是否为叶子节点，再遍历左右子树，在遍历左右子树的过程中，会使用递归的方法。这样，整个二叉树就被遍历完了，所有的叶子节点也被输出了。

需要注意的是，函数中需要判断节点是否为空，如果为空则直接返回。此外，如果二叉树是空树，也需要特殊处理。

按照上述方法，我们编写了一个可以输出先序叶子节点的程序。这个程序的时间复杂度是 O(n)，其中 n 是二叉树中节点的个数。

### 回答3：
题目要求我们从二叉树的根节点开始，按照先序遍历的顺序依次输出叶子节点。

先回忆一下什么是二叉树的先序遍历：首先输出根节点，然后遍历左子树，最后遍历右子树。我们可以在这个过程中加入一个判断条件：当该节点为叶子节点时输出该节点。

因为先序遍历是一种深度优先遍历，因此我们可以用递归来实现这个算法。具体来说，我们可以按照如下步骤实现：

1. 如果二叉树为空，则直接返回。

2. 输出当前节点的数据。

3. 如果当前节点是叶子节点，则输出该节点的数据。

4. 遍历当前节点的左子树，重复步骤 1-3。

5. 遍历当前节点的右子树，重复步骤 1-3。

通过这样的实现，我们可以得到该二叉树的先序遍历序列，并且在遍历到每个叶子节点时输出该节点的数据。如果需要将输出的结果存储下来，我们可以用一个容器（如数组或列表）来保存遍历过程中所有的叶子节点。

需要注意的是，这个算法可能存在一定的效率问题。因为遍历过程中需要判断当前节点是否为叶子节点，而这个判断需要额外的时间复杂度，因此可能会让算法的时间复杂度略微增加。不过在一般情况下，这个问题并不会对程序的效率产生太大的影响。