Как mallo c выделяет пространство при вставке значений в двоичное дерево поиска? - PullRequest
Новая
       37

Как mallo c выделяет пространство при вставке значений в двоичное дерево поиска?

0 голосов
/ 09 февраля 2020

ниже приведен простой код для двоичного дерева поиска. Он имеет 2 случая, первый вставляет значения в дерево, а второй находит обход по предварительному порядку дерева.

Мой вопрос касается функции mallo c. В первом случае у нас есть это ptr = (struct node *)malloc(sizeof(struct node));, и давайте скажем, что значение, которое мы хотим вставить, равно 50. Я могу видеть при отладке, что ptr = 50, и я не могу понять, как (struct node *)malloc(sizeof(struct node)) дает этот результат.

Также, когда у нас есть struct node *ptr, *nodeptr, *parentptr как указывающие переменные для структурного узла внутри функции, и после этого у нас есть, например, parentptr=NULL;, это parentptr ссылается на указатель *parentptr или его просто переменную. 

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

struct node* tree;
struct node*
insert(struct node*, int);
void
preorder(struct node*);
int
main()
{
  int option, val;
  struct node* ptr;
  tree = NULL;
  do {
    printf("\n ******MAIN MENU******* \n");
    printf("\n 1. Insert an element");
    printf("\n 2. Preorder Traversal");
    printf("\n 3. Exit");
    printf("\n\n Enter your option : ");
    scanf("%d", &option);

    switch (option) {
      case 1:
        printf("\n Enter the value of the new node : ");
        scanf("%d", &val);
        tree = insert(tree, val);
        break;

      case 2:
        printf("\n The elements of the tree are : \n");
        preorder(tree);
        break;
    }
  } while (option != 3);
  getch();
  return 0;
}

struct node*
insert(struct node* tree, int val)
{
  struct node *ptr, *nodeptr, *parentptr;

  ptr = (struct node*)malloc(sizeof(struct node));
  ptr->data = val;
  ptr->left = NULL;
  ptr->right = NULL;

  if (tree == NULL) {
    tree = ptr;
    tree->left = NULL;
    tree->right = NULL;
  } else {
    nodeptr = tree;
    parentptr = NULL;
    while (nodeptr != NULL) {
      parentptr = nodeptr;
      if (val < nodeptr->data)
        nodeptr = nodeptr->left;
      else
        nodeptr = nodeptr->right;
    }
    if (val < parentptr->data)
      parentptr->left = ptr;
    else
      parentptr->right = ptr;
  }
  return tree;
}

void
preorder(struct node* tree)
{
  if (tree != NULL) {
    printf("%d\t", tree->data);
    preorder(tree->left);
    preorder(tree->right);
  }
}
...