مفهوم الشجرة الثنائية
الشجرة الثنائية هي مجموعة محدودة من العقد N (n> = 0). هذه المجموعة هي إما مجموعة فارغة (شجرة ثنائية فارغة) ، أو تتكون من عقدة الجذر وشجرتين ثنائيتين لا يتقاطعان مع بعضهما البعض ، تسمى عقدة الجذر والشجرة الفرعية اليمنى على التوالي.
خصائص الأشجار الثنائية
تحتوي كل عقدة على أكثر من شقين فرعيين ، لذلك لا توجد عقد بدرجة أكبر من 2 في الشجرة الثنائية. كل عقدة في الشجرة الثنائية هي كائن ، ولكل عقدة بيانات ثلاثة مؤشرات ، وهي مؤشرات للوالد ، الطفل الأيسر والطفل الأيمن. كل عقدة متصلة ببعضها البعض من خلال مؤشر. العلاقة بين المؤشرات المتصلة هي العلاقة بين الأب والابن.
تعريف عقد الأشجار الثنائية
يتم تعريف عقدة الشجرة الثنائية على النحو التالي:
نسخة الكود كما يلي:
هيكلي ثنائية الأبعاد
{
int m_nvalue ؛
BinaryTreeNode* m_pleft ؛
BinaryTreeNode* m_pright ؛
} ؛
خمسة أشكال أساسية من الأشجار الثنائية
شجرة ثنائية فارغة
لا يوجد سوى عقدة جذر واحدة
عقدة الجذر تحتوي فقط على الشجرة الفرعية اليسرى
عقدة الجذر لديها فقط الشجرة الفرعية الصحيحة
تحتوي عقدة الجذر على شجرة فرعية يسار وليمين
لا يوجد سوى حالتان للأشجار العادية مع ثلاث عقد: اثنتين أو ثلاثة. ومع ذلك ، نظرًا لأن الشجرة الثنائية يجب أن تميز اليسار واليمين ، فسوف تتطور إلى الأشكال الخمسة التالية:
شجرة ثنائية خاصة
شجرة مائلة
كما هو موضح في الصور الصغيرة الثانية والثالثة في الصورة الفرعية قبل الأخيرة أعلاه.
شجرة ثنائية كاملة
في شجرة ثنائية ، إذا كانت جميع العقد الفرعية الفرعية اليسرى واليمنى ، وكل الأوراق على نفس الطبقة ، تسمى هذه الشجرة الثنائية شجرة ثنائية كاملة. كما هو مبين في الشكل أدناه:
شجرة ثنائية كاملة
الشجرة الثنائية تمامًا تعني أن الطبقة الأخيرة ممتلئة على اليسار ، وقد يكون الجانب الأيمن ممتلئًا أم لا ، وبقية الطبقات ممتلئة. شجرة ثنائية ذات عمق K وعدد من العقد 2^K - 1 هي شجرة ثنائية كاملة (شجرة ثنائية كاملة). إنها شجرة ذات عمق k وليس هناك مساحة.
خصائص شجرة ثنائية تمامًا هي:
يمكن أن تظهر عقد الأوراق فقط في أدنى طبقتين.
يجب أن تتركز أدنى ورقة في وضع مستمر على اليسار.
في الطبقة قبل الأخيرة ، إذا كانت هناك عقد أوراق ، فيجب أن تكون في مواقع مستمرة على اليمين.
إذا كانت درجة العقدة 1 ، فإن العقدة لديها الطفل الأيسر فقط.
بالنسبة للأشجار الثنائية مع نفس شجرة العقدة ، فإن الشجرة الثنائية الكاملة لديها أصغر عمق.
ملاحظة: يجب أن تكون شجرة ثنائية كاملة شجرة ثنائية تمامًا ، ولكن قد لا تكون شجرة ثنائية تمامًا شجرة ثنائية كاملة.
الخوارزمية كما يلي:
نسخة الكود كما يلي:
Bool IS_COMPLETE (TREE *ROOT)
{
قائمة الانتظار ف ؛
شجرة *PTR ؛
5
Q.Push (الجذر) ؛
بينما ((ptr = q.pop ())! = null)
{
q.push (ptr-> اليسار) ؛
q.push (ptr-> right) ؛
}
// تحديد ما إذا كانت هناك عقد لم يتم الوصول إليها
بينما (! q.is_empty ())
{
ptr = q.pop () ؛
// إذا كانت هناك عقد غير فائقة لا يمكن الوصول إليها ، فإن الشجرة لها فراغ وهي شجرة ثنائية غير مكتملة.
إذا (NULL! = PTR)
{
العودة كاذبة
}
}
العودة صحيح.
}
خصائص الأشجار الثنائية
خاصية 1 من الشجرة الثنائية: هناك على الأكثر 2^(I-1) العقد على الطبقة الأولى من الشجرة الثنائية (i> = 1)
الخاصية 2 من شجرة ثنائية: شجرة ثنائية ذات عمق K لديها على الأكثر 2^K-1 العقد (K> = 1)
بنية التخزين المتسلسلة للأشجار الثنائية
تتمثل هيكل التخزين المتسلسل للشجرة الثنائية في استخدام صفيف أحادي البعد لتخزين كل عقدة في الشجرة الثنائية ، ويمكن أن يعكس موقع تخزين العقد العلاقة المنطقية بين العقد.
قائمة الارتباط الثنائي
نظرًا لأن طريقة التخزين المتسلسلة لا تنطبق بشكل كبير ، يجب علينا النظر في بنية تخزين السلسلة. وفقًا للممارسة الدولية ، يعتمد تخزين الأشجار الثنائية عمومًا هيكل تخزين السلسلة.
كل عقدة من شجرة ثنائية لديها على الأكثر طفلين ، لذلك من الطبيعي تصميم حقل بيانات وحقلتين مؤشرتين لذلك. نسمي هذه القائمة المرتبطة قائمة مرتبطة ثنائية.
اجتياز الأشجار الثنائية
يشير اجتياز الشجرة الثنائية إلى الوصول إلى جميع العقد في الشجرة الثنائية بترتيب معين من عقدة الجذر ، بحيث يتم الوصول إلى كل عقدة مرة واحدة وفقط.
هناك ثلاث طرق لاجتياز الأشجار الثنائية ، على النحو التالي:
(1) اجتياز التمرير المسبق (DLR) ، أولاً الوصول إلى عقدة الجذر ، ثم اجتياز الشجرة الفرعية اليسرى ، وأخيراً اجتياز الشجرة الفرعية اليمنى. جذر مختصر - يسار - يمين.
(2) اجتياز الترتيب (LDR) ، أول اجتياز الشجرة الفرعية اليسرى ، ثم الوصول إلى عقدة الجذر ، وأخيراً اجتياز الشجرة الفرعية اليمنى. ملاحظة مختصرة: اليمين الأيسر.
(3) اجتياز ما بعد الترتيب (LRD) ، والعبور أولاً في الشجرة الفرعية اليسرى ، ثم اجتياز الشجرة الفرعية اليمنى ، وأخيراً الوصول إلى عقدة الجذر. جذر اليمين الأيسر المختصر.
تمريرات الديباجة:
إذا كانت الشجرة الثنائية فارغة ، فإن العملية الفارغة تعود. خلاف ذلك ، قم أولاً بالوصول إلى عقدة الجذر ، ثم اجتاز الشجرة الفرعية اليسرى بالترتيب السابق ، ثم اجتياز الشجرة الفرعية اليمنى بالترتيب السابق.
ترتيب اجتياز هو: عبدهجكفيكج
نسخة الكود كما يلي:
// اجتياز دقيق
وظيفة preorder (العقدة) {
if (! node == null) {
putstr (node.show ()+ "") ؛
preorder (node.left) ؛
preorder (node.right) ؛
}
}
اجتياز الترتيب:
إذا كانت الشجرة فارغة ، فإن العملية الفارغة تُرجع ، وإلا فإنها تبدأ من عقدة الجذر (لاحظ أنه لا يتم الوصول إلى عقدة الجذر أولاً) ، ويتم اجتياز الشجرة الفرعية اليسرى لعقدة الجذر بالترتيب الأوسط ، ثم يتم الوصول إلى عقدة الجذر ، وأخيراً يتم اجتياز الشجرة الفرعية اليمنى في الترتيب الأوسط.
ترتيب اجتياز: hdibejafkcg
نسخة الكود كما يلي:
// استخدم الطريقة العودية لتنفيذ اجتياز الترتيب الأوسط
وظيفة inorder (العقدة) {
if (! (node == null)) {
inorder (node.left) ؛ // أضف إلى الشجرة الفرعية اليسرى أولاً
putstr (node.show ()+ "") ؛ // أضف إلى عقدة الجذر مرة أخرى
inorder (node.right) ؛ // آخر الوصول إلى الشجرة الفرعية اليمنى
}
}
اجتياز ما بعد الترتيب:
إذا كانت الشجرة فارغة ، فإن العملية الفارغة تعود. بخلاف ذلك ، يتم اجتياز المسطحين الفرعيين الأيسر واليسرى من اليسار إلى اليمين للوصول إلى المقطوعين الأيسر والأيمن ، وأخيراً الوصول إلى عقدة الجذر.
ترتيب اجتياز هو: hidjebkfgca
نسخة الكود كما يلي:
// بعد الترتيب
وظيفة postorder (العقدة) {
if (! node == null) {
postorder (node.left) ؛
postorder (node.right) ؛
putstr (node.show ()+ "") ؛
}
}
تنفيذ شجرة البحث الثنائية
تتكون شجرة البحث الثنائية (BST) من العقد ، لذلك نحدد كائن عقدة على النحو التالي:
نسخة الكود كما يلي:
دالة عقدة (البيانات ، اليسار ، يمين) {
this.data = البيانات ؛
this.left = left ؛ // احفظ رابط العقدة اليسرى
this.right = الحق ؛
this.show = show ؛
}
وظيفة العرض () {
إرجاع this.data ؛ // إظهار البيانات المحفوظة في العقدة
}
ابحث عن الحد الأقصى والحد الأدنى للقيم
إن العثور على الحد الأدنى والحد الأقصى للقيم على BST أمر بسيط للغاية ، لأن القيم الأصغر موجودة دائمًا على عقدة الطفل اليسرى ، والبحث عن الحد الأدنى من القيمة على BST ، فقط اجتياز شجرة الطفل اليسرى حتى يتم العثور على العقدة الأخيرة
ابحث عن الحد الأدنى للقيمة
نسخة الكود كما يلي:
وظيفة getMin () {
var current = this.root ؛
بينما (! (current.left == null)) {
الحالي = current.left ؛
}
إرجاع Current.Data ؛
}
تعبر هذه الطريقة واحدة تلو الأخرى على طول الشجرة الفرعية اليسرى من BST حتى تعبر إلى العقدة اليسرى من BST ، والتي يتم تعريفها على أنها:
نسخة الكود كما يلي:
current.left = null ؛
في هذا الوقت ، تكون القيمة المحفوظة على العقدة الحالية هي الحد الأدنى للقيمة
ابحث عن القيمة القصوى
يتطلب إيجاد القيمة القصوى على BST فقط اجتياز الشجرة الفرعية اليمنى حتى يتم العثور على العقدة الأخيرة ، والقيمة المحفوظة على تلك العقدة هي القيمة القصوى.
نسخة الكود كما يلي:
وظيفة getMax () {
var current = this.root ؛
بينما (! (current.right == null)) {
الحالي = current.right ؛
}
إرجاع Current.Data ؛
}