CMPSC 130A Chapter Notes - Chapter 4: Binary Search Tree, Tree Traversal, Avl Tree
Document Summary
Edge = a connection from the subtree(s) to the root. Parent = the root of each subtree root. Path = a path from node to is a sequence of nodes such that is the parent of for. Length = the number of edges on the path; Depth = the depth of any node is the length of the unique path from the root to. Height = the height of node is the length of the longest path from to a leaf. If there is a path from to , then is an ancestor of and is a descendent of. If , then is a proper ancestor of and is a proper descendant of. To implement a tree, keep the children of each node in a linked list of tree nodes. Preorder traversal = work at a node is performed before its children are processed. Postorder traversal = the work at a node is performed after its children are evaluated.
