I am struggling to print a binary search tree like the below output (in-order traversal):
2, 3, 6, 9
the output I get:
2, 3, 6, 9,
The code I have:
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left_node);
printf("%d, ", root->value);
inorder(root->right_node);
}
}
how struct node is implemented:
struct node {
int value;
struct node *left_node;
struct node *right_node;
};
I am not sure how to get rid of the comma and the space characters after the last element.
CodePudding user response:
The theory is that you have to print the ,
only if you are sure that the leaf you are printing is not the last one.
Thus, you need a way to tell your nodes (sub-trees) whether they contain the "last" leaf of your tree. One way of doing is to create another function which takes one more parameter:
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);
}
CodePudding user response:
You only need to print a ,
if the right node is not null. With that in mind, split the printf()
into two calls and check whether the next node is null or not.
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);
}
}