0

У меня есть дерево,размер и количество элементов которого мне заранее не известны,мне необходимо обеспечить консольный ввод этого дерева,но проблема в том,что используя мою функцию root->left=newNode(элемент) при большом количестве элементов,приходиться писать root->left->left->...(при этом невозможно отсеять момент,когда я не ввожу сына,тоесть последовательность на нем должна прекратиться )это очень неудобно.Мне необходимо автоматизировать этот процесс,но вот я никак не могу понять как заменить этот способ. Структура дерева:

struct node
{
int data;
struct node* left;//левый сын
struct node* right;// правый сын
};

Функция,создающая новый узел:

struct node* newNode(int data)
{
struct node* node = (struct node*)
                            malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

Функция,добавляющая новый узел:

struct node* insert(struct node* node, int data) { 
// 1. If the tree is empty, return a new, single node 
if (node == NULL) { 
return(newNode(data)); 
} 
else { 
// 2. Otherwise, recur down the tree 
if (data <= node->data) node->left = insert(node->left, data); 
else node->right = insert(node->right, data);

return(node); // return the (unchanged) node pointer 
} 
} 

Пример дерева:

 /* 
          1
        /   \
      2      3
    /  \    /
  4     5  6
 /
7
*/

Текущая версия ввода:

int counter;
printf("Vvedite kolichestvo uzlov: ");
scnaf("%d",&counter);
int nodarr=(int *)malloc(sizeof(int)*counter);
printf("Vvedite koren`: ");
scanf("%d",&nodarr[0]);
struct node *root = newNode(nodarr[0]);
printf("next %d ");
scanf("next %d",&nodarr[1]);
root->left = newNode(nodarr[1]);
scanf("next %d",&nodarr[2]);
root->right = newNode(nodarr[2]);
printf("next %d ");
scanf("next %d",&nodarr[3]);
root->left->left = newNode(nodarr[3]);
1

1 ответ 1

1

Не нужно вам вводить размер дерева изначально. Само определится :)

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

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

static struct node *newNode(int data)
{
    struct node *newnode = malloc(sizeof(struct node));
    if( newnode ) {
        newnode->data = data;
        newnode->left = NULL;
        newnode->right = NULL;
    }
    return newnode;
}

static struct node *insert(struct node **node, int data)
{
    if( !*node )  {
        *node = newNode(data );
        return *node;
    }
    if( data <= (*node)->data ) {
        return insert( &(*node)->left, data);
    }
    return insert( &(*node)->right, data);
}

/* не очень наглядно, но на скорую руку сгодится */
static void printNode( struct node *node, int level ) {

    if( node ) {
        int i = 0;
        while( i++ < level ) {
            putchar( ' ' );
        }

        printf( "%d\n", node->data );
        printNode( node->left, level+1 );
        printNode( node->right, level+1);
    }
}

int main(void)
{
    int n;
    struct node *root = NULL;

    /* конец - ввод 0 */
    printf( "Enter nodes (0 to end)\n" );
    while( scanf( "%d", &n ) != EOF && n ) {
        if( !insertNode( &root, n ) ) {
            perror( "Node creation" );
            break;
        }
    }
    printNode( root, 0 );
    /* освободить память дерева не забыть */
    return 0;
}
1
  • Спасибо большое,протестировал и добавил проверку на сбалансированность,все работает 18 ноя 2016 в 15:34

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.