Trees 06 Handout 1 PDF

IT1815 Trees O and N I and K Fundamentals...

IT1815 Trees O and N I and K Fundamentals A and Q A tree represents a hierarchical nature of a structure in a Leaf nodes I, K, A, Q, T graphical form. It consists of elements or nodes, with each One-level subtrees B-E/R node linked to its successors. E-O/N The best example of a tree is the computer's file system: R-I/K C:\Users\bpena\Desktop\TreeDemo.java O-A/Q The top of a tree is called its root. The links from a node to its N-T successors are called branches, edges, lines, or paths. Nodes per level Level 0 – B The successors of a node are called its child nodes or Level 1 – E, R children. The predecessor of a node is called its parent. Level 2 – O, N, I, K A tree is considered a binary tree if all its nodes have two (2) Level 3 – A, Q, T child nodes at most. Depth 3 Each node in a tree has exactly one (1) parent except for the Degree of each one-level Subtree B – 2 root node, which has no parent. subtree Subtree E – 2 Nodes that have the same parent are siblings. Subtree R – 2 A node that has no child nodes is a leaf node or external Subtree O – 2 node. Nodes that have children are known as internal nodes. Subtree N – 1 A tree within a tree is considered a subtree. The level of a node is a measure of its distance from the root. Tree Traversal The depth of the tree is its highest level. Traversal is the process of visiting all the nodes in a specific The degree is the number of child nodes in a subtree. order. The following are the different traversal types: Example: o Breadth-First or Level Order: Nodes are visited by level. 1, 2, 3, 4, 5 Parts Value(s) o Depth-First Root node B ▪ Inorder (Left, Root, Right): 4, 2, 5, 1, 3 Child nodes E, R, O, N, I, K, A, Q, T Start with the bottommost left subtree. Once Parent nodes B, E, R, O, N the root in Level 0 is visited, proceed to the Siblings E and R bottommost right subtree. 06 Handout 1 *Property of STI  [email protected] Page 1 of 3  IT1815 ▪ Preorder (Root, Left, Right): 1, 2, 4, 5, 3 of a node in the parent's Start with the root in Level 0 then continue children array with the left subtree. getSiblingCount() Returns the number of ▪ Postorder (Left, Right, Root): 4, 5, 2, 3, 1 siblings of a node Start with the bottommost left subtree then isLeaf() Returns true if a node proceed to the other subtrees. The root in has no children Level 0 is the last node visited. getLeafCount() Returns the total number of leaves that are Programming Trees descendants of a node The JTree is a Java Swing component that displays a set of getLevel() Returns the number of hierarchical data as an outline. It is included in the levels above a node javax.swing package. getDepth() Returns the highest level The Java class, DefaultMutableTreeNode, is used to of the tree represent a general-purpose node in a tree data structure. It getChildCount() Returns the number of is included in the javax.swing.tree package. children (degree) of a The add() method removes a node from its parent and makes node it a child of another node by adding it to the end of that node's breadthFirstEnumeration() Creates and returns an child array. enumeration that Other Java methods used in retrieving values from a tree are: traverses the subtree rooted at a node in Method Description breadth-first order. getRoot() Returns the root of the preorderEnumeration() Creates and returns an tree that contains the enumeration that node traverses the subtree children() Creates and returns a rooted at a node in forward-order preorder enumeration of a node's postorderEnumeration() Creates and returns an children enumeration that getChildCount() Return the number of traverses the subtree children that a node has rooted at this a in getParent() Returns a node's parent postorder. or null if it has no parent isNodeSibling() Returns true if a node is Sample Codes: a sibling of the other 1. To create an empty tree node JTree tree = new JTree(); getPreviousSibling() Returns the previous 2. To create a node: sibling of a node in the DefaultMutableTreeNode root = new parent's children array DefaultMutableTreeNode("B"); getNextSibling() Returns the next sibling 06 Handout 1 *Property of STI  [email protected] Page 2 of 3  IT1815 3. To create a tree with identified root node: Output: JTree tree = new JTree(root); 4. To add a child node root.add(n1); //n1 is another node 5. To display the children of a node: //Convert the Enumeration type to List List childNodes = Collections.list(root.children()); System.out.print(childNodes); //or simply System.out.print(Collections.list(root.children())); 6. To display a traversed tree: References: //Convert the Enumeration type to List Koffman, E. and Wolfgang, P. (2016). Data structures: Abstraction and design using List preTree = Java. Hoboken: John Wiley & Sons, Inc. Collections.list(root.preorderEnumeration()); Oracle Docs (n.d.). Citing sources. Retrieved from System.out.print(preTree); https://docs.oracle.com/javase/7/docs/api/javax/swing/tree/DefaultMutableTreeN ode.html Sample Program to Display a JTree in a JFrame: 06 Handout 1 *Property of STI  [email protected] Page 3 of 3