Print a Binary tree in alphabetical order

Question

I need to print out a binary tree from the bottom left most node to the bottom right most node, with the tree being sorted in alphabetical order.

struct Book{
/* Book details */
char title[MAX_TITLE_LENGTH+1];   /* name string */
char author[MAX_AUTHOR_LENGTH+1]; /* job string */
int  year;                        /* year of publication */

/* pointers to left and right branches pointing down to next level in
  the binary tree (for if you use a binary tree instead of an array) */
struct Book *left, *right;};

I wrote a compare function to add books to the tree in alphabetical order, but cannot figure out how to modify it to print them in alphabetical order instead.

void compare(struct Book *a, struct Book* new){
struct Book *temp; temp =(struct Book *)malloc(sizeof(struct Book));
if(strcmp(a->title, new->title)<0){
    if(a->right == NULL)
        a->right = new;
    else{
        temp = a->right;
        compare(temp,new);
    }
}

else if(strcmp(a->title, new->title)>0){
    if(a->left == NULL)
        a->left = new;
    else{
        temp = a->left;
        compare(temp,new);
    }
}
else if(strcmp(a->title, new->title) == 0){
    fprintf(stderr, "\nThis title already exists\n");
}}

You don't have to modify the insertion code in order to print it. Proper insertion ensures that left nodes are "smaller" than right nodes. Just walk the tree in in-order fashion. All the string comparisons are in the insertion, so that printing can rely of the correct order. — M Oehm
If the tree is already in sorted order, why would you want to touch the compare function? Instead you need to provide a traverse like function. — Gerhardh
I would also suggest adding this on top of compare function "int comparison = strcmp(a->title, new->title);" and the using "comparison" in all your ifs. You also don't have to cast malloc. — Shadowchaser

Shadowchaser Shadowchaser · Accepted Answer · 2020-05-04T14:57:33

This could be your print function:

void print(struct Book *root) {
    if (root->left)
        print(root->left);

    printf("%s\n", root->title);

    if (root->right)
        print(root->right);
}

Print a Binary tree in alphabetical order

1 Answers