Tree Data Structures in Computation
The Theory of Computation
النظرية الاحتسابية
المحاضرة رقم -9-
Trees
الاشجار
إعداد
م.م وديان حبيب حميد
كلية التربية الاساسية / قسم الحاسبات
T
R
E
E
S
رسم بياني متزامن لا يحتوي على دورات. المسار بين أي عقدتين في الشجرة فريد.
:Free tree
: هو طول المسار في الشجرة ما بين اي عقد والجذر.
The depth
: هو طول أطول مسار من الجذر.
The height of tree
اذا كانت جميع أوراقها ضمن نفس المستوى.
Balanced
تكون الشجرة متوازنة
Example1
:
the five boxing wizards jump quickly.
Tree Terminology
مصطلحات الشجرة
•
Root
: node without parent (A)
•
Siblings
: nodes share the same parent
•
Internal node
: node with at least one child (A, B, C, F)
•
External node
(leaf ): node without children (E, I, J, K, G, H, D)
•
Ancestors
of a node: parent, grandparent, grand-grandparent, etc.
•
Descendant
of a node: child, grandchild, grand-grandchild, etc.
•
Depth
of a node: number of ancestors
•
Height
of a tree: maximum depth of any node (3)
•
Degree
of a node: the number of its children
•
Degree
of a tree: the maximum number of its node.
Tree Terminology
مصطلحات الشجرة
•
Subtree
: tree consisting of a node and its descendants
Tree Properties
خصائص الشجرة
•
Property Value
•
Number of nodes
•
Height
•
Root Node
•
Leaves
•
Interior nodes
•
Ancestors of H
•
Descendants of B
•
Siblings of E
•
Right subtree of A
•
Degree of this tree
Intuitive Representation of Tree Node
•
List Representation
•
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
•
The root comes first, followed by a list of links to sub-trees
How many link fields are needed in
such a representation?
Tree Traversal
•
Two main methods:
•
Pre
order
•
Post
order
•
Recursive definition
•
Pre
order:
•
visit the root
•
traverse in preorder the children (subtrees)
•
Post
order
•
traverse in postorder the children (subtrees)
•
visit the root
Binary Tree
الشجرة الثنائية
•
A binary tree is a tree with the following properties:
•
Each internal node has at most two children (degree of two)
•
The children of a node are an ordered pair
•
We call the children of an internal node left child and right child
•
Alternative recursive definition: a binary tree is either
•
a tree consisting of a single node, OR
•
a tree whose root has an ordered pair of children, each of which is a binary tree
•
Applications:
•
arithmetic expressions
•
decision processes
•
searching
Examples of the Binary Tree
Explore the theory of computation trees, tree properties, and terminology including nodes, root, leaves, siblings, ancestors, descendants, and more. Learn about subtree representation, tree traversal methods, and the concept of binary trees in computing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Theory of Computation Trees / - 9 - .
TREES TREES . . . :Free tree . : The depth : The height of tree Balanced .
Tree Terminology Root: node without parent (A) Siblings: nodes share the same parent Internal node: node with at least one child (A, B, C, F) External node (leaf ): node without children (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grand-grandparent, etc. Descendant of a node: child, grandchild, grand-grandchild, etc. Depth of a node: number of ancestors Height of a tree: maximum depth of any node (3) Degree of a node: the number of its children Degree of a tree: the maximum number of its node.
Tree Terminology Subtree: tree consisting of a node and its descendants A D B C E F G H I J K
Tree Properties Property Value Number of nodes Height Root Node Leaves Interior nodes Ancestors of H Descendants of B Siblings of E Right subtree of A Degree of this tree A C B D E F G H I
Intuitive Representation of Tree Node List Representation ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) The root comes first, followed by a list of links to sub-trees How many link fields are needed in such a representation? Data Link 1 Link 2 Link n
Tree Traversal Two main methods: Preorder Postorder Recursive definition Preorder: visit the root traverse in preorder the children (subtrees) Postorder traverse in postorder the children (subtrees) visit the root
Binary Tree A binary tree is a tree with the following properties: Each internal node has at most two children (degree of two) The children of a node are an ordered pair We call the children of an internal node left child and right child Alternative recursive definition: a binary tree is either a tree consisting of a single node, OR a tree whose root has an ordered pair of children, each of which is a binary tree Applications: arithmetic expressions decision processes searching
Examples of the Binary Tree Skewed Binary Tree Complete Binary Tree A A A B B B C C F G D E D H I E
