在C中打印带有逗号和空间的二进制搜索树

Question

我正在努力打印一个二进制搜索树，如以下输出（订购遍历）：

2, 3, 6, 9

我获得的输出：

2, 3, 6, 9, 

我拥有的代码：

void inorder(struct node* root)
{   
    if (root != NULL) {
        inorder(root->left_node);
        printf("%d, ", root->value);
        inorder(root->right_node);
    }
     
}

如何实现结构节点：

struct node {
    int value;           
    struct node *left_node;  
    struct node *right_node; 

};

我不确定如何摆脱逗号和空间最后一个元素之后的字符。

Answer 1

理论是，仅当您确定要打印的叶子不是最后一个时，才必须打印，。

因此，您需要一种方法来告诉您的节点（子树）是否包含树的“最后”叶子。一种做法的方法是创建另一个功能，该函数还需要一个参数：

static void inorder_haslastleaf(struct node* root, int haslastleaf) {
  if (root != NULL) {
    /* Print the left sub-tree, we are guaranteed it can't contain the last leaf
     * because the current node will be printed right after. */
    inorder_haslastleaf(root->left_node, 0);
    printf("%d", root->value);
    /* Now, we have to print comma if and only if we are sure that
     * some nodes will be printed after it. We can make sure of that
     * thanks to the haslastleaf flag. */
    if(!haslastleaf || root->right_node != NULL)
      printf(", ");
    /* Finally, print the right sub-tree. Pass back haslastleaf to it
     * to notify whether it contains the last leaf or not  */
    inorder_haslastleaf(root->right_node, haslastleaf);
  }
}

void inorder(struct node* root)
{
  /* Of course, the main tree contains the last leaf */
  inorder_haslastleaf(root, 1);
}

Answer 2

您只需要打印，，如果右节点不为null。考虑到这一点，将printf（）拆分为两个调用，并检查下一个节点是否为null。

void inorder(struct node* root)
{   
    if (root != NULL) {
        inorder(root->left_node);
        printf("%d", root->value);
        if (root->right_node)
             printf(", ");
        inorder(root->right_node);
    }         
}