Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39TreesRosen Chapter 9 (page 631 onwards)Where else might we see trees?1. Table of contents of a book (chapters, sections, subsections, …)2. Organisational charts (boss is at the top)3. Decision procedures (Hayne’s manual for repairing a car)4. The local sewage system5. As a data structure (for storing information)6. As an ephemeral structure, as in combinatorial search (backtracking)7. Your family tree.8. …So, what is a tree?A tree is a connected undirected graph with no simple circuitsA tree is a connected graph with n-1 edgesA tree is a graph such that there is a unique simple path between any pair of verticesAll of the above say the same thing!An unrooted treeKinds of nodes/vertices in a tree• the root (this tree doesn’t have one)• leaf nodes (there are 6 here)• interior nodes (there are 5 here)A Rooted treeA rooted tree has one vertex designated as the root and everyother edge is directed away from the rootThe above tree is a binary treeWe put the root at the top by conventionAIHCBJKFEGDThe parent of H is BThe sibling of G is JThe ancestors of I are E, K, and AC is a child of KThe descendants of B are F, H, and DA is the root, and has no ancestorsThe leaf nodes have no childrenAgain, the tree is a binary treeAIHCBJKFEGDThe height of a binary tree•The height of a leaf node is 0•The height of an empty tree is 0•The height of a node x is 1 + max(height(left(x)),height(right(x)))Note: I’ve assumed that we have functions left, right, isNode, and isLeafAIHCBJKFEGDTraversalsIf you’ve got some structure one of the 1st things you want to be able to do is to traverse it!We have 3 traversals 1. preorder2. inorder3. postorderAgain, we’ll stick to rooted binary treesAIHCBJKFEGDTraversalspreorder(x) if isNode(x) then print(x), preorder(left(x)), preorder(right(x))inorder(x) if isNode(x) then inorder(left(x)), print(x), inorder(right(x))postorder(x) if isNode(x) then print(x), postorder(left(x)), postorder(right(x))A,B,F,H,D,K,C,J,G,E,IF,B,D,H,A,J,C,G,K,E,IF,D,H,B,J,G,C,I,E,K,AAIHCBJKFEGDA walk round the tree• if we “print” on 1st visit we get preorder• if we “print” on 2nd visit we get inorder• if we “print” on last visit we get postorderDetermine the tree from its traversals1. Preorder: ICBEHDAFG2. Inorder: EBHCIFADG3. Postorder: EHBCFAGDI• (a) I is the root (from 1)• (b) E, B, H, and C are to the left of I (from (a) and 2)• (c) F, A, D, and G are to the right of I (from (a) 2)• (d) C is the first left node of I (from (c) and 1)• (e) D is the first right node of I (from (c) and 1)• (f) possibly we have • B to the left of C, • E to the left of B,• H to the right of B … as this satisfies 1 and 2• (g) F and A are left of D, and G is right of D (from 2)• (h) F must be left of A (from 1)• (j) the tree is now fully definedDetermine the tree from its traversals1. Preorder: ICBEHDAFG2. Inorder: EBHCIFADG3. Postorder: EHBCFAGDIIDCHAGE FBHow would you represent a tree in a computer?1108329116574Might have a btree data structure with attributes• data • the actual information in a node• left• the btree to the left, or nil• right• the btree to the right, or nil1108329116574Might use a 2d array 53111111101011991488117711661015511447933862211211rightleftdata1108329116574Might use a 1d array , giving parent of a node15323211811111110987654321+8+*9*657An expression(6 * 8) + ((9 + 7) * 5)What would a preorder, inorder and postorder traversal of this tree looklike?Standard format for trees• Cayley Notation• Newick Notation(((((((PLE:1,PPA:1)9:1,PON:2,PUN:2)8:1,(NNE:2,PTI:2)8:1)7:5, (((LCA:2,LRU:2)8:3,PMA:5)6:2,PTE:7,(AJU:5,PCO:5)6:2, (LSE:5,(CCA:3,PAU:3)7:2)6:2)5:1)4:1,FCA:9)3:1,LPA:10)2:10,CCR:20)1;Trees are beautiful recursive structuresThere are many tree-based data structuresThere are many algorithms for treesThere is a lot to learn about treesThere is a lot of research going on about