[CSUSB] >> [CompSci] >> [Dick Botting] >> [CS330 Course Materials] >> [Ref] >> treeGlossary
[Index] || [Contents] || [Grades] Thu Oct 31 12:21:22 PST 2002

Contents


    Glossary of Trees

  1. AVL_tree::=A nearly balanced tree invented by Aho, V??, and L??.

  2. ancestors::=nodes that are above this node.

  3. balanced::=`A tree where all paths from a node to a leaf are nearly the same value`. See height_balanced.

  4. binary_tree::= tree where each node has zeroe, one or two children. The two children are labeled the left and right children.

  5. complete_binary_tree::=`Almost a full binary_tree, with the bottom level filled from left to right`.

  6. DAG::=A directed acyclic graph, A directed graph which is almost a tree. The branches can join up but never loop back to a previous node.

  7. descendants::=The children and the children's children, etc....

  8. full_binary_tree::=A binary_tree where all interior nodes have 2 children.

  9. binary_search_tree::=A binary_tree where all the descendants of the left child are less than the root and all the right hand descendants are bigger.

  10. height::=the longest path from the root down the tree to a leaf in the tree.

  11. height_balanced::=The difference between the heights of the subtrees is no more than 1(one).

  12. inorder::=`traversing a tree so that all nodes to the left are visited before a node, and all nodes to the right are visited afterward`.

  13. interior::=all nodes that are nor leafs in the tree.

  14. leaf::=A node on a tree with no children.
  15. leafs::=plural of leaf.
  16. leaves::=British spelling of leafs.

  17. node::=An object in the implementation of a tree that has an item of data and a number of links to the subtrees of the item,
  18. node may or may not have a link to a parent.

  19. postorder::=visiting the children before the parent.
  20. preorder::=visiting the node before visiting the children.

  21. search_tree::=`a tree where a particular value can be found by choosing on branch and never having to back track`.

  22. subtree::=A tree that is part of another tree.
  23. subtrees::=plural of subtree.

  24. root::=The unique node that is an ancestor of all other nodes in the tree.

  25. tree::=either empty or a root plus zero or more subtrees. Note that computer scientists draw trees upside donw with the root at the top! A mathematical description of a tree is as a directed graph that is weakly-connected, has no semicycles, and a single root: [ Trees in math_22_graphs ]

  26. traverse::=to visit each node in a data structure in turn. See inorder, preorder, and postorder.

    . . . . . . . . . ( end of section Glossary of Trees) <<Contents | Index>>

    Exercise

    Draw a DAG of all types of tree. The root should be the most general kind of tree. Subtrees should be special kinds of their parents.

Formulae and Definitions in Alphabetical Order