الفنون رقم 015

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

الفنون 015

هذه المادة 15

سؤال خوارزمية الخوارزمية

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

الفرق بين العودية والتكرار: العودية: تقنية البرمجة التي يطلق فيها البرنامج على نفسه اسم العودية التكرار: استخدم القيمة الأصلية للمتغير لحساب قيمة جديدة للمتغير. التكرار يعني أن A يستمر في الاتصال بـ B.

أمثلة على قصة الفيلم: التكرار - “حافة الغد” العودية - “البداية”

参见：
https://blog.csdn.net/laoyang360/article/details/7855860
Google：递归 迭代
斐波那契数列为:0,1,1,2,3,5...
//迭代实现斐波那契数列  
long fab_iteration(int index)  
{  
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        long f1 = 1L;  
        long f2 = 1L;  
        long f3 = 0;  
        for(int i = 0; i < index-2; i++)  
        {     
            f3 = f1 + f2; //利用变量的原值推算出变量的一个新值  
            f1 = f2;  
            f2 = f3;  
        }  
         return f3;  
    }  
}  
  
//递归实现斐波那契数列  
 long fab_recursion(int index)  
 {      
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值  
    }  
} 

اجتياز الطلب المسبق: العقدة الجذرية —> الشجرة الفرعية اليسرى —> الشجرة الفرعية اليمنى الاجتياز بالترتيب: الشجرة الفرعية اليسرى —> العقدة الجذرية —> الشجرة الفرعية اليمنى اجتياز الطلب اللاحق: الشجرة الفرعية اليسرى —> الشجرة الفرعية اليمنى —> العقدة الجذرية

94. اجتياز ترتيب الشجرة الثنائية

الصعوبة: متوسطة

بالنظر إلى شجرة ثنائية، قم بإرجاع اجتياز inorder لقيم العقد الخاصة بها.

مثال:

**Input:** [1,null,2,3]
   1
    \
     2
    /
   3

**Output:** [1,3,2]```

**متابعة:** الحل العودي أمر تافه، هل يمكنك القيام بذلك بشكل متكرر؟



#### الحل

اللغة: **ج**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
 

// الحل العودي التنفيذ العودي

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    //左子树
    int returnSizeLeft = 0;
    int *left = NULL;
    if(root->left != NULL){
        left= inorderTraversal(root->left, &returnSizeLeft);
    }
    
    //根结点
    
    //右子树
    int returnSizeRight = 0;
    int *right = NULL;
    if(root->right!= NULL){
        right = inorderTraversal(root->right, &returnSizeRight);
    }
    
    *returnSize = returnSizeLeft + returnSizeRight + 1;
    int* traversalResult=(int*)malloc((*returnSize)*sizeof(int));
    
    int index = 0;
    for (int i =0; i<returnSizeLeft; i++) {
        traversalResult[index++] = left[i];
    }
    free(left);
    
    traversalResult[index++] = root->val;
    
    for (int i =0; i<returnSizeRight; i++) {
        traversalResult[index++] = right[i];
    }
    free(right);

    return traversalResult;
}

// الحل التكراري التنفيذ التكراري

//迭代算法 iteratively
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
   struct TreeNode** traversalResult=(struct TreeNode**)malloc(1000*sizeof(struct TreeNode*));
   if (root == NULL) {
       *returnSize = 0;
       return NULL;
   }
   int *result=(int*)malloc(1000*sizeof(int));
   *returnSize = 0;
   
   int index = 0;
   struct TreeNode* p = root;
   
   while (p != NULL || index>0) {
       printf("%d",index);
       while (p != NULL) {
               traversalResult[index++] = p;
               p = p->left;
       }
       if (index >= 1) {
           p = traversalResult[--index];
           result[(*returnSize )++] = p->val;
           p = p->right;
       }
   }
   return result;
}

144. اجتياز الطلب المسبق للشجرة الثنائية

الصعوبة: متوسطة

في حالة وجود شجرة ثنائية، قم بإرجاع اجتياز preorder لقيم العقد الخاصة بها.

مثال:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[1,2,3]`

متابعة: الحل العودي أمر تافه، هل يمكنك القيام بذلك بشكل متكرر؟

الحل

اللغة: ج

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

//iteratively solution 迭代解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
        if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int * result = (int *)malloc(sizeof(int) * (1000));
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
   
    struct TreeNode* p=root;
    *returnSize = 0;
    int stackIndex = 0;
   
    while (p || stackIndex > 1) {
    
        result[(*returnSize)++] = p->val;
        
        if (p->right) {
            stack[stackIndex++]=p->right;
        }
        
        p = p->left;
        
        if (stackIndex > 0&&!p) {
             p = stack[--stackIndex];
        }
    }
    
    
    return result;
}

//recursive solution 递归解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        * returnSize = 0;
        return NULL;
    }
    
    //左节点
    int leftSize =  0;
    int *left = NULL;
    if(root->left){
       left =  preorderTraversal(root->left, &leftSize);
    }
    
    //右节点
    int rightSize =  0;
    int *right = NULL;
    if(root->right){
       right =  preorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize + 1;
    int * result = (int *)malloc(sizeof(int) * (*returnSize));
    
    
    int index = 0;
    
    //根节点
    result[index++] = root->val;
    
    //左节点
    for (int i =0; i<leftSize; i++) {
        result[index++] = left[i];
    }
    free(left);
    
    //右节点
    for (int i =0; i<rightSize; i++) {
        result[index++] = right[i];
    }
    free(right);
    
    return result;
}

145. اجتياز الشجرة الثنائية بعد الطلب

الصعوبة: صعب

في حالة وجود شجرة ثنائية، قم بإرجاع اجتياز postorder لقيم عقدها.

مثال:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[3,2,1]`

متابعة: الحل العودي أمر تافه، هل يمكنك القيام بذلك بشكل متكرر؟

الحل

اللغة: ج

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

////迭代实现 iteratively solution
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int *)malloc(sizeof(int) * 1000);
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    
    * returnSize  = 0;
    int stackIndex = 0;
    int *flag = (int *)malloc(sizeof(int) * 1000);//用来标记是否是第二次访问这个节点
    
    struct TreeNode* p = root;

    while (p || stackIndex > 1) {
        if (p) {
            int dex = stackIndex++;
            stack[dex] = p;
            flag[dex] = 1;
            
        }
        
        if (p->right) {
            int dex = stackIndex++;
            stack[dex] = p->right;
            flag[dex] = 0;
        }
        
        p = p->left;
        if (!p && stackIndex > 0) {
            int loop =1;
            while (loop && stackIndex>0) {
                int index = --stackIndex;
                p = stack[index];
                if (flag[index] == 1) {
                    result[(*returnSize)++] = p->val;
                    loop = 1;
                }
                else{
                    loop =0;
                }
            }
            if (stackIndex==0) {
                return result ;
            }
        }
    }
    return result;
}

//递归实现 Recursive solution
int* postorderTraversal_1(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int *left = NULL;
    int leftSize = 0;
    if (root->left) {
        left = postorderTraversal(root->left, &leftSize);
    }
    
    int *right = NULL;
    int rightSize = 0;
    if (root->right) {
        right = postorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize  + 1;
    int *result =  (int *)malloc(sizeof(int) * (*returnSize));
    int index = 0;
   
    for (int i = 0; i < leftSize; i++) {
        result[index++] = left[i];
    }
    
    for (int i = 0; i < rightSize; i++) {
        result[index++] = right[i];
    }
    
    result[index] = root->val;
    
    free(left);
    free(right);
    
    
    return result;
}

مراجعة

المراجعة كمقالة وحدها: https://dandan2009.github.io/2018/11/17/accelerating-your-coding-skills/

نصائح

هذا الأسبوع، دعونا نفرز المفاهيم المتعلقة بالأشجار الثنائية.

بعض المفاهيم المتعلقة بالأشجار الثنائية:

الشجرة الثنائية هي بنية شجرة تحتوي كل عقدة فيها على فرعين على الأكثر (أي لا توجد عقد ذات درجة فرع أكبر من 2). عادةً ما تسمى الفروع “الشجرة الفرعية اليسرى” أو “الشجرة الفرعية اليمنى”. فروع الشجرة الثنائية لها ترتيب يمين ويسار ولا يمكن عكسها حسب الرغبة. يحتوي المستوى i للشجرة الثنائية على 2^i-1 على الأكثر

تختلف عن الأشجار العادية عدد العقد في الشجرة العادية لا يقل عن 1، في حين أن عدد العقد في الشجرة الثنائية يمكن أن يكون 0؛ لا يوجد حد لدرجة التفرع القصوى لعقدة الشجرة العادية، في حين أن الحد الأقصى لدرجة التفرع لعقدة الشجرة الثنائية هو 2؛ عقد الشجرة العادية ليس لها ترتيب يسار أو يمين، في حين أن عقد الشجرة الثنائية لها ترتيب يسار أو يمين.

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

الأشجار الثنائية ليست حالة خاصة من الأشجار على الرغم من وجود العديد من أوجه التشابه بين مفاهيم الأشجار والأشجار الثنائية، إلا أنهما بنيان مختلفان للبيانات. لأنه من التعريف: الشجرة الثنائية ليست شجرة ذات شجرتين فرعيتين فقط ولا شجرة بها شجرتان فرعيتان على الأكثر. الفرق الرئيسي بين الشجرة والشجرة الثنائية هو أن الشجرة الفرعية للعقدة في الشجرة الثنائية يجب أن تميز بين الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى. حتى لو كانت العقدة تحتوي على شجرة فرعية واحدة فقط، فيجب تحديد ما إذا كانت الشجرة الفرعية هي الشجرة الفرعية اليسرى أو الشجرة الفرعية اليمنى بوضوح. أما بالنسبة للشجرة، بغض النظر عن عدد الأشجار الفرعية التي تحتوي عليها، فإن حالة كل شجرة فرعية هي نفسها، على عكس الشجرة الثنائية حيث يتم التمييز بين اليسار واليمين.

الشجرة الثنائية هي شجرة مرتبة خاصة: تحتوي كل عقدة على فرعين على الأكثر (العقد الفرعية)، والفروع لها ترتيب يسار ويمين ولا يمكن عكسها. شجرتان ثنائيتان خاصتان: شجرة ثنائية كاملة: باستثناء الطبقة الأخيرة، إذا كانت جميع الطبقات الأخرى ممتلئة، وكانت الطبقة الأخيرة إما ممتلئة، أو تفتقد عدة عقد متتالية على اليمين (لاحظ أنها على اليمين، وليس على اليسار). شجرة ثنائية كاملة: كل مستوى ممتلئ (باستثناء المستوى الأخير، حيث يشير المستوى الأخير إلى العقدة الطرفية).

يمكن تخزين الأشجار الثنائية باستخدام المصفوفات أو القوائم المرتبطة. إذا كانت الشجرة الثنائية ممتلئة، فيمكن ترتيبها بشكل مضغوط دون إضاعة المساحة. إذا كان فهرس العقدة هو i، (على افتراض أن فهرس العقدة الجذرية هو 0)، فسيكون فهرس العقدة الفرعية اليسرى 2i+1، وسيكون فهرس العقدة الفرعية اليمنى 2i+2؛ والعقدة الأصلية (إذا كانت موجودة) ستحتوي على الفهرس $\frac{i-1}{2}$. يعد هذا الأسلوب أكثر ملاءمة للتخزين المدمج وتحسين موقع الوصول، خاصة في اجتياز الطلب المسبق. ومع ذلك، فهي تتطلب مساحة تخزين مستمرة، لذلك سيتم إهدار مساحة كبيرة عند تخزين شجرة عامة مكونة من n عقد بارتفاع h. في أسوأ الحالات، إذا كانت كل عقدة من الشجرة الثنائية ذات العمق h تحتوي على طفل مناسب فقط، فيجب أن تشغل بنية التخزين مساحة 2^h - 1. في الواقع، هناك عقد h، والتي تهدر الكثير من المساحة وهي عيب كبير في بنية التخزين التسلسلي.

شجرة ثنائية كاملة مخزنة في مصفوفة

العمق الأول للاجتياز في أولوية العمق، نريد الوصول إلى أبعد عقدة من العقدة الجذرية. وبخلاف البحث عن العمق أولاً في الرسم البياني، ليست هناك حاجة لتذكر كل عقدة تمت زيارتها، لأنه لن تكون هناك دورات في الشجرة. الطلب المسبق وحسب الطلب والطلب اللاحق كلها حالات خاصة من اجتياز العمق أولاً. انظر البحث العميق أولاً.

** اجتياز العرض الأول ** على عكس اجتياز العمق أولاً، يقوم اجتياز العرض أولاً بزيارة العقد الأقرب إلى العقدة الجذرية أولاً. انظر بحث العرض الأول. يُطلق على اجتياز العرض الأول للشجرة الثنائية أيضًا اسم اجتياز المستوى تلو الآخر. يتم تنفيذ الخوارزمية بمساعدة قوائم الانتظار.

شجرة ثنائية التعريف: الشجرة الثنائية t عبارة عن مجموعة من العناصر المحدودة (يمكن أن تكون فارغة). عندما لا تكون الشجرة الثنائية فارغة، يوجد عنصر يسمى الجذر، وتتكون العناصر المتبقية (إن وجدت) من شجرتين ثنائيتين، تسمى الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى لـ t على التوالي.

الفرق الأساسي بين الشجرة الثنائية والشجرة هو:

يمكن أن تكون الأشجار الثنائية فارغة، لكن لا يمكن أن تكون الأشجار فارغة. يحتوي كل عنصر في الشجرة الثنائية على شجرتين فرعيتين بالضبط (قد تكون إحداهما أو كلتيهما فارغة). يمكن أن يحتوي كل عنصر في الشجرة على عدة أشجار فرعية. في الشجرة الثنائية، يتم ترتيب الأشجار الفرعية لكل عنصر، أي أنه يمكن تمييزها عن طريق الأشجار الفرعية اليمنى واليسرى. الأشجار الفرعية للشجرة غير مرتبة. يوضح الشكل أدناه شجرة ثنائية تمثل تعبيرًا رياضيًا. هناك ما مجموعه 3 تعبيرات رياضية. يمكن أن يكون لكل عامل معامل واحد أو اثنين، المعامل الأيسر هو الشجرة الفرعية اليسرى للمشغل، والمعامل الأيمن هو الشجرة الفرعية اليمنى. العقد الورقية في الشجرة هي ثوابت أو متغيرات.

خصائص الأشجار الثنائية الخاصية 1: عدد حواف الشجرة الثنائية التي تحتوي على عناصر n (n>0) هو n-1.

أثبت أن كل عنصر في الشجرة الثنائية (باستثناء العقدة الجذرية) له عقدة أصل واحدة بالضبط. توجد حافة واحدة فقط بين العقدة الفرعية والعقدة الأصلية، وبالتالي فإن عدد الحواف هو n-1.

يشير ارتفاع أو عمق الشجرة الثنائية إلى عدد مستويات الشجرة الثنائية.

الخاصية 2: إذا كان ارتفاع الشجرة الثنائية هو h، h≥0، فإن الشجرة الثنائية تحتوي على عناصر h على الأقل وعلى عناصر 2h−1 على الأكثر.

الدليل: بما أن كل مستوى يجب أن يحتوي على عنصر واحد على الأقل، فإن عدد العناصر لا يقل عن h. يحتوي كل عنصر على عقدتين تابعتين على الأكثر، وبالتالي فإن عناصر عقدة الطبقة i تكون على الأكثر 2i-1، i>0. عندما يكون h=0، يكون العدد الإجمالي للعناصر 0، وهو 20−1. عندما h>0، لن يتجاوز العدد الإجمالي للعناصر ∑hi=12i−1=2h−1.

الخاصية 3: الحد الأقصى لارتفاع الشجرة الثنائية التي تحتوي على n من العناصر هو n، والحد الأدنى للارتفاع هو ⌈log2(n+1)⌉.

إثبات نظرًا لوجود عنصر واحد على الأقل في كل مستوى، فلا يمكن أن يتجاوز الارتفاع n. من الخاصية 2، يمكننا أن نعرف أن الشجرة الثنائية ذات الارتفاع h تحتوي على عناصر 2h−1 على الأكثر. لأن n≥2h−1، وبالتالي h≥log2(n+1). بما أن h عدد صحيح، h≥⌈log2(n+1)⌉.

عندما تحتوي الشجرة الثنائية ذات الارتفاع h على عناصر 2h−1 بالضبط، فإنها تسمى شجرة ثنائية كاملة. الصورة أدناه عبارة عن شجرة ثنائية كاملة يبلغ ارتفاعها 4.

افترض أن العناصر الموجودة في شجرة ثنائية كاملة الارتفاع h مرقمة من 1 إلى 2h−1 بالترتيب من الأعلى إلى الأسفل ومن اليسار إلى اليمين، كما هو موضح في الشكل أعلاه. افترض أن عناصر k قد تم حذفها من الشجرة الثنائية الكاملة، وعددها هو 2h−i, 1≤i≥k. تسمى الشجرة الثنائية الناتجة شجرة ثنائية كاملة. تظهر الأشجار الثنائية الثلاثة الكاملة في الشكل أدناه. لاحظ أن الشجرة الثنائية الكاملة هي حالة خاصة من الشجرة الثنائية الكاملة، وعمق الشجرة الثنائية الكاملة التي تحتوي على n من العناصر هو ⌈log2(n+1)⌉.

في الشجرة الثنائية الكاملة، يكون للعنصر توافق جيد جدًا مع عدد أبنائه. العلاقة مذكورة في الخاصية 4 أدناه.

السمة 4: لنفترض أن الرقم التسلسلي لعنصر ما في شجرة ثنائية كاملة هو i، 1≥i≥n. ومن ثم تنشأ العلاقة التالية:

1. عندما يكون i=1، يكون العنصر هو جذر الشجرة الثنائية. إذا كان i>1، فإن رقم العقدة الأصلية للعنصر هو ⌊i/2⌋.
2. عندما يكون العنصر 2i>n، لا يكون للعنصر شجرة فرعية يسرى، وإلا فإن عدد الشجرة الفرعية اليسرى له هو 2i.
3. إذا كان 2i+1>n، فإن العنصر لا يحتوي على الشجرة الفرعية اليمنى، وإلا فإن رقم الشجرة الفرعية اليمنى هو 2i+1.

شجرة ثنائية

1. الشكل الأساسي للشجرة الثنائية:

يتم أيضًا تعريف الأشجار الثنائية بشكل متكرر، وتنقسم عقدها إلى شجرتين فرعيتين يسارية ويمينية. منطقيا، الأشجار الثنائية لها خمسة أشكال أساسية:

(1) شجرة ثنائية فارغة (2) شجرة ثنائية ذات عقدة جذر واحدة فقط (3) الشجرة الفرعية الصحيحة فقط (4) الشجرة الفرعية اليسرى فقط (5) شجرة ثنائية كاملة

ملحوظة: على الرغم من أن الأشجار الثنائية لها العديد من أوجه التشابه مع الأشجار، إلا أن الأشجار الثنائية ليست حالة خاصة من الأشجار.

2. مفهومان مهمان:(1) شجرة ثنائية كاملة - شجرة ثنائية تكون فيها درجات العقد في المستويين السفليين فقط أقل من 2، وتتركز عقد المستوى السفلي في عدة مواضع على الجانب الأيسر الأقصى من المستوى؛ (2) شجرة ثنائية كاملة - شجرة ثنائية تحتوي كل عقدة فيها، باستثناء العقد الورقية، على فلقات يمينية ويسارية، وتكون العقد الورقية جميعها في الأسفل.

3. خصائص الأشجار الثنائية (1) في الشجرة الثنائية، لا يتجاوز العدد الإجمالي للعقد عند المستوى i 2^(i-1)؛ (2) تحتوي الشجرة الثنائية ذات العمق h على 2^h-1 عقدة على الأكثر (h>=1) وعقدة h على الأقل؛ (3) بالنسبة لأي شجرة ثنائية، إذا كان عدد العقد الورقية هو N0 وكان إجمالي عدد العقد من الدرجة 2 هو N2، ثم N0=N2+1؛ (4) عمق الشجرة الثنائية الكاملة ذات العقد n هو int(log2n)+1 (5) إذا تم تخزين عقد شجرة ثنائية كاملة ذات عقد N بطريقة تسلسلية، فإن العقد لها العلاقة التالية: إذا كان I هو رقم العقدة، فإذا كنت <>1، فإن رقم العقدة الأصلية هو I/2؛ إذا كان 2I<=N، فإن عدد الابن الأيسر (أي العقدة الجذرية للشجرة الفرعية اليسرى) هو 2I؛ إذا كان 2I>N، فلا يوجد ابن اليسار؛ إذا كان 2I+1<=N، فإن رقم العقدة لابنه الأيمن هو 2I+1؛ إذا كان 2I+1>N، فلا يوجد ابن صالح. (6) بالنظر إلى العقد N، يمكن تشكيل أشجار ثنائية مختلفة h(N). h(N) هو الحد N من رقم كاتيلان. ح(ن)=C(ن,2*ن)/(ن+1).

شجرة ثنائية كاملة شجرة ثنائية بعمق k و 2 أس (k) - عقدة واحدة. الميزات: عدد العقد في كل مستوى هو الحد الأقصى لعدد العقد.

تعريف الشجرة الثنائية الكاملة: الشجرة الثنائية ذات العقد بعمق k وn تسمى شجرة ثنائية كاملة إذا وفقط إذا كانت كل عقدة من عقدها تتوافق مع عقدة مرقمة من 1 إلى n في شجرة ثنائية كاملة بعمق k. الميزات: يمكن أن تظهر العقد الورقية فقط على المستويين الأكبر؛ بالنسبة لأي عقدة، إذا كان الحد الأقصى لمستوى أحفادها تحت الفرع الأيمن هو l، فيجب أن يكون الحد الأقصى لمستوى أحفادها تحت الفرع الأيسر هو l أو l+1. الشجرة الثنائية الكاملة: شجرة ثنائية بعمق k و2 أس 1 - 1 عقدة. الميزات: عدد العقد في كل طبقة هو الحد الأقصى لعدد العقد. الشجرة الثنائية الكاملة هي بالتأكيد شجرة ثنائية كاملة. الشجرة الثنائية الكاملة ليست بالضرورة شجرة ثنائية كاملة.

لكن شجرة البحث الثنائية لديها مشكلة مزعجة للغاية. إذا تم إدراج بيانات عشوائية في الشجرة، يكون تأثير التنفيذ جيدًا جدًا، ولكن إذا تم إدراج بيانات مرتبة أو عكسية، تصبح سرعة تنفيذ شجرة البحث الثنائية بطيئة جدًا. لأنه عندما يتم ترتيب القيم المدرجة، تكون الشجرة الثنائية غير متوازنة، وتفقد قدرتها على العثور على عناصر البيانات المحددة وإدراجها وحذفها بسرعة.

لحل هذه المشكلة، يمكننا استخدام الشجرة المتعددة.

شجرة 2-3-4 عبارة عن شجرة متعددة، حيث تحتوي كل عقدة على ما يصل إلى أربع عقد فرعية وثلاثة عناصر بيانات. الشجرة 2-3-4، مثل الشجرة ذات اللون الأحمر والأسود، هي أيضًا شجرة متوازنة. كفاءتها أسوأ قليلاً من الشجرة ذات اللون الأحمر والأسود، لكنها أسهل في البرمجة. تشير معاني 2 و3 و4 في اسم الشجرة 2-3-4 إلى عدد العقد الفرعية التي قد تحتوي عليها العقدة. هناك ثلاث حالات محتملة للعقد غير الورقية:

تحتوي العقدة التي تحتوي على عنصر بيانات دائمًا على عقدتين فرعيتين؛ تحتوي العقدة التي تحتوي على عنصري بيانات دائمًا على ثلاث عقد فرعية؛ تحتوي العقدة التي تحتوي على ثلاثة عناصر بيانات دائمًا على أربع نقاط بايت.

شجرة البحث الثنائية، شجرة 2-3-4، شجرة حمراء-سوداء

شجرة ثنائية

مرجع؛ https://zh.wikipedia.org/wiki/二叉树 https://www.cnblogs.com/myjavascript/articles/4092746.html

شارك

كيف تتعلم هياكل البيانات والخوارزميات؟ لقد شاركت هذا مرة من قبل، ورأيت مؤخرًا مقالًا يتوافق تمامًا مع أفكاري. هنا ملخص:

الأساسيات التي تحتاجها قبل الإجابة على الأسئلة

1. هياكل البيانات المشتركة: القوائم المرتبطة، والأشجار (مثل الأشجار الثنائية).
2. أفكار الخوارزمية الشائعة: الطريقة الجشعة، طريقة فرق تسد، الطريقة الشاملة، البرمجة الديناميكية، طريقة التراجع.
3. خوارزميات الفرز الشائعة

إذا كنت لا تعرف حتى هذه الأشياء الأساسية، فستجد صعوبة في حل الأسئلة وسيكون لديك عدد قليل نسبيًا من الأفكار. يمكن القول أنه بالنسبة للعديد من الأسئلة، ستستخدم فقط أساليب القوة الغاشمة، لذلك لا تزال بحاجة إلى إتقان هذه الأشياء الأساسية قبل حل الأسئلة.

يجب عليك أيضًا قراءة الكتب والدراسة بشكل منهجي.

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

بالإضافة إلى leetcode، هناك أيضًا موقع nuke.com والمواقع الإلكترونية التالية لكتابة الأسئلة. 18 موقعًا لممارسة مهاراتك البرمجية [المبرمج العلوي] https://www.topcoder.com/ هاكر ايرث http://www.hackerearth.com/ كودربيت https://coderbyte.com/ مشروع أويلر: https://projecteuler.net/

المرجع: كيف تعلمت هياكل البيانات والخوارزميات؟ :https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ غالبًا ما يتم فقدان محتوى WeChat، إليك نسخة: الرابط الأصلي: https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ

تعتبر حالة هياكل البيانات والخوارزميات أمرًا بديهيًا للمبرمج. مقالة اليوم ليست هنا لتنصحك بتعلم هياكل البيانات والخوارزميات، كما أنها ليست هنا لتخبرك بمدى أهمية هياكل البيانات والخوارزميات.

السبب الرئيسي هو أنه في الأيام القليلة الماضية، سألني القراء كيف تعلمت هياكل البيانات والخوارزميات، وما إذا كان هناك أي اختصارات، سواء لمشاهدة مقاطع الفيديو أو قراءة الكتب، أو أين أدرس الأسئلة، وما إلى ذلك… وبعضهم من الصغار والكبار، لذلك أنا متوتر وقلق عليك…

لذلك سأشارككم اليوم كيف أدرس عادةً.

الطريق المختصر لتعلم الخوارزميات هو الإجابة على المزيد من الأسئلة لأكون صادقًا، عندما يتعلق الأمر بالاختصارات، أعتقد أن الأمر يجب أن يكون واقعيًا وأن تتدرب على المزيد من الأسئلة، وتجيب على المزيد من الأسئلة.

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

بمعنى آخر، إذا كنت تريد الانتقال إلى موقع ويب مثل leetcode للإجابة على الأسئلة، فيجب أن يكون لديك أولاً أساس معين. وتشمل هذه الأسس:

1. هياكل البيانات المشتركة: القوائم المرتبطة، والأشجار (مثل الأشجار الثنائية).

2. أفكار الخوارزمية الشائعة: الطريقة الجشعة، طريقة فرق تسد، الطريقة الشاملة، البرمجة الديناميكية، طريقة التراجع.

تلك المذكورة أعلاه هي الأكثر أساسية. وهذا يعني أنه قبل الإجابة على الأسئلة، يجب عليك مراجعة هذه الأسئلة مرة أخرى ثم الإجابة على الأسئلة. إذا كنت لا تعرف حتى هذه الأشياء الأساسية، فستجد صعوبة في الإجابة على الأسئلة وسيكون لديك عدد قليل نسبيًا من الأفكار.

باختصار، لا تتعجل. راجع هذه الأساسيات أولاً وحاول فهمها قبل الإجابة على الأسئلة. لقد تعلمت هياكل البيانات والخوارزميات الأساسية هذه في الفصل الدراسي الثاني من سنتي الأولى. لم أشاهد الفيديوهات. لقد تعلمتهم من خلال قراءة الكتب. الكتب التي قرأتها في ذلك الوقت كانت:

1. تحليل الخوارزميات وأساسيات التحليل: هذا الكتاب بسيط نسبيًا ويوصى به للمبتدئين.

2. تحليل بنية البيانات والخوارزمية - وصف لغة C: الكود مكتوب بلغة C. يوصى بقراءته.

3. مسابقة برمجة التحدي (الإصدار الثاني): هذا أيضًا كتاب جيد جدًا، موصى به.

وللتفاصيل يمكنك قراءة مقالتي الأخرى التي التعريف بهذه الكتب: كتب الخوارزميات وبنية البيانات وفوائد الفيديو

لأكون صادقًا، قضيت كل وقتي تقريبًا في ذلك الفصل الدراسي في دراسة هياكل البيانات والخوارزميات، ولكن كانت هناك أسئلة قليلة جدًا، فقط بعض الأمثلة من الكتاب. لذا، بعد أن استعرضت هذه الأساسيات، كان لا يزال من الصعب جدًا الانتقال إلى بعض مواقع الويب للإجابة على الأسئلة.

لذلك لا تتوقع أن تظن أنك ستكون جيدًا في الإجابة على الأسئلة بعد تعلم هذه الأفكار. فقط من خلال الإجابة على المزيد من الأسئلة وممارسة المزيد يمكن تحسين حساسيتك.

اسمحوا لي أن أتحدث عن عمود شائع جدًا منذ فترة - [جمال هياكل البيانات والخوارزميات]

لم أشتري هذا العمود. ما أريد قوله هو، إذا اشتريته، يجب عليك قراءته ولا تضيعه. لا تظن أنك ستصبح أكثر روعة بعد تعلم هذا العمود. إذا قمت فقط بمتابعة التقدم المحرز في تعلم هذا العمود، فلن تقضي وقتًا للإجابة على الأسئلة والقيام بوقت عملي. ثم يمكنني أن أضمن أنك ستظل جيدًا فيها بعد الانتهاء من الدراسة.

لتلخيص:

لا يوجد طريق مختصر لتحسين هياكل البيانات والخوارزميات. أفضل اختصار هو الإجابة على المزيد من الأسئلة. ومع ذلك، فإن الشرط الأساسي لحل الأسئلة هو أنه يجب عليك أولاً تعلم بعض هياكل البيانات الأساسية وأفكار الخوارزمية.

السعي لتحقيق الكمال كيفية الإجابة على الأسئلة؟ كيفية التعامل مع مشكلة الخوارزمية؟

أعتقد أنه عند طرح الأسئلة، يجب عليك السعي إلى الكمال. لا تنهي أبدًا سؤالًا، قم بإرساله وتمريره، ثم اندفع إلى السؤال التالي.

هناك علاقة معينة بين تحسين القدرات الخوارزمية وعدد الأسئلة، ولكنها ليست علاقة خطية. وبعبارة أخرى، عند حل مشكلة ما، يجب أن تسعى جاهدة لحل مشاكل متعددة. إذا كنت لا تستطيع حقًا التفكير في طريقة أخرى، فيمكنك الذهاب لترى كيف يفعل الآخرون ذلك. - لا تشعر أنه من العيب تقليد ما يفعله الآخرون.

عندما أقوم بطرح سؤال، عندما أرى سؤالاً، قد تكون فكرتي الأولى هي حله بطريقة بدائية للغاية، لأن العديد من الأسئلة من السهل حلها باستخدام طريقة القوة الغاشمة، ولكن التعقيد الزمني مرتفع جدًا. بعد ذلك، سأفكر في الأمر ببطء وأرى ما إذا كانت هناك طرق أخرى لتقليل تعقيد الوقت أو تعقيد المكان. أخيرًا، سأنظر إلى ما فعله الآخرون. وبطبيعة الحال، لن يتم تنفيذ كل سؤال بهذه الطريقة.

إن قياس جودة مشكلة الخوارزمية ليس أكثر من تعقيد زمني وتعقيد مكاني. لذلك، إذا أردنا أن نسعى إلى الكمال، يجب علينا التقليل من هذين الأمرين وجعلهما يكملان بعضهما البعض.

دعني أعطيك مثالا:

سؤال: يمكن للضفدع أن يقفز خطوة واحدة أو خطوتين في المرة الواحدة. بكم طريقة يمكن للضفدع أن يقفز على سلم المستوى n؟

لقد قمت بتحليل هذا السؤال في الفصول السابقة. إذا لم تفهم، يمكنك قراءة ما كتبته من قبل: التكرار والبرمجة الديناميكية — الفصل الأساسي 1

الأسلوب 1:: العودية العنيفة

هذا السؤال ليس صعبا. ربما ستتبع النهج التالي:

حل ثابت عام (int n) { إذا(ن == 1 || ن == 2){ العودة ن؛ }إلا إذا(ن <= 0){ العودة 0؛ }آخر{ إرجاع حل(ن-1) + حل(ن-2); } }

التعقيد الزمني لهذا النهج مرتفع جدًا وأسي. ولكن إذا نجحت لحسن الحظ بعد الإرسال، ثم انتقلت إلى السؤال التالي، فأنت بحاجة إلى التفكير في الأمر بعناية.

الطريقة الثانية: استبدال المساحة بالوقت

للسعي لتحقيق الكمال، يمكننا أن نفكر في مبادلة المساحة بالوقت: إذا فكرت في هذا السؤال بعناية، ستجد أن الكثير منه يتكرر. لذلك يمكنك اتباع النهج التالي:

// استخدم HashMap لحفظ الحالة المحسوبة خريطة ثابتة <Integer,Integer> Map = new HashMap(); حل ثابت عام (int n) { إذا(ن <= 0)إرجاع 0; وإلا إذا(ن <= 2){ العودة ن؛ }else{//ما إذا كان قد تم حسابه إذا (map.containsKey(n)){ إرجاع Map.get(n); }آخر{ int m = حل(ن-1) + حل(ن-2); Map.put(n, m); عودة م؛ } } }

وبهذه الطريقة، يمكن تقصير الوقت إلى حد كبير. بمعنى آخر، بعد أن تحل مشكلة ما وتجد أن التعقيد الزمني مرتفع جدًا، يمكنك التفكير فيما إذا كانت هناك طريقة أفضل وما إذا كان بإمكانك استبدال المساحة بالوقت.

الطريقة الثالثة: تسلسل فيبوناتشي

في الواقع، يمكننا جعل تعقيد المساحة أصغر ولا نحتاج إلى HashMap لحفظ الحالة:

حل ثابت عام (int n) { إذا (ن <= 0) العودة 0؛ إذا (ن <= 2){ العودة ن؛ }كثافة العمليات f1 = 0; كثافة العمليات f2 = 1؛ مجموع صحيح = 0؛ ل(int i = 1; i<= n; i++){ المجموع = f1 + f2؛ f1 = f2; f2 = المبلغ; } مبلغ الإرجاع؛ }

أعرض عليك هذا السؤال ليس لأعلمك كيفية القيام بذلك، ولكن للأغراض التالية:

1. عند الإجابة على الأسئلة يجب أن نسعى إلى الكمال.

2. لا أستطيع التفكير في هذه الأساليب، ماذا علي أن أفعل؟ ثم يمكنك أن تنظر إلى ما فعله الآخرون. لاحقًا، عندما تواجه مشاكل مماثلة، سيكون لديك المزيد من الأفكار وتعرف الاتجاه الذي يجب أن تفكر فيه.

3. يمكنك البدء بعنف بسيط لحل المشكلة، وتحسينها شيئًا فشيئًا مع مراعاة القياس بين المكان والزمان.

يوصي ببعض المواقع طرح الأسئلة عادةً ما أدرس الأسئلة على Leetcode وNiuke.com، وأشعر أنني بحالة جيدة جدًا. الأسئلة ليست صعبة للغاية.

على موقع Niuke.com، قمت بدراسة عرض Jianzhi بشكل أساسي، ولكن يوجد أيضًا برنامج عبر الإنترنت يسمى Leetcode، ولكن عدد الأسئلة فيه صغير نسبيًا. مكان مناسب جدًا لحل الأسئلة على Niuke.com هو منطقة المناقشة. سيكون هناك العديد من الأشخاص الكبار الذين يشاركون أساليبهم في حل المشكلات، لذلك لا يتعين علينا الذهاب إلى Baidu للعثور على الحل. لذا، بعد الانتهاء منه وعدم قدرتك على التفكير في أي شيء آخر، يمكنك بسهولة الذهاب لترى كيف فعل الآخرون ذلك.

أما بالنسبة إلى leetcode، فإن معظم الأسئلة لها إجابات رسمية، وهو أيضًا موقع جيد لحل الأسئلة. يمكنك اختيار واحد من الاثنين، أو القيام بكليهما.

بالطبع، هناك مواقع ويب أخرى تطرح الأسئلة، لكن بما أنني لم أتصفح المواقع الأخرى، فلا أعرف كيفية مسحها.

دعونا نتحدث عن بنية البيانات لقد تحدثت سابقًا بشكل أساسي عن الطريقة التي أتعلم بها الخوارزميات عادةً. فيما يتعلق بطرق بنية البيانات، ذكرت للتو أنه يجب عليك تعلم القوائم والأشجار المرتبطة (الكومة الثنائية)، ولكن هذه هي الأكثر أساسية ويجب إتقانها قبل الإجابة على الأسئلة. بالنسبة لهياكل البيانات، سأدرج بعضًا من أهمها:

1. القائمة المرتبطة (مثل القائمة المرتبطة ذات الاتجاه الواحد، والقائمة المرتبطة ذات الاتجاهين).

2. الأشجار (مثل الأشجار الثنائية، والأشجار المتوازنة، والأشجار الحمراء والسوداء).

3. الرسم البياني (مثل العديد من الخوارزميات لأقصر المسارات).

4. قائمة الانتظار، المكدس، المصفوفة.

لهذه، يجب عليك تنفيذها بنفسك. يمكنك قراءة الكتب أو مشاهدة مقاطع الفيديو. يمكن للمبتدئين مشاهدة مقاطع الفيديو أولاً، ولكن يمكنك مشاهدة مقاطع الفيديو في المرحلة المبكرة. وبعد ذلك أنصحك بقراءة الكتب.

لقد أوصيت بمقاطع الفيديو والكتب من قبل: كتب الخوارزميات وبنية البيانات وفوائد الفيديو

على سبيل المثال، بالنسبة للشجرة المتوازنة، قد تنساها بعد فترة من اتباع الكود الموجود في الكتاب، لكن لا يهم. على الرغم من أنك نسيت ذلك، إذا كنت قد نفذته باستخدام التعليمات البرمجية من قبل وفهمته، فعندما تراه مرة أخرى، سوف تتذكره بسرعة وتفهم الفكرة بسرعة، وسيتم تحسين قدرتك على التجريد دون وعي. لاحقًا، إذا تعرفت على الأشجار ذات اللون الأحمر والأسود وهياكل البيانات الأخرى، فسوف تتعلمها بسرعة كبيرة.

الأهم افعلها، افعلها، افعلها. قل أشياء مهمة ثلاث مرات.

لا تجد مجموعة من الموارد، ضع خطة دراسية، واترك الأمر ليوم معين للقيام بذلك…

لا تفعل هذا، ولكن عندما يأتي شغفك، افعله على الفور. لا تتركه حتى عطلة أو أيا كان. كثير من الناس الذين يفكرون بهذه الطريقة لن يفعلوا شيئًا في النهاية.

لا تشعر أن هناك الكثير لتتعلمه ولا تعرف من أين تبدأ. كما قلت أعلاه، يمكنك تعلم الأساسيات أولاً، ثم دراسة الأسئلة. ودراسة الأسئلة أمر يحتاج إلى مثابرة طويلة الأمد، سنة أو سنتين. في عملية حل الأسئلة، يمكنك أن تتخلل التعلم من هياكل البيانات الأخرى.