时间戳

首页 > 解决方案 > 如何在 C++ 中实现逐级计数/显示节点的函数

c++ - 如何在 C++ 中实现逐级计数/显示节点的函数

问题描述

我在一本在线书籍中得到了这个任务，但我无法弄清楚。我想我必须使用某种 BFS 或 DFS，但我不知道该怎么做。

由于害怕浪费太多时间，我没有尝试过很多事情，但是我尝试过的是使用从节点开始的迭代并使用大量 if 语句来找到节点上的不同值我需要，但它根本不起作用。

string CharacterAnalyzer::nodeCountByLevel(nodeptr_t const node) const {
    /* TODO (1):
     * Return a formatted string of the node count at each level. For example for the 
     * text "Hello all!" the string will be:
     * 
     * Each line is terminated with a newline.
     * 
     * Node count by level:
     *    Level 1: TN(1), LRN(2), LON(0), RON(0), LN(0)
     *    Level 2: TN(2), LRN(0), LON(1), RON(1), LN(0)
     *    Level 3: TN(2), LRN(0), LON(0), RON(0), LN(2)
     *
     * where 
     * TN - level node count
     * LRN - two child node count
     * LON - left only child count
     * RON - right only child count
     * LON - leaf node count
     */

}// end nodeCountByLevel()

////////////////////////
//The accompanying code in .h
////////////////////////

  bool hasTwoChildren(nodeptr_t const node) const    { return (node->left && node->right);   }// end hasTwoChildren()

  bool hasLeftChildOnly(nodeptr_t const node) const  { return (node->left && !node->right);  }// end hasLeftChildOnly()

  bool hasRightChildOnly(nodeptr_t const node) const { return (node->right && !node->left);  }// end hasRightChildOnly()

  bool isLeaf(nodeptr_t const node) const            { return (!node->left && !node->right); }// end isLeaf()

标签： c++binary-tree

解决方案

实现 DFS 的一种方法是使用递归函数，如下所示

void depth_first_search(const nodeptr_t node)
{
    // Do something with node
    // ...
    if (node->left)
        depth_first_search(node->left);

    if (node->right)
        depth_first_search(node->right);
}

您可以轻松地让这个函数知道它的深度，如下所示

void depth_first_search(const nodeptr_t node, unsigned depth)
{
    // Do something with node and depth
    // ...

    if (node->left)
        depth_first_search(node->left, depth + 1);

    if (node->right)
        depth_first_search(node->right, depth + 1);
}

在您的情况下，“做某事”将是std::vector使用它在此深度遇到的节点类型的计数来更新某个容器（例如 a ）。为此，您当然需要从函数内部访问此结构。这可以通过以下任一方式完成

  • 使容器（或指向它的指针或引用）成为全局变量
  • depth_first_search在以容器为成员的类中实现
  • 将容器作为附加参数传递给depth_first_search

最后一个选项的一个变体是使用“访客模式”，就像这样

void depth_first_search(const nodeptr_t node, unsigned depth, Visitor& visitor)
{
    // Do something with node and depth
    // ...

    visitor.visit(node, depth);

    if (node->left)
        depth_first_search(node->left, depth + 1, visitor);

    if (node->right)
        depth_first_search(node->right, depth + 1, visitor);
}

从现在派生的某些类Visitor确切地知道如何处理节点和深度信息（例如计算它们并将结果存储在容器中）。这里的好处是，如果你下次需要对节点做一些不同的事情，你只需实现一个新的访问者。

推荐阅读