of tree (or in our workshop appletthe nodes are represented as circlesand the edges as lines connecting the circles trees have been studied extensively as abstract mathematical entitiesso there' large amount of theoretical knowledge about them tree is actually an instance of more general category called graphbut we don' need to worry about that here we'll discuss graphs in "graphs,and "weighted graphs figure tree in computer programsnodes often represent such entities as peoplecar partsairline reservationsand so onin other wordsthe typical items we store in any kind of data structure in an oop language such as javathese real-world entities are represented by objects the lines (edgesbetween the nodes represent the way the nodes are related roughly speakingthe lines represent convenienceit' easy (and fastfor program to get from one node to another if there is line connecting them in factthe only way to get from node to node is to follow path along the lines generally you are restricted to going in one direction along edgesfrom the root downward edges are likely to be represented in program by referencesif the program is written in java (or by pointers if the program is written in or ++typically there is one node in the top row of treewith lines connecting to more nodes on the second roweven more on the thirdand so on thus trees are small on the top and large on the bottom this may seem upside-down compared with real treesbut generally program starts an operation at the small end of the treeand it' (arguablymore natural to think about going from top to bottomas in reading text there are different kinds of trees the tree shown in figure has more than two children per node (we'll see what "childrenmeans in moment howeverin this we'll be discussing specialized form of tree called binary tree each node in binary tree has maximum of two children more general treesin which nodes can have more than two childrenare called multiway trees we'll see an example in tables and external storage,where we discuss trees an analogy one commonly encountered tree is the hierarchical file structure in computer system the root directory of given device (designated with the backslashas in :\on many systemsis the tree' root the directories one level below the root directory are its children there may be many levels of subdirectories files represent leavesthey have no children of their own clearly hierarchical file structure is not binary treebecause directory may have many children complete pathnamesuch as :\sales\east\november\smith datcorresponds to the path from the root to the smith dat leaf terms used for the file structuresuch as root and pathwere borrowed