c++ - 遍历二叉树时如何跟踪层？

Question

如果我需要打印出用下面的结构构造的二叉树的每个元素。我怎样才能跟踪我打印的是哪一层元素？ struct for a binary tree node

例如: any binary tree

预期输出: 第 0 层:12 第-1层:28 19 第-2层:94 32 第-3层:65 18 72

Answer 1

基于GeeksForGeeks使用队列的解决方案

#include <iostream>
#include <queue>

using namespace std;

// A Binary Tree Node

struct node
{
    struct node *left;

    int data;

    struct node *right;
};

// Iterative method to do level order traversal
// line by line

void printLevelOrder(node *root)
{
    // Base Case

    if (root == NULL)
        return;

    // Create an empty queue for level order tarversal

    queue<node *> q;

    // Enqueue Root and initialize height

    q.push(root);

    int i = 0;

    while (q.empty() == false)

    {
        cout << "layer " << i << ": ";

        // nodeCount (queue size) indicates number

        // of nodes at current lelvel.

        int nodeCount = q.size();

        // Dequeue all nodes of current level and

        // Enqueue all nodes of next level

        while (nodeCount > 0)

        {
            node *node = q.front();

            cout << node->data << " ";

            q.pop();

            if (node->left != NULL)

                q.push(node->left);

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;
        }

        cout << endl;
        --i;
    }
}

// Utility function to create a new tree node

node *newNode(int data)
{
    node *temp = new node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;
}

// Driver program to test above functions

int main()
{
    // Create binary tree

    node *root = newNode(12);

    root->left = newNode(28);

    root->right = newNode(19);

    root->left->left = newNode(94);

    root->left->left->left = newNode(65);

    root->left->left->right = newNode(18);

    root->right->left = newNode(32);

    root->right->left->right = newNode(72);

    printLevelOrder(root);

    return 0;
}

基于CrazyForCode的使用递归函数和辅助函数的解决方案:

#include <iostream>
using namespace std;

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

void printLevel(node *, int);
int height(struct node *node);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node *root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++){
        printf("layer %d: ",i*-1+1);
        printLevel(root, i);
        cout << endl;
    }
}

/* Print nodes at a given level */
void printLevel(struct node *root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
    {
        printf("%d ", root->data);
    }
    else if (level > 1)
    {
        printLevel(root->left, level - 1);
        printLevel(root->right, level - 1);
    }
}

/* Compute the "height" of a tree */
int height(struct node *node)
{
    if (node == NULL)
        return 0;
    else
    {
        int lheight = height(node->left);
        int rheight = height(node->right);

        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}

node *newNode(int data)
{
    node *temp = new node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;
}

int main()
{
    // Create binary tree

    node *root = newNode(12);

    root->left = newNode(28);

    root->right = newNode(19);

    root->left->left = newNode(94);

    root->left->left->left = newNode(65);

    root->left->left->right = newNode(18);

    root->right->left = newNode(32);

    root->right->left->right = newNode(72);

    printLevelOrder(root);

    return 0;
}