Creating a binary tree with recursion in C

Question

I tried to use recursion to create a binary tree, but when I type ABD***CE**FG***, the code didn't yield any result. I pressed space key but the code still didn't half. Was the code wrong or my input wrong?

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

typedef struct tree
{
    struct tree *left;
    struct tree *right;
    char val;
}treeNode;
void createTree(treeNode **node)
{
    char value=0;
    value=getchar();
    if(value=='*')
        *node=NULL;
    else
    {
        *node = (treeNode*)malloc(sizeof(treeNode));
        if(!*node)  exit(-1);
        (*node)->val=value;
        createTree(&(*node)->left);
        createTree(&(*node)->right);
    }

}
void preOrder(treeNode *node)
{
    if (node==NULL) return;
    putchar(node->val);
    preOrder(node->left);
    preOrder(node->right);
}
int main() {
    // insert code here...
    treeNode **node;
    createTree(node);
    preOrder(*node);
    return 0;
}

The first instance of undefined behavior in your code is treeNode **node; createTree(node), which passes an uninitialized variable to createTree. — melpomene
– melpomene, Commented Mar 5, 2019 at 16:34
Prefer this: Thing* createThing(void) to this: void createThing(Thing** thing). — n. m. could be an AI
– n. m. could be an AI, Commented Mar 5, 2019 at 16:38
It's the same problem as writing: int *value; scanf("%d", value); instead of int value; scanf("%d", &value);. A classic one. There are tons of duplicates. — Jabberwocky
– Jabberwocky, Commented Mar 5, 2019 at 16:46

bruno · Accepted Answer · 2019-03-06 14:22:10Z

int main() {
    // insert code here...
    treeNode **node;
    createTree(node);
    preOrder(*node);
    return 0;
}

must be

int main() {
    treeNode *node;
    createTree(&node);
    preOrder(node);
    return 0;
}

else in createTree *node = ... write in a non valid location (*node is not set to a valid pointer in main)

your input must be ABD***CEFG***** to finish :

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra b.c
pi@raspberrypi:/tmp $ ./a.out
ABD***CEFG******
ABDCEFGpi@raspberrypi:/tmp $

About your remark :

yes i don't know which one is left which is right

a practical way is to draw the tree.

A very simple way is :

void draw(treeNode *node, int level, char empty)
{
  if (node != NULL) {
    draw(node->right, level+1, '/');
    for (int i = 0; i != level; ++i)
      putchar(' ');
    printf("%c\n", node->val);
    draw(node->left, level+1, '\\');
  }
  else {
    for (int i = 0; i != level; ++i)
      putchar(' ');
    printf("%c\n", empty);
  }
}

if I change main to :

int main() {
    treeNode *node;
    createTree(&node);
    preOrder(node);
    putchar('\n');
    draw(node, 1, ' ');
    return 0;
}

Compilation and execution :

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra b.c
pi@raspberrypi:/tmp $ ./a.out
ABD***CEFG*****
ABDCEFG
   /
  C
    /
   E
     /
    F
      /
     G
      \
 A
   /
  B
    /
   D
    \

The '/' indicates there is nothing on the right and the '\' indicates there is nothing on the left

[edit] Some ways to draw a prettiest tree can be found on C How to “draw” a Binary Tree to the console

I did a mistake on the input, if I use yours being ABD***CE**FG*** the result is :

/tmp % ./a.out
ABD***CE**FG***
ABDCEFG
    /
   F
     /
    G
     \
  C
    /
   E
    \
 A
   /
  B
    /
   D
    \

Collectives™ on Stack Overflow

Creating a binary tree with recursion in C

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related