TreesDefinition of a treeMore definitionsData structure for a treeADT for a treeTraversing a treeOther tree manipulationsFile systemsFamily treesPart of a genealogyGame treesBinary trees for expressions(General) trees for expressionsMore trees for statementsWriting compilers and interpretersI’ll never need to write a compiler...The EndTrees2Definition of a treeA tree is like a binary tree, except that a node may have any number of childrenDepending on the needs of the program, the children may or may not be orderedLike a binary tree, a tree has a root, internal nodes, and leavesEach node contains an element and has branches leading to other nodes (its children)Each node (other than the root) has a parentEach node has a depth (distance from the root)ACB D EGF H J KIL M N3More definitionsAn empty tree has no nodesThe descendents of a node are its children and the descendents of its childrenThe ancestors of a node are its parent (if any) and the ancestors of its parentThe subtree rooted at a node consists of the given node and all its descendentsAn ordered tree is one in which the order of the children is important; an unordered tree is one in which the children of a node can be thought of as a setThe branching factor of a node is the number of children it hasThe branching factor of a tree is the average branching factor of its nodes4Data structure for a treeA node in a binary tree can be represented as follows: class BinaryTreeNode { Object value; BinaryTreeNode leftChild, rightChild;}However, each node in a tree has an arbitrary number of children, so we need something that will hold an arbitrary number of nodes, such as an ArrayList class TreeNode { Object value; ArrayList children;}If we don’t care about the order of children, we might use a Set instead of a ArrayList5ADT for a treeIt must be possible to:Construct a new treeIf a tree can be empty, this may require a header nodeAdd a child to a nodeGet (iterate through) the children of a nodeAccess (get and set) the value in a nodeIt should probably be possible to:Remove a child (and the subtree rooted at that child)Get the parent of a node6Traversing a treeYou can traverse a tree in preorder: void preorderPrint(node) { System.out.println(node); Iterator iter = node.children.iterator(); while (iter.hasNext()) { preorderPrint(iter.next()); }}You can traverse a tree in postorder: void postorderPrint(node) { Iterator iter = node.children.iterator(); while (iter.hasNext()) { postorderPrint(iter.next()); } System.out.println(node);}You can’t usually traverse a tree in inorderWhy not?7Other tree manipulationsThere’s really nothing new to talk about; you’ve seen it all with binary treesA tree consists of nodes, each node has references to some other nodes—you know how to do all this stuffThere are some useful algorithms for searching trees, and with some modifications they also apply to searching graphsLet’s move on to some applications of trees8File systemsFile systems are almost always implemented as a tree structureThe nodes in the tree are of (at least) two types: folders (or directories), and plain filesA folder typically has children—subfolders and plain filesA folder also contains a link to its parent—in both Windows and UNIX, this link is denoted by ..In UNIX, the root of the tree is denoted by /A plain file is typically a leaf9Family treesIt turns out that a tree is not a good way to represent a family treeEvery child has two parents, a mother and a fatherParents frequently remarryAn “upside down” binary tree almost worksSince it is a biological fact (so far) that every child has exactly two parents, we can use left child = father and right child = motherThe terminology gets a bit confusingIf you could go back far enough, it becomes a mathematical certainty that the mother and father have some ancestors in common10Part of a genealogyIsaacDavidPaulaStevenDanielleWinfred CarolChester Elaine Eugene Pauline11Game treesTrees are used heavily in implementing games, particularly board gamesA node represents a position on the boardThe children of a node represent all the possible moves from that positionMore precisely, the branches from a node represent the possible moves; the children represent the new positionsPlanning ahead (in a game) means choosing a path through the treeHowever—You can’t have a cycle in a treeIf you can return to a previous position in a game, you have a cycleGraphs can have cycles12Binary trees for expressionsOrdered trees can be used to represent arithmetic expressionsTo evaluate an expression (given as a node):If it is a leaf, the element in it specifies the valueIf the element is a number, that number is the valueIf the element is a variable, look up its value in a tableIf it is not a leaf, the element in it specifies an operationEvaluate the children and combine them according to the operation+2 2The expression 2+2+2*3 4The expression 2+3*4*4+2 3The expression (2+3)*413(General) trees for expressionsYou can use binary trees for expressions if you have only unary and binary operatorsJava has a ternary operatorTrees can be used to represent statements as well as expressionsStatements can be evaluated as easily as expressions The expression x > y ? x : y?:> xxyyThe statement if (x > y) max = x; else max = y;yif>xx ymax max= =14More trees for statements while (n >= 1) { exp = x * exp; n--;} for (int i = 0; i < n; i++) a[i] = 0;while>=n 1expexp*=n--x;foriint=0a[ ]iin 0++=<i15Writing compilers and interpretersA compiler does three things:Parses the input program (converts it into an abstract syntax tree)(Optionally) optimizes the abstract syntax treeTraverses the tree and outputs assembly language or machine code to do the same operationsAn interpreter does three things:Parses the input program (converts it into an abstract syntax tree)(Optionally) optimizes the abstract syntax treeTraverses the tree in an order controlled by the node contents, and performs the operations as it goesParsing is usually the hard part, but there is a very simple technique (called recursive descent parsing) that can be used if the language is carefully designed and you don’t care too much about efficiency or good error messages16I’ll
View Full Document
Unlocking...