Дерево поиска в C


Я начал работать над реализацией для БСТ, просто для себя, чтобы иметь некоторые проекты с. это то, что я сделал до сих пор.

дерево.ч

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

#ifndef MIN
    #define MIN(X, Y) (((X) > (Y)) ? (X) : (Y))
#endif
#ifndef MAX
    #define MAX(X, Y) (((X) < (Y)) ? (X) : (Y))
#endif

typedef struct Node { /* The tree struct */
    int val; /* The value in the node */
    struct Node *l, *r; /* Pointer to the next nodes, l = left r = right */
} Node;

int minDepth (Node *root);
int maxDepth (Node *root);
void printTree (Node *root);
void printTreeValues (Node *root);
int exist (Node *root, int value);
Node *createNode (int value);
void insertNewNumber (Node **root, int value);
int numberOfElements (Node *root);
int isMaxHeap (Node *root);
int maxElement (Node *root);
int minElement (Node *root);
void freeTree (Node *root);

дерево.с

Я не буду постить сюда весь код, так как это немного долго (я буду удалять такие функции, как параметр maxdepth...)

#include "tree.h"

int minDepth (Node *root) /* A recursive function returns the shortests distance from the root node to a leaf */
{
    /* Corner case. Should never be hit unless the code is */
    /* called on root = NULL */
    if (root == NULL)
        return 0;

    /* Base case : Leaf Node. This accounts for height = 1. */
    if (root->l == NULL && root->r == NULL)
       return 1;

    /* If left subtree is NULL, recur for right subtree */
    if (!root->l)
       return minDepth(root->r) + 1;

    /* If right subtree is NULL, recur for left subtree */
    if (!root->r)
       return minDepth(root->l) + 1;

    /* Return the smallest result */
    if (minDepth(root->l) > minDepth(root->r))
        return minDepth(root->r) + 1;
    else if (minDepth(root->l) < minDepth(root->r))
        return minDepth(root->l) + 1;
    else
        return minDepth(root->l) + 1;
}

void printTreeRec (Node *root) { /* A recursive function which prints the tree by given root */
    /* Prints the tree the way it looks */
    if(!root) {
        printf("NULL");
        return; 
    }
    printf("%d (", root->val);
    printTreeRec(root->l);
    printf(",");
    printTreeRec(root->r);
    printf(")");
}
void printTree (Node *root) { /* A recursive function which prints the tree by given root */
    printTreeRec(root);
    printf("\n");
}

void printTreeValuesRec (Node *root) {
    /* In this kind of printing if the tree is also sorted the vals will be printed by up going order */
    if(!root) {
        return; 
    }
    printTreeValuesRec(root->l);
    printf("%d->", root->val);
    printTreeValuesRec(root->r);
}
void printTreeValues (Node *root) {
    printTreeValuesRec(root);
    printf("NULL\n");
}

int exist (Node *root, int value) { /* A function that checks if a node with the value 'value' is in the tree. Returns 1 if he is -1 if he isn't */
    if (!root)
    {
        return -1;
    }
    if (root->val > value)
    {
        return exist(root->l, value);
    }
    else if (root->val < value)
    {
        return exist(root->r, value);
    }
    return 1;
}

Node *createNode (int value) { /* Creating a new node */
    Node *newNode = (Node*) malloc(sizeof(Node)); 
    if (newNode == NULL)
    {
        fprintf(stderr, "Error allocating memory, Exiting\n");
        exit(1);
    }
    newNode->val = value;
    newNode->l = NULL;
    newNode->r = NULL;
    return newNode;
}

void insertNewNumber (Node **root, int value) { /* A function that adds a node to the tree */
    Node *newNode = createNode(value);
    if(!*root) { /* We need to add the number here */
        *root = newNode; 
        return; 
    }
    if ((*root)->val > value) /* (*root)->val is bigger than value so we will go left  */
    {
        insertNewNumber(&(*root)->l, value);
    }
    else if ((*root)->val < value) /* (*root)->val is smaller than value so we will go right  */
    {
        insertNewNumber(&(*root)->r, value);
    }
    else { /* Node with the value value is already exist in the tree */
        free(newNode);
        return;
    }
}

int numberOfElements (Node *root) { /* Count the number of numbers in the tree */
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        return numberOfElements(root->r) + numberOfElements(root->l) + 1;
    }
}

int isMaxHeap (Node *root) { /* Max Heap description http://courses.cs.vt.edu/cs2604/spring02/Notes/C07.Heaps.pdf */
    if (root == NULL)
    {
        return 1;
    }
    else if (root->r != NULL && root->l != NULL)
    {
        if (root->r->val < root->val && root->l->val < root->val) 
        {
            return MIN(isMaxHeap(root->r), isMaxHeap(root->l));
        }
        return -1;
    }
    else if (root->r != NULL)
    {
        if (root->r->val < root->val) 
        {
            return isMaxHeap(root->r);
        }
        return -1;
    }
    else if (root->l != NULL)
    {
        if (root->l->val < root->val) 
        {
            return isMaxHeap(root->l);
        }
        return -1;
    }
    return 1;
}

int minElement (Node *root) {/* A function to find min element in the tree recursively */
    if (root == NULL)
    {
        return INT_MAX;
    }
    else if (root->l != NULL)
    {
        return minElement(root->l);
    }
    else {
        return root->val;
    }
}

void freeTree (Node *root) { /* A function to free the tree recursively */
    if(!root)
        return; 
    freeTree(root->l);
    freeTree(root->r);
    free(root);
}

int main(int argc, char const *argv[])
{
    Node *root = createNode(9);

    insertNewNumber(&root,5);
    insertNewNumber(&root,1);
    printf("%d\n",isMaxHeap(root));
    printTree(root);
    printTreeValues(root);
    printf("%d\n", minElement(root));
    freeTree(root);
    return 0;
}

И, наконец,

Файл Makefile

tree: tree.c
    gcc -Wall -ansi -pedantic tree.c -o tree
clean:
    rm tree

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

Спасибо заранее.



152
1
задан 5 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ

У вас есть способ перемудрил minDepth():

/* 
* A recursive function returns the shortests distance
* from the root node to a leaf
*/
int minDepth (Node *root)
{
if (root == NULL) {
return 0;
}
return 1 + MIN(minDepth(root->l), minDepth(root->r));
}

(но см. Примечания ниже MIN() макрос расширяет свои аргументы несколько раз)

Ваш insertNewNumber() утечка очень плохо. Вы создаете новый узел на каждом вызове. Но только поставив его в дерево под корень.

void insertNewNumber(Node **root, int value)
{
(*root) = insertNewNumberAtLeaf(*root, value);
}
Node* insertNewNumberAtLeaf(Node *root, int value)
{
if (root == NULL) {
return createNode(value);
}
if (root->val > value) {
root->right = insertNewNumberAtLeaf(root->right, value);
}
else {
root->left = insertNewNumberAtLeaf(root->left, value);
}
return root;
}

Я думаю, что твое определение MIN и MAX это неправильно.

#ifndef MIN
#define MIN(X, Y) (((X) > (Y)) ? (X) : (Y))
#endif
#ifndef MAX
#define MAX(X, Y) (((X) < (Y)) ? (X) : (Y))
#endif

Кроме того, если они уже определены, это ОК? Ты думаешь у всех такое же определение, как вы? Если какой-либо из них уже определены, я бы ошибку, а не продолжать.

Я также хотел бы отметить, что эти макросы делают вас вызвать функцию несколько раз.

Взято из кода:

 return MIN(isMaxHeap(root->r), isMaxHeap(root->l));

Это расширяет:

 return (((isMaxHeap(root->r)) > (isMaxHeap(root->l))) ? (isMaxHeap(root->r)) : (isMaxHeap(root->l)));

Компилятор не может взять на себя функция возвращает то же значение каждый раз (если это делать много лишних анализов). Так что это было бы эквивалентно:

 int tmpL = isMaxHeap(root->r);
int tmpR = isMaxHeap(root->l);

// Then call again to get the result.
int rest = (tmpL > tmpR) ? isMaxHeap(root->r) : isMaxHeap(root->l);
return rest;

4
ответ дан 5 марта 2018 в 06:03 Источник Поделиться