时间戳

首页 > 解决方案 > 打印二叉搜索树的所有叶节点

c - 打印二叉搜索树的所有叶节点

问题描述

我正在尝试按升序打印所有叶节点，但输出与我预期的不同。
插入功能：

Node *insert(Node **root, int k)
{
    if(*root == NULL)
    {
        Node *newNode = (Node *)malloc(sizeof(Node ));
        if(newNode == NULL)
            return NULL;
        newNode->key = k;
        newNode->left = NULL;
        newNode->right = NULL;
        (*root) = newNode; 
        return newNode; 
    }
    if(k < (*root)->key)
        return insert(&((*root)->left),k);
    else
        return insert((&(*root)->right),k);
}

升序打印功能：

void printLeafs(Node *r)
{
    if (r != NULL)
    {
        if(r->right == NULL && r->left == NULL)
           printf("%d ", r->key);
        printLeafs(r->right);       
        printLeafs(r->left);
        
    }
}

示例：
输入：1 2 3 4 5 6 7 8 9
正确输出：4 7 8 9
我的输出：9

其他示例：
bst

在这棵树中，我的代码应该打印：
4 6 7 9 10有
什么想法吗？

标签： cbinary-search-tree

解决方案

你只打印叶子，因为

if(r->right == NULL && r->left == NULL)

对于非常特殊的输入1 2 3 4 5 6 7 8 9，您只有一个叶子，即 9。

因此，您的代码正在执行“打印二叉树的所有叶节点”，并在叶节点上施加压力。

但是，如果您想要所有节点：

要解决此问题，您不应跳过非叶节点中的值，而是将其打印在正确的位置：

printLeafs(r->right);       
printf("%d ", r->key);
printLeafs(r->left);

为了获得乐趣和洞察力，请在未更改的代码上尝试不同的输入： 5 4 6 2 1 3 8 7 9

注意：我承认忽略了所需的输出，因为它既不匹配“所有叶子”也不匹配“全部”。我的回答与（回顾）假设您有复制粘贴错误并且所需的输出是1 2 3 4 5 6 7 8 9.

推荐阅读