如何在c中按级别打印二叉树中的元素

Question

我得到的是二叉树，不是BST，所以元素没有排序，每个节点保存的信息都是字符串类型。当我在 BST 中打印包含整数的元素时，我会像这样递归：(in_order printing)

void PrintElements(const Data* node)
{
    // Check if its empty
    if (node == NULL)
        return;

    PrintElements(node->left);     
    printf(" %d\n", node->key);      
    PrintElements(node->right);    
}

但我无法弄清楚如何在包含未排序（按字母顺序）的字符串的二叉树中按级别打印它们。非常感谢任何帮助。

Answer 1

您必须实现一些辅助功能才能以递归方式按级别打印：

首先，您需要一个函数来检索树的层数

int getLevelCount(Data *node)
{
    if (node == NULL)
    {
        return 0;
    }
    int leftMaxLevel = 1 + getLevelCount(node->left);
    int rightMaxLevel = 1 + getLevelCount(node->right);
    if (leftMaxLevel > rightMaxLevel)
    {
        return leftMaxLevel;
    }
    else
    {
        return rightMaxLevel;
    }
}

其次，您必须实现一个打印树的特定级别的函数：

void printLevel(Data *node, int level)
{
    if (node != NULL && level == 0)
    {
        printf("%s\n", node->key);
    }   
    else if (node != null)
    {
        printLevel(node->left, level - 1);
        printLevel(node->right, level - 1);
    }
}

最后，打印树的每一层（从根节点开始）：

void printElements(Data *node)
{
    int i;
    int levelCount = getLevelCount(node);
    for (i = 0; i < levelCount; i++)
    {
        printLevel(node, i);
    }
}

希望对您有所帮助。

如何在c中按级别打印二叉树中的元素

How to print elements from Binary Tree by level in c

c

binary-search-tree