c - 如何修复我的函数以将霍夫曼树打印到屏幕上？

Question

我有一棵霍夫曼树，我正在尝试将其打印到屏幕上，右分支水平延伸，左分支向下。我的功能如下。如果节点是中间节点之一，则 IsNodeNamSingleChar() 仅返回“*”。

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

我想我有一个适合你的解决方案，我将用“伪类型”代码写出来......因为我认为你真正需要的是一个可以工作的算法......

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

应该用

调用

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 需要多少个空格......总的来说，这是一个相当困难的挑战 - 可以通过小心地左右上下移动光标来完成。