Chapter 10 Trees Data Abstraction Problem Solving with C Fifth Edition by Frank M Carrano Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 Categories of Data Management Operations General Operations that Insert data into a data collection Delete data from a data collection Ask questions about the data in a data collection Position oriented ADTs Operations that Insert data into the ith position Delete data from the ith position Ask a question about the data in the ith position Examples list stack queue binary tree Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 2 Categories of Data Management Operations Value oriented ADTs Operations that Insert data according to its value Delete data knowing only its value Ask a question about data knowing only its value Examples sorted list binary search tree Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 3 Terminology Trees are composed of nodes and edges Trees are hierarchical Parent child relationship between two nodes Ancestor descendant relationships among nodes Subtree of a tree Any node and its descendants Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 4 Terminology Figure 10 1 A general tree Figure 10 2 A subtree of the tree in Figure 10 1 Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 5 Terminology General tree A general tree T is a set of one or more nodes such that T is partitioned into disjoint subsets A single node r the root Sets that are general trees called subtrees of r Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 6 Terminology Parent of node n The node directly above node n in the tree Child of node n A node directly below node n in the tree Root The only node in the tree with no parent Subtree of node n A tree that consists of a child if any of node n and the child s descendants Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 7 Terminology Leaf A node with no children Siblings Nodes with a common parent Ancestor of node n A node on the path from the root to n Descendant of node n A node on a path from n to a leaf Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 8 A Binary Tree A binary tree is a set T of nodes such that either T is empty or T is partitioned into three disjoint subsets A single node r the root Two possibly empty sets that are binary trees called the left subtree of r and the right subtree of r Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 9 A General Tree A Binary Tree Figure 10 3 a An organization chart b a family tree Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 10 More Binary Trees Figure 10 4 Binary trees that represent algebraic expressions Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 11 A Binary Search Tree A binary search tree A binary tree that has the following properties for each node n n s value is all values in n s left subtree TL n s value is all values in n s right subtree TR Both TL and TR are binary search trees Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 12 A Binary Search Tree Figure 10 5 A binary search tree of names Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 13 The Height of Trees Height of a tree Number of nodes along the longest path from the root to a leaf Height 3 Height 5 Height 7 Figure 10 6 Binary trees with the same nodes but different heights Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 14 The Height of Trees Level of a node n in a tree T If n is the root of T it is at level 1 If n is not the root of T its level is 1 greater than the level of its parent Height of a tree T defined in terms of the levels of its nodes If T is empty its height is 0 If T is not empty its height is equal to the maximum level of its nodes Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 15 The Height of Trees A recursive definition of height If T is empty its height is 0 If T is not empty height T 1 max height TL height TR r TL TR Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 16 Full Binary Trees A binary tree of height h is full if Nodes at levels h have two children each Recursive definition If T is empty T is a full binary tree of height 0 If T is not empty and has height h 0 T is a full binary tree if its root s subtrees are both full binary trees of height h 1 Figure 10 7 A full binary tree of height 3 Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 17 Complete Binary Trees A binary tree of height h is complete if It is full to level h 1 and Level h is filled from left to right Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 18 Complete Binary Trees Figure 10 8 A complete binary tree Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 19 Complete Binary Trees Another definition A binary tree of height h is complete if All nodes at levels h 2 have two children each and When a node at level h 1 has children all nodes to its left at the same level have two children each and When a node at level h 1 has one child it is a left child Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 20 Balanced Binary Trees A binary tree is balanced if the heights of any node s two subtrees differ by no more than 1 Complete binary trees are balanced Full binary trees are complete and balanced Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 21 The ADT Binary Tree Figure 10 9 UML diagram for the class BinaryTree Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 22 The ADT Binary Tree Building the ADT binary tree in Fig 10 6b tree1 setRootData F tree1 attachLeft G tree2 setRootData D tree2 attachLeftSubtree tree1 tree3 setRootData B tree3 attachLeftSubtree tree2 tree3 attachRight E tree4 setRootData C tree10 6 createBinaryTree A tree3 tree4 Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 23 Traversals of a Binary Tree A traversal visits each node in …