Topic 17It d ti t TIntroduction to Trees"A t"A tree may grow a thousand feet tall butthousand feet tall, but its leaves will return to its roots."Chinese Proverb-Chinese ProverbCS 307 Fundamentals of Computer Science1DefinitionsAtibttdttdA treeis an abstract data typeroot nodeinternalnodes–one entry point, the root– Each node is either a leaf or it l dan internal node– An internal node has 1 or morechildrennodes thatmore children, nodes that can be reached directly from that internal nodethat internal node. – The internal node is said to be theparentof its child nodesleaf nodesCS 307 Fundamentals of Computer Science2the parentof its child nodesProperties of TreesOnly access point is the rootAll nodes, except the root, have one parent– like the inheritance hierarchy in JavaTraditionally trees drawn upside downTraditionally trees drawn upside downrootCS 307 Fundamentals of Computer Science3leavesProperties of Trees and Nodesrootsiblings: two nodes that have the same parentrootedgeedge: the link from one node to anotherpath length: the number of edges that must be siblingsedges a us betraversed to get from one node to anotherpath length from root to thisnode is 3CS 307 Fundamentals of Computer Science4More Properties of Treesdthth th l th f th t f th tdepth:the path length from the root of the tree to this nodehiht f dTh i di theight of a node: The maximum distance (path length) of any leaf from this nodea leaf has a height of 0–a leaf has a height of 0– the height of a tree is the height of the root of that treetreedescendants: any nodes that can be reached via 1 or more edges from this nodevia 1 or more edges from this nodeancestors: any nodes for which this node is a descendantCS 307 Fundamentals of Computer Science5descendant Tree VisualizationADBCFEG H JIKLMKLMNOCS 307 Fundamentals of Computer Science6NOAttendance Question 1What is the depth of the node that contains M on the previous slide?A. -1B.00C. 1D2D.2E. 3CS 307 Fundamentals of Computer Science7Binary TreesThere are many variations on trees but we will work with binary treesbinary tree: a tree with at most two children for each node– the possible children are normally referred to as the left and right childparentleft childright childCS 307 Fundamentals of Computer Science8Full Binary Treefull binary tree: a binary tree is which each node was exactly 2 or 0 childrenCS 307 Fundamentals of Computer Science9Complete Binary Treecomplete binary tree: a binary tree in which every level, except possibly the deepest is completely filled. At depth n, the height of the tree, all nodes are as far left as possibleWhere would the next node goCS 307 Fundamentals of Computer Science10Where would the next node goto maintain a complete tree?Perfect Binary Treeperfect binary tree: a binary tree with all leaf nodes at the same depth. All internal nodes have exactly two children.a perfect binary tree has the maximum number of nodes for a given heighta perfect binary tree has 2(n+1)-1 nodes a pe ec b a y ee asodeswhere n is the height of a tree– height = 0 -> 1 node– height = 1 -> 3 nodes– height = 2 -> 7 nodes–height=3->15 nodesCS 307 Fundamentals of Computer Science11height 3 15 nodesA Binary Node classbli l BN dpublic class BNode{ private Object myData;private BNode myLeft;itBNd Rihtprivate BNode myRight;public BNode();bli d ( bj d d l fpublic BNode(Object data, BNode left, BNode right)public Object getData()ipublic BNode getLeft()public BNode getRight()public void setData(Object data)public void setLeft(BNode left)public void setRight(BNode right)CS 307 Fundamentals of Computer Science12}Binary Tree TraversalsMlih illdfbiMany algorithms require all nodes of a binary tree be visited and the contents of each node processedprocessed.There are 4 traditional types of traversalspreorder traversal: process the root then process all sub–preorder traversal: process the root, then process all sub trees (left to right)– in order traversal: process the left sub tree, process the root, process the right sub tree– post order traversal: process the left sub tree, process the right sub tree then process the rootthe right sub tree, then process the root– level order traversal: starting from the root of a tree, process all nodes at the same depth from left to right, CS 307 Fundamentals of Computer Science13ppgthen proceed to the nodes at the next depth.Results of TraversalsTo determine the results of a traversal on a given tree draw a path around the tree.– start on the left side of the root and trace around the tree. The path should stay close to the tree.12pre order: process when pass down left side of node12 49 13 5 4249 4212 49 13 5 42in order: process when passunderneath node51313 49 5 12 42post order: process when pass up right side of nodeCS 307 Fundamentals of Computer Science14pass up right side of node13 5 49 42 12 Tree TraversalsADCF G H JKLCS 307 Fundamentals of Computer Science15Attendance Question 2What is a the result of a post order traversal of the tree on the previous slide?A. F C G A K H L D JB. F G C K L H J D AGC JC. A C F G D H K L JDACDFGHJKLD.A C D F G H J K LE. L K J H G F D C ACS 307 Fundamentals of Computer Science16Implement TraversalsImplement preorder, inorder, and post order traversal– Big O time and space?Implement a level order traversal using a pgqueue–Big O time and space? gpImplement a level order traversal without a queuequeue– target depthDifferent kinds of Iterators for traversals?CS 307 Fundamentals of Computer Science17Different kinds of Iterators for
View Full Document
Unlocking...