Lecture 7: Introduction to Trees (CSE354)

Lecture 7 Introduction to Trees CSE354-Algorithms and Data Structure © Dr. Ahmed Ayoub, 2019  Learning Objectives By the end of this lecture you will be able to:  Tree structure definition  Tree Terminology  Binary Trees  Binary Search Trees ...

Lecture 7 Introduction to Trees CSE354-Algorithms and Data Structure © Dr. Ahmed Ayoub, 2019  Learning Objectives By the end of this lecture you will be able to:  Tree structure definition  Tree Terminology  Binary Trees  Binary Search Trees  Trees A non-linear, hierarchical collection with a “one to many” relationships  Visual Representation of a Tree Trees allow each node to have multiple successors Parent Child  Tree Terminology Root Parent Child Leaf  Tree Terminology The first node is called the root. Successors are called children A parent node points to a child node. Nodes with no children are called leaves.  Binary Trees Binary trees can have at most two successors.  Binary Tree Example No imposed ordering. 25 42 7 12 3 105 111 17 68  Structure of a Binary Tree Node definesa Record data isoftype left_child isoftype Ptr toa right_child isoftype Ptr toa endrecord data left_child right_child Example Definition: Binary Tree Node Tree_Node definesa Record data isoftype Num left_child isoftype Ptr toa Tree_Node right_child isoftype Ptr toa Tree_Node endrecord // Tree_Node  Binary Search Trees For each node, the value stored in it is greater than the value in every node in the left sub-tree and less than the value in every node in the right sub-tree root 34 25 45 21 29 41 52  Node Depth in a Tree Measures how far down a node is in the tree. How many “ancestor” nodes “live above” the node? 0 1 2 3  Balanced Trees Roughly symmetrical There is a difference of a most one level of depth among the various leaves Balanced Not Balanced  Conclusion Trees allow us to create nonlinear collections Binary Trees have at most two successors (children) Binary Search Trees impose structure – Every node’s value is greater than all the values in its left sub-tree – Every node’s value is less than all the values in its right sub-tree