如何修复我的功能以打印出霍夫曼树到屏幕？

Question

我有一棵霍夫曼树，我正试图将它打印到屏幕上，右分支水平延伸，左分支向下延伸。我的功能如下。如果节点是中间节点之一，IsNodeNamSingleChar() 只是 returns 一个 '*'。

void PrintBranches(Node * Top)
{
  if(Top == NULL){
    return;
  }
  if(Top->right != NULL){
    printf("-%c", IsNodeNameSingleChar(Top));
    Top = Top->right;
    PrintBranches(Top);
  }
  else{
    printf("%c\n|\n", IsNodeNameSingleChar(Top));
    Top = Top->left;
    PrintBranches(Top);
  }
}

我知道这是不对的，但我不知道该如何解决。目前，打印出来（对于我正在使用的测试文件）：

  -*  -*  -*B
|

Answer 1

我想我有一个解决方案，我将用 'pseudo-type' 代码写出来...因为我认为您真正需要的是一种可行的算法...

.....这个解决方案有两个相互调用的递归函数。

应该用

调用

printNodeRight(&topNode, 0);

函数是...

int printNodeRight(Node * pTop, int indent)
{  
  if (current node pTop is not end of branch)
  {
    printf("*-");
    printNodeRight(pTop->Right,indent+1);
    printNodeLeft(pTop->Left,indent);
  } else {
    printf("%c\n", pTop->value);
    for (loop indent times) 
    {
      printf("| ");
    }
    printf("\n);
  }
  return 0;
}

int printNodeLeft(Node * pTop, int indent)
{  
  for (loop (indent-1) times) 
  {
    printf("| ");
  }
  printNodeRight(pTop,indent);
  return 0;
}

请注意，此代码应生成如下所示的树...

*-*-b
| |
| c
|
a

*-*-*-b
| | |
| | *-d
| | |
| | e
| |
| *-*-*-g
| | | | 
| | | *-h
| | | |
| | | i
| | |
| | j
| |
| c
|
a

原回答

由于文本打印到屏幕的方式，这是一个特别困难和有趣的挑战。

因此，例如使用您拥有的递归例程，将无法打印以下树

  -*-*-b
   | | 
   a c

因为您将从打印开始

  -*-*-b

那么c会在b之后直接打印得到

  -*-*-bc
  |

如果您将 printf 从“%c\n|\n”更改为“\n|\n%c”，您将得到

  -*-*-b
  |
  c

但根本问题是，使用递归函数，您将在打印 a 之前 打印 c 。

你的问题在
的第二行
-*-*-b | | a c

您需要在 c 之前打印 a，但是您的递归例程会在到达 a 之前到达 c，因此很难（？不可能）返回并在 c 前面打印 a --- 也当你要打印第二行你需要知道有多少空格来打印 c 和 a.... 总的来说这是一个相当困难的挑战 - 可以通过小心地左右移动光标来完成它.

如何修复我的功能以打印出霍夫曼树到屏幕？

How can I fix my function to print out a Huffman tree to screen?

c

recursion

binary-tree

nodes

huffman-code