C:寻找树中特定叶子的霍夫曼编码路径

Question

我正在尝试编写一个递归函数来定位霍夫曼树中的特定叶子，然后用 0 和 1 打印其最短路径(0 表示向左遍历，1 表示向右遍历)。我理解我需要做的事情的逻辑，但我没有成功地实际实现它。我相信我在这里有一个很好的框架，但我缺少的部分是一些更复杂的逻辑来告诉我什么时候应该实际运行 printf 什么时候不应该(因为这目前只打印每个零和一个)。另外，我知道除此之外的其余逻辑都可以正常工作，因为如果您进行正常遍历，而不必绘制最短路径，则可以找到我要搜索的每个元素。

我已经尝试在网上查看了很多资源，但找不到解决方案，或者至少，我无法正确识别解决方案。我可能已经重写了 50 次或更多次。让我知道你的想法!

void traverse(struct tree *curr, struct tree *cmp)
{
  if (curr == NULL)
  {
    return;
  }

  if (getLeft(curr) == NULL && getRight(curr) == NULL)
  {
    if (curr == cmp)
    {
      return;
    }
  }

  if (getLeft(curr) != NULL)
  {
    printf("0");

    traverse(getLeft(curr), cmp);
  }

  if (getRight(curr) != NULL)
  {
    printf("1");

    traverse(getRight(curr), cmp);
  }
}

对于context:cmp是我们要查找的节点，getLeft()和getRight()返回的左右 child 一个节点，curr 开始作为哈夫曼树本身的根。另外，这个 printf 之所以起作用，是因为我遍历了所有已知的叶子，打印了关于叶子的其他信息，然后调用了这个遍历方法，后面跟了一个换行符。

Answer 1

有几种解决方案。

首先，您可以像现在这样遍历整个树并构建一个代码表。然后使用表，而不是树。这样您就不会浪费时间在整棵树中搜索每个代码。当您遍历树时，您构建了一个由 0 和 1 组成的字符串，当您到达一片叶子时，您将构建的字符串和叶子中的符号保存在表中。然后扔掉这棵树。这是推荐的方法。

其次，您的链接可以是双向的。由于您有一个指向叶子的指针，您可以简单地从叶子开始，然后返回根，反向构造 0 和 1 的字符串。

第三，您可以通过让遍历函数返回 true 或 false 来坚持对每一片叶子进行痛苦的树搜​​索。如果到达所需的叶子，或者其中一个遍历调用返回 true，它将返回 true。然后根据哪个遍历调用返回 true，您将打印或保存零或一。这将反向打印路径。如果您以相反的顺序将它们保存在一个字符串中而不是打印出来，那么您可以在第一次遍历调用返回时打印该字符串。