Understanding Trees in Data Structures
Explore the world of trees in data structures through a comprehensive discussion on tree definitions, properties, formal definitions, node relationships, and edges. Discover how trees are structured hierarchically with parent-child relationships, nodes, roots, siblings, leaves, ancestors, descendants, and more. Dive into the fundamental concepts that define tree data type and its significance in computing, presented by Ali Akbar Mohammadi.
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
Tree Tree
Table of Content Table of Content General Trees Binary trees Implementing Trees Tree Traversal Algorithm Ali Akbar Mohammadi 2
General Trees General Trees Tree Definitions and Properties The Tree Abstract Data Type Computing Depth and Height Ali Akbar Mohammadi 3
Tree Definitions and Properties Tree Definitions and Properties A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements. A tree is usually visualized by placing elements inside ovals or rectangles, and by drawing the connections between parents and children with straight lines. We typically call the top element the root of the tree, but it is drawn as the highest element, with the other elements being connected below. Ali Akbar Mohammadi 5
Formal Tree Definition Formal Tree Definition Formally, we define a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties: If T is nonempty, it has a special node, called the root of T, that has no parent. Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w. Ali Akbar Mohammadi 7
Other Node Relationships Other Node Relationships Two nodes that are children of the same parent are siblings. A node v is external if v has no children. A node v is internal if it has one or more children. External nodes are also known as leaves. A node u is an ancestor of a node v if u = v or u is an ancestor of the parent of v. Conversely, we say that a node v is a descendant of a node u if u is an ancestor of v. The subtree of T rooted at a node v is the tree consisting of all the descendants of v in T (including v itself). Ali Akbar Mohammadi 8
Edges and Paths in Trees Edges and Paths in Trees An edge of tree T is a pair of nodes (u,v) such that u is the parent of v, or vice versa. A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge. Ali Akbar Mohammadi 9
Ordered Trees Ordered Trees A tree is ordered if there is a meaningful linear order among the children of each node; Ali Akbar Mohammadi 10
Position Position An abstraction for a node of a tree. An element is stored at each position, and positions satisfy parent- child relationships that define the tree structure. Ali Akbar Mohammadi 12
The Tree Abstract Data Type The Tree Abstract Data Type getElement( ): Returns the element stored at this position. root( ): Returns the position of the root of the tree (or null if empty). parent(p): Returns the position of the parent of position p (or null if p is the root). children(p): Returns an iterable collection containing the children of position p (if any). numChildren(p): Returns the number of children of position p. isInternal(p): Returns true if position p has at least one child. isExternal(p): Returns true if position p does not have any children. isRoot(p): Returns true if position p is the root of the tree. size( ): Returns the number of positions (and hence elements) that are contained in the tree. isEmpty( ): Returns true if the tree does not contain any positions (and thus no elements). iterator( ): Returns an iterator for all elements in the tree (so that the tree itself is Iterable). positions( ): Returns an iterable collection of all positions of the tree. Ali Akbar Mohammadi 13
Computing Depth Computing Depth The depth of p is the number of ancestors of p, other than p itself. The depth of p can also be recursively defined as follows: If p is the root, then the depth of p is 0. Otherwise, the depth of p is one plus the depth of the parent of p. Ali Akbar Mohammadi 14
Computing Height Computing Height The height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty). we define the height of a position p in a tree T as follows: If p is a leaf, then the height of p is 0. Otherwise, the height of p is one more than the maximum of the heights of p s children. Ali Akbar Mohammadi 15
Propositions Propositions The height of the root of a nonempty tree T, according to the recursive definition, equals the maximum depth among all leaves of tree T. Ali Akbar Mohammadi 16
Binary Trees Binary Trees The Binary Tree Abstract Data Type Properties of Binary Trees Ali Akbar Mohammadi 17
Binary Trees Binary Trees A binary tree is an ordered tree with the following properties: 1. Every node has at most two children. 2. Each child node is labeled as being either a left child or a right child. 3. A left child precedes a right child in the order of children of a node. Ali Akbar Mohammadi 18
Definitions Definitions The subtree rooted at a left or right child of an internal node v is called a left subtree or right subtree, respectively, of v. A binary tree is proper if each node has either zero or two children. Some people also refer to such trees as being full binary trees. Thus, in a proper binary tree, every internal node has exactly two children. A binary tree that is not proper is improper. Ali Akbar Mohammadi 19
Decision Trees Decision Trees An important class of binary trees arises in contexts where we wish to represent a number of different outcomes that can result from answering a series of yes-or-no questions. Ali Akbar Mohammadi 20
A decision tree A decision tree Providing Providing Investment Advice Investment Advice Ali Akbar Mohammadi 21
((((3+1) ((((3+1) 3)/((9 5)+2)) ((3 3)/((9 5)+2)) ((3 (7 4))+6)) (7 4))+6)) Ali Akbar Mohammadi 22
((((3+1) ((((3+1) 3)/((9 5)+2)) ((3 3)/((9 5)+2)) ((3 (7 4))+6)) (7 4))+6)) Ali Akbar Mohammadi 23
3+1 3+1 3/9 5+2 3 3/9 5+2 3 7 4+6 7 4+6 Ali Akbar Mohammadi 24
A Recursive Binary Tree Definition A Recursive Binary Tree Definition An empty tree. A nonempty tree having a root node r, which stores an element, and two binary trees that are respectively the left and right subtrees of r. We note that one or both of those subtrees can be empty by this definition. Ali Akbar Mohammadi 25
The Binary Tree Abstract Data Type The Binary Tree Abstract Data Type Additional methods of a binary tree left(p): Returns the position of the left child of p (or null if p has no left child). right(p): Returns the position of the right child of p (or null if p has no right child). sibling(p): Returns the position of the sibling of p (or null if p has no sibling). Ali Akbar Mohammadi 26
Properties of Binary Trees Properties of Binary Trees In a binary tree, level 0 has at most one node (the root). Level 1 has at most two nodes (the children of the root). Level 2 has at most four nodes, and so on. In general, level d has at most 2^d nodes. Ali Akbar Mohammadi 27
Implementing Trees Implementing Trees Linked Structure for Binary Trees Array-Based Representation of a Binary Tree Linked Structure for General Trees Ali Akbar Mohammadi 29
Linked Structure for Binary Trees Linked Structure for Binary Trees Ali Akbar Mohammadi 30
Operations for Updating a Linked Binary Tree Operations for Updating a Linked Binary Tree addRoot(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty. addLeft(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child. addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child. set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element. Ali Akbar Mohammadi 31
Performance of the Linked Binary Tree Implementation Performance of the Linked Binary Tree Implementation Ali Akbar Mohammadi 32
Array Array- -Based Representation of a Binary Tree Based Representation of a Binary Tree For every position p of T, let f (p) be the integer defined as follows: If p is the root of T, then f (p) = 0. If p is the left child of position q, then f (p) = 2 f (q)+1. If p is the right child of position q, then f (p) = 2 f (q)+2. Ali Akbar Mohammadi 33
((((3+1) ((((3+1) 3)/((9 5)+2)) ((3 3)/((9 5)+2)) ((3 (7 4))+6)) (7 4))+6)) Ali Akbar Mohammadi 35
3+1 3+1 3/9 5+2 3 3/9 5+2 3 7 4+6 7 4+6 Ali Akbar Mohammadi 36
Example Example Ali Akbar Mohammadi 37
Tree Traversal Algorithm Tree Traversal Algorithm Preorder and Post-order Traversals of General Trees In-order Traversal of a Binary Tree Ali Akbar Mohammadi 38
Preorder of General Trees Preorder of General Trees In a preorder traversal of a tree T, the root of T is visited first and then the subtrees rooted at its children are traversed recursively. If the tree is ordered, then the subtrees are traversed according to the order of the children. Ali Akbar Mohammadi 39
Preorder Traversal of an Ordered Tree Preorder Traversal of an Ordered Tree Ali Akbar Mohammadi 40
Algorithm for Preorder Traversal Algorithm for Preorder Traversal perform the visit action for position p for each child c in children(p) do preorder(c) Ali Akbar Mohammadi 41
Post Post- -order Traversals of General Trees order Traversals of General Trees In some sense, this algorithm can be viewed as the opposite of the preorder traversal, because it recursively traverses the subtrees rooted at the children of the root first, and then visits the root (hence, the name postorder ). Ali Akbar Mohammadi 42
Post Post- -Order traversal of the ordered tree Order traversal of the ordered tree Ali Akbar Mohammadi 43
Algorithm for Post Algorithm for Post- -Order Traversal Order Traversal for each child c in children(p) do postorder(c) perform the visit action for position p Ali Akbar Mohammadi 44
Running Running- -Time Analysis Time Analysis Cause this algorithms visit all the nodes on a tree, the Running-Time: O(n) Ali Akbar Mohammadi 45
In In- -order Traversal of a Binary Tree order Traversal of a Binary Tree Ali Akbar Mohammadi 46
Algorithm for In Algorithm for In- -order Traversal of a Binary Tree order Traversal of a Binary Tree if p has a left child lc then inorder(lc) perform the visit action for position p if p has a right child rc then inorder(rc) Ali Akbar Mohammadi 47
