TreesDefinition of a treeMore definitionsData structure for a treeADT for a treeFile systemsFamily treesPart of a genealogyGame treesTrees for expressions and statementsMore trees for statementsThe EndTrees2Definition of a treeA tree is a node with a value and zero or more childrenDepending on the needs of the program, the children may or may not be orderedA 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 treeEach 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 Tree<V> { V 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 node6File 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 leaf7Family 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 common8Part of a genealogyIsaacDavidPaulaStevenDanielleWinfred CarolChester Elaine Eugene Pauline9Game 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 cycles10Trees for expressions and statementsExamples:The expression x > y ? x : y?:> xxyyThe statement if (x > y) max = x; else max = y;yif>xx ymax max= =11More 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++=<i12The
View Full Document
Unlocking...