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

# 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.