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
Slide Note
Embed
Share

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.

  • Computation
  • Tree Structures
  • Data Representation
  • Binary Trees

Uploaded on Oct 05, 2024 | 0 Views


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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. The Theory of Computation Trees / - 9 - .

  2. TREES TREES . . . :Free tree . : The depth : The height of tree Balanced .

  3. Example1: the five boxing wizards jump quickly.

  4. 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.

  5. Tree Terminology Subtree: tree consisting of a node and its descendants A D B C E F G H I J K

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#