用C语言编写表示二叉树的递归函数

Question

问题

我想要按中序遍历打印二叉树节点，并希望节点的高度与其数据相对应用尽可能多的短划线（即横杠）来打印。

已进行的研究

我发现了其他文章，例如这篇文章或这篇文章，但我仍然不知道如何以我想要的方式表示我的二叉树，因为它与那些问题中的二叉树有所不同。

示例

假设我以以下方式插入具有数据的节点：

5,4,2,3,9,8

我展示二叉树时期望的输出如下：

-9
--8
5
-4
---3
--2

玩具示例代码

到目前为止，我已经能够按正确的顺序打印节点。但是经过几天的努力，我仍然不知道如何实现递归函数以获得正确的表示。我也尝试了循环，但发现它更混乱，并且也没有得到正确的结果。

问题在于破折号的数量不正确，我不确定在递归中需要在哪里添加破折号。我在考虑可能需要重写整个printBinaryTreeRecurrsively代码。

下面是可以编译为整体的玩具示例代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct repBinaryTree *BinaryTree;

struct repBinaryTree {
  int data;
  BinaryTree left;
  BinaryTree right;
};

BinaryTree newNode() {
  BinaryTree b = new repBinaryTree;
  b->data = NULL;
  b->left = b->right = NULL;
  return b;
}

BinaryTree insertNode(int i, BinaryTree b) {
  if (b==NULL) {
    b = newNode();
    b->data = i;
  } else if ( i < b->data ) {
    if (b->left == NULL) {
      b->left = newNode();
      b->left->data = i;
    } else {
      insertNode(i, b->left);
    }
  } else if ( i > b->data ) {
    if (b->right == NULL) {
      b->right = newNode();
      b->right->data = i;
    } else {
      insertNode(i, b->right);
    }
  }
  return b;
}

char* printBinaryTreeRecurrsively(BinaryTree b, char level[]) {
  if (b == NULL) {
    printf("\n");
    return level;
  } else {
    level = printBinaryTreeRecurrsively(b->right, level);
    printf("%s%d",level,b->data);
    level = printBinaryTreeRecurrsively(b->left, level);
  }
  strcat(level,"-");
  return level;
}

int main () {
  BinaryTree b = insertNode(5,NULL);
  b = insertNode(4, b);
  b = insertNode(2, b);
  b = insertNode(3, b);
  b = insertNode(9, b);
  b = insertNode(8, b);
  printf("Recursive BinaryTree print:");
  char level0[] = "";
  printBinaryTreeRecurrsively(b, level0);
  printf("Expected BinaryTree print:");
  printf("\n-9\n--8\n5\n-4\n---3\n--2\n");
}

编译并通过命令行运行程序后，我得到的输出如下：

cedric@multivac:~$ g++ printBinaryTree.cpp -o printBinaryTree
cedric@multivac:~$ ./printBinaryTree 
Recursive BinaryTree print:
9
8
--5
--4
--3
---2
Expected BinaryTree print:
-9
--8
5
-4
---3
--2

问题

如何修改我的printBinaryTreeRecurrsively函数的代码，以便获得正确的输出？

- Cedric Zoppolo

Answer 1

将函数修改为以下内容

void printBinaryTreeRecurrsively(BinaryTree b, int level) {
  if (b == NULL) {
    printf("\n");
  } else {
    printBinaryTreeRecurrsively(b->right, level+1);
    for (int i = 0; i < level; i++) {
        printf("-");
    }
    printf("%d",b->data);
    printBinaryTreeRecurrsively(b->left, level+1);
  }
}

并在 main() 中调用它：

printBinaryTreeRecurrsively(b, 0);

这种方法比担心字符串连接等要简单得多。只需用一个int跟踪您在哪个级别，打印正确数量的-，并告诉下面的级别使用一个更多的-打印。

- Chris Loonam