Двоичное дерево поиска для отображения «Предзаказ», «Заказ» и «Заказ» - PullRequest
Новая
       4

Двоичное дерево поиска для отображения «Предзаказ», «Заказ» и «Заказ»

0 голосов
/ 10 декабря 2018

Я хочу написать программу, которая может построить дерево бинарного поиска и показать
«Предзаказ», «Задание» и «Поступорядочение».

Первый ввод - это количество входных рядов,Начиная со второй строки, каждая строка представляет собой последовательный вход для построения бинарного дерева поиска.

Ввод: 

3
9,5,6,7,1,8,3
22,86,-5,8,66,9
45,3,5,3,8,6,-8,-9

Вывод: 

Preorder: 9 5 1 3 6 7 8
Inorder: 1 3 5 6 7 8 9
Postorder: 3 1 8 7 6 5 9
Preorder: 22 -5 8 9 86 66
Inorder: -5 8 9 22 66 86
Postorder: 9 8 -5 66 86 22
Preorder: 45 3 3 -8 -9 5 8 6
Inorder: -9 -8 3 3 5 6 8 45
Postorder: -9 -8 3 6 8 5 3 45

Вот мой кодобнаружить букву (,) 

int limit,i;
char tree_input[1000];
char *pch;
scanf("%d",&limit);
printf("%d",limit);

for(i=0; i<limit; i++){
    scanf("%s",tree_input);
    pch = strtok (tree_input,",");
    while (pch != NULL){
        printf ("%s\n",pch);
        pch = strtok (NULL, ",");
    }
}

Моя идея состоит в том, чтобы использовать 'pch', чтобы быть деревом

И тогда я понятия не имею с следующим шагом. Это весь мой коддо сих пор.

Вот мой код 

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

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

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

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int data)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(data);

    /* Otherwise, recur down the tree */
    if (data < node->data)
        node->left  = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);

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


void preorder(struct node* root)
{
    if(root == NULL)
        return;
    printf("%d", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(struct node* root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    printf("%d", root->data);
    inorder(root->right);
}

void postorder(struct node* root)
{
    if(root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    printf("%d", root->data);
}

//void change(char a) //change char to int
//{
//    
//    for (char ch = '0'; ch <= '9'; ++ch) {
//      printf("%d\t", ch - '0');
//  }
//}

int main()
{
    int limit,i;
    char tree_input[1000];
    char *pch;
    scanf("%d",&limit);
    printf("%d",limit);

    for(i=0; i<limit; i++)
    {
        scanf("%s",tree_input);
        pch = strtok (tree_input,",");

//        struct node *root = NULL;
//        root = insert(root, 50);
//        insert(root, 30);
//        insert(root, 20);
//        insert(root, 40);
//        insert(root, 70);
//        insert(root, 60);
//        insert(root, 80);

        struct node *root = NULL;
        while (pch != NULL)
        {
            printf ("%s\n",pch);
            pch = strtok (NULL, ",");
            printf("%d\n")
//            if (root == NULL)
//            {
//                root = insert(root, pch);
//            }
        }
    }
    return 0;
}

1 Ответ

0 голосов
/ 10 декабря 2018

Вы могли бы начать с изменения основного и таким образом и работать оттуда. 

int main()
{
    int limit,i, j;
    char *pch;

    struct node* tree;

    printf("Enter the length of the string you will use: ");
    scanf("%d", &limit); // number of keys and delimiters in initial string
    char str[limit];    // array containing the input string

    scanf("%s",str);
    printf("%s",str);

    /* get the first token */
    pch = strtok(str, ",");

    /* walk through other tokens */
    while( pch != NULL ) {
        printf("\n%d", atoi(pch) ); // atoi turns an alphanumeric (char) to an integer
        insert(tree, atoi(pch) );   // insert the integer to the tree

        pch = strtok(NULL, ",");
     } 

     printf("\n");
     printf("Preorder: ");
     preorder(tree);

     printf("\n");
     printf("Postorder: ");
     postorder(tree);

     printf("\n");
     printf("Inorder: ");
     inorder(tree);
     printf("\n");

     return 0;
 }

Конечно, вы никогда не должны определять массив типа "char str [limit];", вы должны использовать malloc.Однако я не уверен, знакомы ли вы с malloc, поэтому я избежал его для ясности.Даже если вы этого не сделаете, я предлагаю вам прочитать об этом (есть много ресурсов в сети, даже здесь) и использовать его.

Некоторые важные моменты:

1) Чтобы использовать strtok (), вам необходимо включить string.h

2) atoi используется для поворотабуквенно-цифровой в целое число.Поскольку у вас изначально есть строка, и вы хотите ввести целые числа в дерево, вы должны преобразовать символы в целые числа

3) Вам нужно поместить часть кода в main в цикл, чтобы иметь возможность вводить больше, чемодно дерево.

...