基于数组实现的二叉树如何仅显示所有叶子节点

Hey there! Let's work through this problem step by step. It sounds like you're using an array to implement a binary tree, and your displayLeafValues() function is either outputting an extra index value (70) or getting stuck in an infinite loop when you start at index 25. Let's break down what's going wrong and how to fix it.

First, Clarify Array-Based Binary Tree Rules #

Most array implementations use one of two indexing schemes for nodes:

• 0-based: A node at index i has a left child at 2*i + 1 and right child at 2*i + 2
• 1-based: A node at index i has a left child at 2*i and right child at 2*i + 1

A leaf node is one where both children are either outside the array bounds, or marked as empty (you might use a sentinel value like -1 for empty nodes).

Why You're Seeing "70" in Your Output #

That extra 70 is almost certainly an index value being printed by mistake. Double-check your function code—you probably have a line like cout << index << " "; instead of (or in addition to) printing the node's value (arr[index]). Remove any references to printing the index, and you'll get rid of that unwanted number.

Why Starting at Index 25 Causes an Infinite Loop #

Infinite loops here usually stem from missing or incorrect termination conditions in your traversal. If you start at index 25 and don't check whether the current index is beyond the array's size, or whether the node is empty, your code will keep trying to access out-of-bounds indices (or loop through invalid nodes) indefinitely.

The Fix: Correct Leaf Node Detection & Traversal #

Here's a revised version of the displayLeafValues() function that should work, assuming your tree uses 0-based indexing and -1 for empty nodes:

class BinaryTree {
public:
    int sizeOfTree;
    int* arr;

    // Constructor and other methods...

    void displayLeafValues(int currentIndex = 0) {
        // Termination condition: index is out of bounds or node is empty
        if (currentIndex >= sizeOfTree || arr[currentIndex] == -1) {
            return;
        }

        int leftChild = 2 * currentIndex + 1;
        int rightChild = 2 * currentIndex + 2;

        // Check if current node is a leaf (both children are empty/out of bounds)
        bool leftIsEmpty = (leftChild >= sizeOfTree) || (arr[leftChild] == -1);
        bool rightIsEmpty = (rightChild >= sizeOfTree) || (arr[rightChild] == -1);

        if (leftIsEmpty && rightIsEmpty) {
            // Only print the node's value, not the index!
            cout << arr[currentIndex] << " ";
            return;
        }

        // Recursively traverse left and right subtrees
        displayLeafValues(leftChild);
        displayLeafValues(rightChild);
    }
};

Key Fixes in This Code: #

• Proper Termination: We first check if the current index is outside the array or the node is empty—if so, we exit immediately to prevent infinite loops.
• Leaf Node Check: We verify both children are empty before printing the current node's value.
• No Index Output: We only print arr[currentIndex], not the index itself.
• Root Start: The function defaults to starting at index 0 (the root node) so you don't have to pass an index unless you need to traverse a subtree.

If You Prefer Iterative Traversal (Avoid Recursion) #

If recursion is causing issues, here's an iterative version using a stack that does the same thing:

void BinaryTree::displayLeafValues() {
    if (sizeOfTree == 0) return;

    stack<int> nodeStack;
    nodeStack.push(0); // Start at root

    while (!nodeStack.empty()) {
        int currentIndex = nodeStack.top();
        nodeStack.pop();

        if (currentIndex >= sizeOfTree || arr[currentIndex] == -1) {
            continue;
        }

        int leftChild = 2 * currentIndex + 1;
        int rightChild = 2 * currentIndex + 2;

        bool leftIsEmpty = (leftChild >= sizeOfTree) || (arr[leftChild] == -1);
        bool rightIsEmpty = (rightChild >= sizeOfTree) || (arr[rightChild] == -1);

        if (leftIsEmpty && rightIsEmpty) {
            cout << arr[currentIndex] << " ";
            continue;
        }

        // Push right first so left is processed first (matches recursive order)
        if (!rightIsEmpty) {
            nodeStack.push(rightChild);
        }
        if (!leftIsEmpty) {
            nodeStack.push(leftChild);
        }
    }
}

Quick Debugging Tips #

• Double-check your indexing rule (0-based vs 1-based) and adjust the child calculations if needed.
• Make sure sizeOfTree accurately reflects the length of your array.
• If you don't use a sentinel value for empty nodes, remove the arr[currentIndex] == -1 checks—just rely on index bounds.

This should give you the desired output: 25 62 90 120 without any extra index values or infinite loops.

内容的提问来源于stack exchange，提问作者revgirl2012