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

Binary Search Tree

السؤال

نشر

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

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

#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

  • 0
نشر

وعليكم السلام ورحمة الله وبركاته.

نعم إن دالت find_parent و check متشابهتان إلى حد كبير لأنهما تؤديان نفس العملية الأساسية وهو إجتياز شجرة البحث الثنائية (BST) فكلاهما يبدأ من الجذر (root) ويبدا التحرك يسارا أو يميناً بناء على مقارنة القيمة.

ولكن بالرغم من هذا التشابه فإنهما يستخدمان لهدفين مختلفين تماما:

فدالة check هدفها هو العثور على تطابق تام وهي تسأل هل القيمة X موجودة في الشجرة أم لا وتتوقف إما عند العثور على القيمة وتعيد true أو عند الوصول إلى نهاية فرع فارغ (NULL) وتعيد false.

وأما دالة find_parent هدفها هو العثور على المكان المناسب لإدراج عقدة جديدة وهي تسأل أين يجب أن يتم وضع القيمة X إذا لم تكن موجودة .وإنها لا تبحث عن تطابق بل تبحث عن آخر عقدة في المسار (الأب) التي سيتفرع منها الابن الجديد.

ولذلك فإن محاولة دمجهما مباشرة كما تقول من خلال تخزين الأسطر المتشابهة ستجعل الكود أكثر تعقيدا  وليس أبسط ولن يكون سهل القراءة والفهم  وأيضا ستحتاج إلى إضافة شروط كثيرة أو أعلام (flags) داخل الدالة المشتركة لتقرر ما إذا كانت في وضع البحث أم وضع إيجاد الأب وهذا يتعارض مع مبدأ الفصل بين الاهتمامات (Separation of Concerns) في البرمجة. حيث هذا المبدأ أساسي جدا وهو أن يكون لكل جزء من الكود وظيفة حادة وليس أكثر من وظيفة وذلك لجعل التعديل سهل في المستقبل وعدم إعتماد الأكواد على بعضها البعض .

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

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

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

×   لقد أضفت محتوى بخط أو تنسيق مختلف.   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.

  • إعلانات

  • تابعنا على



×
×
  • أضف...