I want to print a binary tree like this:

50
├─25
|  ├─10
|  |  ├─5
|  |  └─15
|  └─40
|     ├─35
|     └─45
└─75
   ├─60
   |  ├─55
   |  └─65
   └─90
      ├─85
      └─95

But my program can only print like this:

50
├─25
|  ├─10
|  |  ├─5
|  |  └─15
|  └─40
|  |  ├─35
|  |  └─45
└─75
|  ├─60
|  |  ├─55
|  |  └─65
|  └─90
|  |  ├─85
|  |  └─95

I tried a lot to remove the rudundant "|" character but still failed. I've read some similar questions but they are written in Java so I can't understand. Could somebody show me how to do it?

Here is my code which contains the test case above:

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* get_node(int value) {
    struct Node* new = (struct Node*) malloc(sizeof (struct Node));
    new->data = value;
    new->left = NULL;
    new->right = NULL;
    return new;
}

void insert(struct Node **ptr, int value) {
    struct Node* root = *ptr;
    if(root == NULL) {
        *ptr = get_node(value);
    } else if(value <= root->data){
        insert(&root->left, value);
    } else {
        insert(&root->right, value);
    }
}

void print_subtree(struct Node* root, int indent, int is_right) {
    if(root == NULL)
        return;

    printf("\n");
    for (int i = 0; i < indent;   i) {
        printf("|  ");
    }

    if(is_right)
        printf("└─%d", root->data);
    else
        printf("├─%d", root->data);

    print_subtree(root->left, indent   1, 0);
    print_subtree(root->right, indent   1, 1);
}

void print(struct Node* root) {
    if(root != NULL) {
        printf("%d", root->data);
        print_subtree(root->left, 0, 0);
        print_subtree(root->right, 0, 1);
    }
}

int main() {
    struct Node* root = NULL;
    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 75);
    insert(&root, 10);
    insert(&root, 40);
    insert(&root, 60);
    insert(&root, 90);
    insert(&root, 5);
    insert(&root, 15);
    insert(&root, 35);
    insert(&root, 45);
    insert(&root, 55);
    insert(&root, 65);
    insert(&root, 85);
    insert(&root, 95);
    print(root);
}

CodePudding user response：

You cannot just count the level of indentation where you are at the moment. You must keep track about the path how you came where you are now.

For some fixed maximum number of levels you can use this code:

#include <stdio.h>
#include <stdbool.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

#define MAX_LEVELS 10

void print_subtree(struct Node* root, int indent, int is_right) {
    static bool right[MAX_LEVELS] = {0};
    
///////////////////////
// TODO: Check for maximum level and do some extra handling...
    right[indent] = is_right;

    if(root == NULL)
        return;

    int i;
    // Print all levels until (without) level above current level.
    for (i = 0; i < indent; i  )
    {
        printf("%s", right[i] ? "   " : "|  ");
    }

    // Print level directly above current level.
    if (i <= indent)
    {
        printf("%s", right[i] ? "└─" : "├─");
    }

    // Print current level
    printf("%d\n", root->data);

    // Print child levels...
    print_subtree(root->left, indent   1, 0);
    print_subtree(root->right, indent   1, 1);
}

void print(struct Node* root) {
    if(root != NULL) {
        printf("%d\n", root->data);
        print_subtree(root->left,  0, 0);
        print_subtree(root->right, 0, 1);
    }
}


// #layer #1, leaves
struct Node Node_05 = {.data =  5, .left = NULL, .right = NULL};
struct Node Node_15 = {.data = 15, .left = NULL, .right = NULL};
struct Node Node_35 = {.data = 35, .left = NULL, .right = NULL};
struct Node Node_45 = {.data = 45, .left = NULL, .right = NULL};
struct Node Node_55 = {.data = 55, .left = NULL, .right = NULL};
struct Node Node_65 = {.data = 65, .left = NULL, .right = NULL};
struct Node Node_85 = {.data = 85, .left = NULL, .right = NULL};
struct Node Node_95 = {.data = 95, .left = NULL, .right = NULL};

// layer #2
struct Node Node_10 = {.data = 10, .left = &Node_05, .right = &Node_15};
struct Node Node_40 = {.data = 40, .left = &Node_35, .right = &Node_45};
struct Node Node_60 = {.data = 60, .left = &Node_55, .right = &Node_65};
struct Node Node_90 = {.data = 90, .left = &Node_85, .right = &Node_95};

// layer #3
struct Node Node_25 = {.data = 25, .left = &Node_10, .right = &Node_40};
struct Node Node_75 = {.data = 75, .left = &Node_60, .right = &Node_90};

// layer #4, root
struct Node Node_50 = {.data = 50, .left = &Node_25, .right = &Node_75};


int main (void)
{
    struct Node *root = &Node_50;
    print(root);
}

Output:

~/stackoverflow$ gcc -Wall -Wextra -pedantic -g test.c -o test
~/stackoverflow$ ./test
50
├─25
|  ├─10
|  |  ├─5
|  |  └─15
|  └─40
|     ├─35
|     └─45
└─75
   ├─60
   |  ├─55
   |  └─65
   └─90
      ├─85
      └─95

If you need to be more flexible about the depth of your tree, you may need to increase the limit or use some dynamic memory allocation that can be increased at runtime if needed.