اذهب إلى المحتوى

السؤال

نشر

السلام عليكم.

في الكود التالي:

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

// global variables & constants
#define NEXT 2

// represent a tree
typedef struct node
{
    int number;
    struct node* next[NEXT];
    // [0] for left subtree and [1] for the one on right
} node;

// functions prototypes
node* allocate_node(int number);
node* find_parent(node* tree, int number);
bool check(node* tree, int number);

int main(void)
{
    // tree: the root of tree - n: to allocate new memory for nodes
    node* tree = NULL;
    node* n = NULL;

    // array to insert
    const int SIZE = 7;
    const int numbers[SIZE] = {5, 7, 2, 6, 8, 2, 4};

    // insert items automatically
    for (int i = 0; i < SIZE; i++)
    {
        n = allocate_node(numbers[i]);

        // n is the root if tree empty
        if (!tree)
        {
            tree = n;
        }
        else
        {
            // temp holds the address of the right parent of n
            node* temp = find_parent(tree, numbers[i]);

            // insert right or left
            if (numbers[i] > temp->number)
            {
                temp->next[1] = n;
            }
            else
            {
                temp->next[0] = n;
            }
        }
    }

    // try checking x
    int x = 50;
    printf("%sFound\n", check(tree, x) ? "" : "Not ");

    // well done!
    return 1;
}

// func1: allocating new memory
node* allocate_node(int number)
{
    node* new = NULL;
    new = malloc(sizeof(node));
    if (!new)
    {
        exit(0);
    }
    new->number = number;
    for (int i = 0; i < NEXT; i++)
    {
        new->next[i] = NULL;
    }
    return new;
}

// func2: find the parent of a node
node* find_parent(node* tree, int number)
{
    if (!tree)
    {
        return NULL;
    }

    node* temp = tree;
    while (temp->next[0] || temp->next[1])
    {
        if (number > (temp->number))
        {
            if (temp->next[1])
            {
                temp = temp->next[1];
                continue;
            }
            return temp;
        }
        else
        {
            if (temp->next[0])
            {
                temp = temp->next[0];
                continue;
            }
            return temp;
        }
    }
    return temp;
}

// func3: search in BST
bool check(node* tree, int number)
{
    // iterative for goes through the tree
    for (node* temp = tree; temp; )
    {
        // found?
        if (number == temp->number)
        {
            // yeah :)
            return true;
        }

        // go right if target greater than temp->number
        else if (number > (temp->number))
        {
            temp = temp->next[1];
            continue;
        }

        // go left if not
        temp = temp->next[0];
    }

    // not found :(
    return false;
}

كلا دالتي البحث و إيجاد الأب للعقد الجديدة متشابهين لحد كبير. هل يمكن بطريقة أو بأخري تقليل عدد أسطر الكود. أو بمعني اَخر, هل يمكن تخزين الأسطر المتشابهة بين الدالتين في مكان ما ثم أستدعاء تلك الأسطر في كلا الدالتين أو شيئ من هذا القبيل.

Recommended Posts

لا توجد أي إجابات على هذا السؤال بعد

انضم إلى النقاش

يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.

زائر
أجب على هذا السؤال...

×   لقد أضفت محتوى بخط أو تنسيق مختلف.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   جرى استعادة المحتوى السابق..   امسح المحرر

×   You cannot paste images directly. Upload or insert images from URL.

  • إعلانات

  • تابعنا على



×
×
  • أضف...