CODEWITHSUNDEEP
crecursionbinary-treegetchar
Liu
Liu

Reputation: 433

Creating a binary tree with recursion in C

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;
}

Upvotes: 2

Views: 1357

Answers (1)

bruno
bruno

Reputation: 32594

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
    \

Upvotes: 9

Related Questions