الأشجار الثنائية (Binary Trees)
تُعتبر الأشجار الثنائية (Binary Trees) أحد أكثر هياكل البيانات الشجرية استخدامًا وتنوعًا في التطبيقات، حيث تتيح لنا الأشجار الثنائية تنظيم البيانات بطريقة تسهل الوصول السريع والفعال إليها، مما يجعلها مثالية للعديد من العمليات الحسابية وعمليات البحث. فما هي الـ Binary Tree وما مميزاتها وما اهم انوعها…!!! وكيف يمكن تنفيذ الشجرة الثنائية (Binary Trees) برمجياً..؟!!
في مقال بعنوان هياكل البيانات الشجرية تكلمنا عن الأشجار (Trees) ، وذكرنا أن لها أنواع متعددة ومنها الأشجار الثنائية (Binary Tree). في هذا المقال سنغطي جميع أساسيات الشجرة الثنائية Binary Tree، وأنواعها و طريقة تنفيذها والعمليات عليها. ولكن قبل متابعة قراءة على هذا المقال ننصح بالإطلاع مقال هياكل البيانات الشجرية (Trees) الذي يشرح المصطلحات المستخدمة في هذا المقال.لنبدأ…
في هذا المقال نتعرف على :
- الشجرة الثنائية Binary Tree.
- مميزات الشجرة الثنائية Binary Tree.
- أنواع الأشجار الثنائية (Binary Tree Types).
- تنفيذ الشجرة الثنائية Binary Tree.
- الاجتياز Traversal والأشجار الثنائية.
الشجرة الثنائية Binary Tree
الشجرة الثنائية (Binary Tree) عبارة عن نوع خاص من هياكل البيانات الشجرية حيث تحتوي كل عقدة على عقدتين فرعيتين على الأكثر. وتكون القيم للعقد في الأشجار الثنائية مرتبة وهو ما يميز الأشجار الثنائية عن الأشجار العادية. ويوضح الشكل التالي الفرق بين الشجرة العادية والشجرة الثنائية Binary tree..
في الـ Binary Tree يمكن أن تحتوي كل عقدة في الشجرة الثنائية على عقدتين فرعيتين على الأكثر ما يعني أنه يمكن أن تحتوي كل عقدة على عقدة فرعية واحدة أو عقدتين فرعيتين أو لا شيء. فإذا كانت العقدة ليس لديها أي عقدة فرعية فإنها تسمى عقدة ورقية (Leaf Node)، وإذا كان للعقدة فرع واحد فإنها تسمى العقدة الأحادية (Unary Node).
أما إذا كانت العقدة لديها عقدتين فإنها تسمى عقدة ثنائية (Binary Node).و يُطلق على العقدة الفرعية اليسرى اسم الطفل الأيسر (The Left Child )، والعقدة الفرعية اليمنى الطفل الأيمن (The Right Child).
بمعنى أن الشجرة الثنائية Binary Tree هي بنية بيانات شجرية تحتوي كل عقدة فيها على عقدتين فرعيتين (Child Nodes) على الأكثر، ويتم استخدام الأشجار الثنائية لتخزين البيانات واسترجاعها بكفاءة، مع عمليات مختلفة مثل الإدراج والحذف والاجتياز وغيرها..
مميزات الشجرة الثنائية Binary Tree
من بين أنواع هياكل البيانات الشجرية تتميز الأشجار الثنائية Binary Trees بمجموعة من المميزات، نستعرض فيما يلي البعض منها:
- في الشجرة الثنائية (Binary Tree) العدد الأقصى لعدد العُقد عند مستوى معين (L) يساوي 2 مرفوعة للأس هذا المستوى، على سبيل المثال :
عقدة الجذر عند المستوى صفر (Level 0) بالتالي عدد العقد يساوي 1 ، لأن : 20 = 1.
عدد العُقد عند المستوى الأول (Level 1) يكون : 21 = 2.
وعدد العُقد عند المستوى الثاني (Level 2) يكون : 22 = 4…….وهكذا . - في الشجرة الثنائية Binary Tree يحسب الحد الأقصى لعدد العُقد عند ارتفاع معين (h) من المعادلة التالية : 2h-1
وتحتوي الشجرة الثنائية على الحد الأقصى من العقد إذا كانت جميع المستويات لها الحد الأقصى من العقد، لذا فإن الحد الأقصى لعدد العقد في الشجرة الثنائية التي يبلغ ارتفاعها h هو:
1+2+4.........2h-1
هذه سلسلة بسيطة ذات حدود h ومجموع هذه السلسلة هو 2h-1 .
ننوه في بعض الكتب، يعتبر ارتفاع الجذر 0، وفي هذه الحالة تصبح صيغة المعادلة أعلاه على الشكل التالي: 2(h+1)-1. - في الشجرة الثنائية ذات عدد العُقد N، يحسب الحد الأدنى المحتمل للارتفاع (Height ) أو الحد الأدنى لعدد المستويات(levels) بواسطة المعادلة : log2(N+1)
كل مستوى يجب أن يحتوي على عنصر واحد على الأقل، لذلك لا يمكن أن يكون الارتفاع أكثر من N. - في الشجرة الثنائية (Binary Tree) ذات عدد الأوراق (L) يحسب الحد الأدنى لعدد المستويات بواسطة |log2L| +1.
تحتوي الشجرة الثنائية على الحد الأقصى لعدد الأوراق (والحد الأدنى لعدد المستويات) عند امتلاء جميع المستويات بالكامل. فيكون
الحد الأقصى لعدد الأوراق : L <= 2l-1 (هذا باعتبار مستوى عقدة الجذر =0)
الحد الأدنى لعدد المستويات : l = |log2L| +1. - في الشجرة الثنائية Binary Tree التي يكون لكل عقدة فيها 0 أو طفلين، سيكون عدد العقد الورقية دائمًا أكثر بواحد من العقد الداخلية التي تحتوي على طفلين:
L= T+ 1 حيث :
L = عدد العقد الورقية.
T = عدد العقد الداخلية التي بها طفلين.
أنواع الأشجار الثنائية (Binary Tree Types )
تعتبر الأشجار الثنائية (Binary Trees) من أهم أنواع هياكل البيانات الشجرية (Trees data Structure) فهي تتضمن أشكال عدة من هياكل البيانات الشجرية، ويمكن تصنيف الشجرة الثنائية إلى أنواع متعددة بناءً على عوامل متعددة، مثلاً :
- يمكن تصنيف أنواع الأشجار الثنائية Binary Tree على أساس عدد العقد الفرعية (Child Nodes).
- يمكن تصنيف أنواع الأشجار الثنائية Binary Tree على أساس المستويات (Levels).
- يمكن تصنيف أنواع الأشجار الثنائية Binary Tree على أساس قيم العقد (Nodes values).
تصنيف أنواع الأشجار الثنائية Binary Tree على أساس عدد العقد الفرعية (Child Nodes)
يكون تصنيف أنواع الأشجار الثنائية Binary Tree على أساس عدد العقد الفرعية (Child Nodes) ، كتالي:
- أشجار ثنائية ممتلئة (Full Binary Trees).
- أشجار ثنائية متدهورة أو مرضية (Degenerate Binary Trees).
- الأشجار الثنائية المنحرفة (Skewed Binary Trees).
في الشكل التالي تمثيل لأنواع الأشجار الثنائية على أساس عدد العُقد الفرعية:
أشجار ثنائية ممتلئة (Full Binary Trees)
الأشجار الممتلئة (Full Binary Trees) هي نوع خاص من الأشجار الثنائية حيث تحتوي كل عقدة أصل أو عقدة داخلية إما على طفلين أو لا تحتوي على أي طفل. وتُعرف أيضًا باسم الشجرة الثنائية المناسبة (Proper Binary Tree).
أي تكون الشجرة الثنائية شجرة ممتلئة إذا كان لكل عقدة 0 أو 2 من العُقد الفرعية . يمكننا أيضًا أن نقول أن الشجرة الثنائية ممتلئة Full binary tree هي شجرة ثنائية تحتوي فيها جميع العقد باستثناء العقد الورقية على طفلين. وهذا يعني أنه لا توجد عقد أحادية في الشجرة الثنائية الممتلئة Full binary tree.
أشجار ثنائية متدهورة أو مرضية (Degenerate Binary Trees)
في هذا النوع من الأشجار الثنائية تحتوي كل عقدة داخلية على فرع واحد أي أن جميع العُقد في الـ Degenerate Binary Trees هي عقد أحادية (Unary node). ويكون مسار العقدة في الشجرة المتدهورة أو المرضية واحد إما يسارًا أو يمينًا (only left or right child). و تعتبر هذه الأشجار من حيث الأداء مثل القائمة المرتبطة Linked List .
الأشجار الثنائية المنحرفة (Skewed Binary Trees)
الشجرة الثنائية المنحرفة Skewed Binary Trees هي شجرة مرضية/متدهورة ولكن تنحرف العقد للشجرة باتجاة واحد إما باتجاه اليسار( عقد يسرى) باتجاه اليمين (عقد يمنى) . وبالتالي، هناك نوعان من الشجرة الثنائية المنحرفة Skewed Binary Trees:
- الشجرة الثنائية المنحرفة إلى اليسار (Left-skewed binary tree): كل العقد المتفرعه تكون جهة اليسار.
- الشجرة الثنائية المنحرفة إلى اليمين (Right-skewed binary tree): كل العقد المتفرعه تكون جهة اليمين.
تصنيف أنواع الأشجار الثنائية Binary Tree على أساس المستويات (Levels)
يكون تصنيف أنواع الأشجار الثنائية Binary Tree على أساس المستويات (Levels)، كتالي:
- أشجار ثنائية كاملة (Complete Binary Trees).
- أشجار ثنائية مثالية ( Perfect Binary Trees).
- أشجار ثنائية متوازنة ( Balanced Binary Trees).
في الشكل التالي تمثيل لأنواع الأشجار الثنائية على أساس المستويات Levels:
أشجار ثنائية كاملة (Complete Binary Trees)
الشجرة الثنائية هي شجرة ثنائية كاملة (Complete Binary Trees) إذا كانت جميع المستويات مملوءة بالكامل باستثناء المستوى الأخير والذي يمكن ملؤه جزئيًا.وهذا يعني أنه لا توجد فجوات في الشجرة وأن جميع العقد الداخلية متصلة بالعقد الأصلية.
الشجرة الثنائية الكاملة (Complete Binary Trees) تشبه الشجرة الثنائية الممتلئة (Full Binary Trees) ولكن مع وجود اختلافين رئيسيين:
- في الشجرة الثنائية الكاملة (Complete Binary Trees) يجب ملء كل مستوىبالكامل باستثناء المستوى الأخير .
- الشجرة الثنائية الكاملة (Complete Binary Trees) يجب أن تميل جميع عناصر الأوراق نحو اليسار.
وقد لا يكون لعنصر الورقة الأخير شقيق مناسب، أي أن الشجرة الثنائية الكاملة (Complete Binary Trees) لا يجب أن تكون شجرة ثنائية ممتلئة (Full Binary Trees).
أشجار ثنائية مثالية ( Perfect Binary Trees)
الشجرة الثنائية المثالية هي نوع من الأشجار الثنائية Perfect Binary Tree حيث تحتوي كل عقدة داخلية على عقدتين فرعيتين بالضبط وتكون جميع العقد الورقية في نفس المستوى.
في الشجرة الثنائية المثالية ( Perfect binary tree)، عدد العقد الورقية (Leaf nodes) هو عدد العقد الداخلية (internal nodes) زائد 1 فإذا كان :
L = عدد العقد الطرفية (leaf nodes).
I = عدد العقد الداخلية ( internal nodes).
فإن:
l +1 = L
أشجار ثنائية متوازنة (Balanced Binary Trees)
تكون الشجرة الثنائية متوازنة Balanced Binary Tree إذا كانت تحافظ على توازن معين بين العُقد ارتفاع الشجرة حيث لابد أن يكون ارتفاع الشجرة هو O(Log n) حيث n هو عدد العقد. في هذا النوع من الأشجار الثنائية يكون الفرق بين ارتفاع الشجرة الفرعية اليسرى واليمنى لكل عقدة إما 0 أو 1.فمثلاً :
- تحافظ شجرة AVL على ارتفاع O(Log n) عن طريق التأكد من أن الفرق بين ارتفاعات الشجرتين الفرعيتين اليسرى واليمنى هو 1 على الأكثر.
- وتحافظ الأشجار ذات اللون الأحمر والأسود على ارتفاع O(Log n) عن طريق التأكد من أن الرقم عدد العقد السوداء على كل مسارات الجذر إلى الورقة هو نفسه ولا توجد عقد حمراء مجاورة.
الأشجار المتوازنة هي نوع الأشجار الثنائية التي يكون الفرق بين ارتفاع الشجرة الفرعية اليسرى واليمنى لكل عقدة إما 0 أو 1. في الشكل أعلاه، الشجرة الثنائية التي لها فارق العمق 2 بين الفرع اليمن والايسر شجرة غير متوازنة . وتعتبر أشجار البحث الثنائية المتوازنة جيدة من حيث الأداء لأنها توفر وقت O(log n) للبحث والإدراج والحذف.
تصنيف أنواع الأشجار الثنائية Binary Tree على أساس قيم العقدة (Node)
يكون تصنيف أنواع الأشجار الثنائية Binary Tree على أساس قيم العقدة (Node) ، كتالي:
- شجرة البحث الثنائية (Binary Search Tree).
- شجرة AVL ( AVL Tree).
- شجرة حمراء سوداء (Red Black Tree).
- شجرة الشرائح ( Segment Tree).
شجرة البحث الثنائية Binary Search Tree
شجرة البحث الثنائية Binary Search Tree أشهر نوع من الأشجار الثنائية وهي شجرة ثنائية تعتمد في ترتيب العُقدة على مقارنة قيمة العقدة مع بقية العُقد الموجودة فتتبع بعض القواعد في ذلك وهي :
- أن تحتوي الشجرة الفرعية اليسرى للعقدة فقط على العقد التي تحتوي على قيم أقل من قيمة العقدة الجذر.
- أن تحتوي الشجرة الفرعية اليمنى للعقدة فقط على العقد التي تحتوي على قيم أكبر من قيمة العقدة الجذر.
وبهذا يجب أن تكون كل من الشجرة الفرعية اليسرى واليمنى أيضًا شجرة بحث ثنائية.
شجرة AVL
شجرة AVL عبارة عن شجرة بحث ثنائية (BST) ذاتية التوازن حيث لا يمكن أن يكون الفرق بين ارتفاعات الأشجار الفرعية اليمنى واليسرى أكثر من ارتفاع واحد لجميع العقد. في المثال على شجرة AVL في الشكل نرى أن الاختلافات بين ارتفاعات الأشجار الفرعية اليسرى واليمنى لكل عقدة أقل من أو تساوي 1.
شجرة حمراء سوداء (Red Black Tree)
الشجرة ذات اللون الأحمر والأسود هي نوع من شجرة البحث الثنائية ذاتية التوازن حيث تحتوي كل عقدة على بت (Bit) إضافي، وغالبًا ما يتم تفسير هذا bit على أنه اللون (أحمر أو أسود). تُستخدم هذه الألوان لضمان بقاء الشجرة متوازنة أثناء عمليات الإدراج والحذف.
وعلى الرغم من أن توازن الشجرة هنا ليس مثاليًا، إلا أنه جيد بما يكفي لتقليل وقت البحث والحفاظ عليه عند وقت O(log n)، حيث n هو إجمالي عدد العناصر في الشجرة.
في الأشجار ذات اللون الأحمر والأسود، والمعروفة أيضًا باسم أشجار RB، هناك شروط مختلفة يجب اتباعها أثناء تعيين الألوان للعقد.
- تكون العقدة الجذرية دائمًا سوداء اللون.
- لا يجب أن تكون العقدتين المتجاورتين باللون الأحمر.
- يجب أن يحتوي كل مسار في الشجرة (من العقدة الجذرية إلى العقدة الورقية) على نفس الكمية من العقد ذات اللون الأسود.
إن أشجار AVL أكثر توازناً من أشجار RB، حيث تكون خوارزمية التوازن في أشجار AVL أكثر صرامة من خوارزمية أشجار RB، فإن عمليات الإدراج والحذف المتعددة والأسرع تتم بشكل أكثر كفاءة من خلال أشجار RB.والشكل التالي يوضح ترتيب القيم في شجرة بحث ثنائية(BST) و لأشجار بحث ثنائية من الأنواع AVL , و RB:
شجرة المقطع ( Segment Tree)
شجرة الشرائح أو المقاطع Segment Tree، والمعروفة أيضًا باسم الشجرة الإحصائية (Statistic Tree)، هي بنية بيانات شجرية تستخدم لتخزين معلومات حول الفواصل الزمنية أو المقاطع. وتسمح بالاستعلام عن الأجزاء المخزنة التي تحتوي على نقطة معينة.
إن شجرة الشرائح أو المقاطع Segment Tree من حيث المبدأ، بنية ثابتة أي أنه هيكل بيانات لا يمكن تعديله بمجرد بنائه.وهي مشابة لشجرة الفاصل الزمني (Interval Tree). يوضح الشكل التالي مثال للشجرة المقطع:
وتستخدم شجرة المقاطع لمجموعة I من الفواصل الزمنية تخزين O(n log n) ويمكن إنشاؤها في وقت O(n log n). كما تدعم أشجار المقاطع البحث عن جميع الفواصل الزمنية التي تحتوي على نقطة استعلام زمنية O(log n + k)، حيث يمثل k عدد الفواصل الزمنية أو المقاطع المستردة.
تنفيذ الشجرة الثنائية Binary Tree
يمكن أن يختلف تنفيذ الأشجار الثانية وفقًا لنوع الشجرة التي تعمل معها. فيما يلي سنقدم التنفيذ الأساسي لشجرة البحث الثنائية (BST) بلغة بايثون، وهي النوع الشائع الاستخدام من أنواع الأشجار الثنائية. وتكون خطوات التنفيذ لهذا النوع كتالي:
إنشاء Node Class: و يمثل عقدة واحدة من الشجرة، كما يحتوي على قيمة (val)، ومؤشرات إلى اليسار واليمين (left وright).
...........
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
...........
إنشاء BinarySearchTree Class: ويحتوي على جذر الشجرة (root)، والدوال الخاصة بعمليات الإدراج (insert)، والبحث (search)، والاجتياز بالترتيب (inorder)، وحذف (delete) العقد.
...........
class BinarySearchTree:
def __init__(self):
self.root = None
...........
عملية الإدراج (insert) : تحقق ما إذا كانت الشجرة فارغة، فإذا كانت فارغة ستصبح العقدة الجديدة هي الجذر. بخلاف ذلك، يتم استخدام الدالة المساعدة insert_ للعثور بشكل متكرر على الموضع الصحيح للعقدة الجديدة.
...........
def insert(self, key):
if self.root is None:
self.root = Node(key)
else:
self._insert(self.root, key)
def _insert(self, node, key):
if key < node.val:
if node.left is None:
node.left = Node(key)
else:
self._insert(node.left, key)
else:
if node.right is None:
node.right = Node(key)
else:
self._insert(node.right, key)
...........
البحث search : بواسطة الدالة المساعدة search_ يتم البحث بشكل متكرر عن عقدة بالمفتاح المحدد.
...........
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None or node.val == key:
return node
if key < node.val:
return self._search(node.left, key)
return self._search(node.right, key)
...........
الاجتياز بالترتيب (In-order Traversal:): بواسطة الدالة المساعدة inorder_ تتم زيارة العقد بالترتيب بشكل متكرر بترتيب inorder (يسار left ، جذر root ، يمين right).
...........
def inorder(self):
self._inorder(self.root)
def _inorder(self, node):
if node:
self._inorder(node.left)
print(node.val, end=" ")
self._inorder(node.right)
...........
الحذف Deletion: بواسطة الدالة المساعدة delete_ يتم العثور على العقدة المراد حذفها. و يعالج ثلاث حالات:
عقدة مع طفل واحد فقط أو لا يوجد طفل. وعقدة ذات طفلين: ابحث عن العقدة اللاحقة بالترتيب (الأصغر في الشجرة الفرعية اليمنى)، وانسخ قيمتها إلى العقدة، واحذف العقدة اللاحقة.
...........
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return node
if key < node.val:
node.left = self._delete(node.left, key)
elif key > node.val:
node.right = self._delete(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
temp = self._min_value_node(node.right)
node.val = temp.val
node.right = self._delete(node.right, temp.val)
return node
...........
ويكون الاستخدام في main على الشكل التالي:
...........
def _min_value_node(self, node):
current = node
while current.left is not None:
current = current.left
return current
# Example usage:
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Inorder traversal of the given tree")
bst.inorder()
print("\n\nDelete 20")
bst.delete(20)
print("Inorder traversal of the modified tree")
bst.inorder()
print("\n\nDelete 30")
bst.delete(30)
print("Inorder traversal of the modified tree")
bst.inorder()
print("\n\nDelete 50")
bst.delete(50)
print("Inorder traversal of the modified tree")
bst.inorder()
...........
الكود بالكامل متوفر على الرابط هنا.
يوفر هذا التنفيذ الأساسي أساسًا لفهم أشجار البحث الثنائية BST والعمل معها. تعتمد الأشجار الأكثر تقدمًا، مثل أشجار AVL أو الأشجار ذات اللون الأحمر والأسود، على هذه المفاهيم بخصائص وآليات موازنة إضافية.
الاجتياز Traversal والأشجار الثنائية
في هياكل البيانات الشجرية والأشجار الثنائية على وجهه التحديد عملية الاجتياز هي عملية زيارة للعُقد (nodes) للشجرة بترتيب معين. أي في عملية الاجتياز Traversal ، تتم زيارة كل عنصر من عناصر الشجرة الثنائية مرة واحدة بالضبط.
ويمكن تنفيذ العديد من عمليات الشجرة الثنائية عن طريق إجراء عملية الاجتياز traversal الشجرة الثنائية. فأثناء زيارة أحد العناصر، يمكن اتخاذ أي من الإجراءات إنشاء نسخة من العنصر ، عرض قيمة العنصر ، تقييم قيمة العنصر في عمليات المقارنة وما إلى ذلك فيما يتعلق بهذا العنصر، ويأخذ الاجتياز traversal ثلاثة أشكال:
1- الاجتياز بالترتيب (In-order traversa) : وفيه تتم زيارة العُقد في الشجرة الفرعية اليسرى، ثم عقدة الجذر ثم الشجرة الفرعية اليمنى (Left -Root -Right ). ويتم تنفيذه كتالي:
...........
def inorder(self):
self._inorder(self.root)
def _inorder(self, node):
if node:
self._inorder(node.left)
print(node.val, end=" ")
self._inorder(node.right)
...........
2- الاجتياز المسبق (Pre-order traversal): وفيه تتم زيارة عقدة الجذر والشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى (Root, Left, Right). ويتم تنفيذه كتالي:
...........
def preorder(self):
self._preorder(self.root)
def _preorder(self, node):
if node:
print(node.val, end=" ")
self._preorder(node.left)
self._preorder(node.right)
...........
3- الاجتياز اللاحق (Post-order traversal): وفيه تتم زيارة الشجرة الفرعية اليسرى، والشجرة الفرعية اليمنى، ثم عقدة الجذر( Left, Right, Root) . ويتم تنفيذه كتالي:
...........
def postorder(self):
self._postorder(self.root)
def _postorder(self, node):
if node:
self._postorder(node.left)
self._postorder(node.right)
print(node.val, end=" ")
...........
نلاحظ الفرق في النتائج عند التنفيذ:
...........
def _min_value_node(self, node):
current = node
while current.left is not None:
current = current.left
return current
# Example usage:
bst = BinarySearchTree()
bst.insert(10)
bst.insert(3)
bst.insert(9)
bst.insert(5)
bst.insert(11)
bst.insert(15)
bst.insert(20)
print("In-order traversal of the given tree")
bst.inorder()
print("\n\nPre-order traversal of the given tree")
bst.preorder()
print("\n\nPost-order traversal of the given tree")
bst.postorder()
...........
الـ Output للمثال:
In-order traversal of the given tree 3 5 9 10 11 15 20 Pre-order traversal of the given tree 10 3 9 5 11 15 20 Post-order traversal of the given tree 5 9 3 20 15 11 10
الكود بالكامل متوفر على الرابط هنا.
في حالات متعددة مثل الأشجار الثنائية يؤثر نوع الترتيب المستخدم في عملية الاجتياز(Traversa) على النتائج، مثلاً يمكن استخدام الأشجار الثنائية للتمثيل التعابير الرياضية (Expression Tree)، في الشكل التالي يوضح كيف يؤثر نوع الاجتياز Traversal على النتائج للتعابير الرياضية:
تُعد الأشجار الثنائية (Binary Trees) من الهياكل البيانية الأساسية في علوم الحاسب وتطبيقاتها. من خلال تنظيم البيانات بطرق تتيح الوصول السريع والفعال، توفر الأشجار الثنائية حلولاً مثالية لمجموعة واسعة من المشاكل البرمجية. سواء كانت تُستخدم في بناء هياكل بيانات معقدة، أو تحسين أداء البحث والفرز، أو حتى في تطوير خوارزميات الذكاء الاصطناعي، تبقى الأشجار الثنائية عنصرًا لا غنى عنه في صندوق أدوات المبرمج.