So right now, when I have a tree that looks like:

       5
     /   \
   3      6
    \      \
    4       7
             \
              9

I can print this in level order so that

5, 
3, 6, 
4, 7, 
9, 

this is printed

However, I want to make it so that it prints something like this:

5,
3, 6,
0, 4, 0, 7,
0, 0, 0, 0, 0, 0, 0, 9, 

So that all the NULL nodes are also printed as 0.

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


typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
} tree;


tree *new(int num){
    tree *temp = (struct tree *)(malloc(sizeof(tree)));

    temp->data = num;
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}


tree *insert(tree *tree, int data){
    if(tree == NULL){
        return new(data);
    }

    if(data > tree->data){
        tree->right = insert(tree->right, data);
    }
    else{
        tree->left = insert(tree->left, data);
    }

    return tree;
}

int height(tree *node){
    if(node == NULL){
        return 0;
    }
    else{
        int left_height = height(node->left);
        int right_height = height(node->right);
        if(left_height > right_height){
            return left_height   1;
        }
        else{
            return right_height   1;
        }
    }
}


void current_height(tree *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%d, ", root->data);
    }
    else if(level > 1){
        current_height(root->left, level - 1);
        current_height(root->right, level - 1);
    }
}


void level_order(tree *root){
    int h = height(root);
    for(int i = 0; i <= h; i  ){
        current_height(root, i);
        printf("\n");
    }
}


int main(){

    tree *root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 4);
    root = insert(root, 7);
    root = insert(root, 9);
    

    level_order(root);

}

This is the code I have so far

BTW, I also thought about putting an index into struct tree so that I could change the tree into an array and just print the array. But I found that it would make the deleting function too complicated so I didn't use that idea

CodePudding user response：

You have to simulate tree content which is not there.
Since you have the info on the relative target level as your additional parameter already in place that is not hard.
Just invent more tree nodes in case of NULL pointers before the target depth, always giving NULL as invented pointer.

void current_height(tree *root, int level){
    if(root == NULL){
        if (level>1){
            current_height(NULL, level - 1);
            current_height(NULL, level - 1);
        }
        else {
            printf("%d, ", 0);
        }
        return;
    }
    if(level == 1){
        printf("%d, ", root->data);
    }
    else if(level > 1){
        current_height(root->left, level - 1);
        current_height(root->right, level - 1);
    }
}

Output here https://www.onlinegdb.com/online_c_compiler is:

5, 
0, 6, 
0, 0, 0, 7, 
0, 0, 0, 0, 0, 0, 0, 9,

CodePudding user response：

First of all, calling current_height on each node (which traverses the whole subtree on that node), makes this algorithm inefficient.

You could use this idea:

• Create an array for storing the current level of nodes. Make sure it is has a size that can contain the bottom level.

• At index 0 store the root reference.

• Then iterate the levels:

• Print the data of the nodes that are currently in the array

• Replace each node with its two children -- or when the node was actually a NULL, put two NULL values in the array.

• To avoid that data is overwritten before it is read, iterate the array from the rightmost filled-in node backwards to index 0, and store the child nodes also from right to left. This way there is no overwriting of parents before they are read.

Here is an implementation:

void level_order(tree *root) {
    int h = height(root) - 1;
    tree *level[1<<h];
    level[0] = root;
    for (int depth = 0; depth <= h; depth  ) {
        for (int j = (1<<depth) - 1; j >= 0; j--) {
            tree *node = level[j];
            int isNode = node != NULL;
            printf("%d, ", isNode ? node->data : 0);
            if (depth < h) {
                level[2*j 1] = isNode ? node->left : NULL; 
                level[2*j] = isNode ? node->right : NULL; 
            }
        }
        printf("\n");
    }
}

Note that your height function returns the number of levels in the tree. The standard definition of "height" is the length of the path from root to its furthest leaf, expressed in number of edges (see Wikipedia). So a tree with just one node has height 0, and an empty tree (NULL) has height -1. This is why the above code subtracts 1 from the value that the height() call returns.