Создание бинарного дерева с рекурсией в C - PullRequest
Новая
       20

Создание бинарного дерева с рекурсией в C

1 голос
/ 05 марта 2019

Я пытался использовать рекурсию для создания бинарного дерева, но когда я набрал ABD***CE**FG***, код не дал никакого результата.Я нажал клавишу пробела, но код все еще не наполовину.Был ли код неправильный или мой ввод неправильный? 

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

1 Ответ

8 голосов
/ 05 марта 2019 
int main() {
    // insert code here...
    treeNode **node;
    createTree(node);
    preOrder(*node);
    return 0;
}

должно быть 

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

еще в createTree *node = ... запись в недопустимом местоположении (* узлу не задан правильный указатель в main )

Ваш ввод должен быть ABD***CEFG***** для завершения: 

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

О вашем замечании:

да, я не знаю, какой слева, а какой правый

практический способ - нарисовать дерево.

Очень простой способ: 

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

если я изменю основной на: 

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

Компиляция и исполнение: 

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

«/» означает, что справа ничего нет, а «\» означает, что слева ничего нет

[править] Некоторые способы нарисовать самое красивое дерево можно найти на C Как «нарисовать» двоичное дерево на консоли

Я сделал ошибку на входе, если я использую ваше значение ABD***CE**FG***, результат будет: 

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