Trees

• Binary tree


  A rooted tree in which each node has at most two children
• Tree


  A rooted tree has a root, branches and leaves, with the root at the top and the leaves at the bottom
• Typical uses for rooted trees

  • Manipulating hierarchical data, such as folder structures or moves in a game
  • Making information easy to search (see binary tree search)
  • Manipulating sorted lists of data
• Generations of a family may be thought of as having a tree structure
• Branch or edge


  Connects two nodes
• Root node


  The only node that has no incoming edges
• Child


  The set of nodes that have incoming edges from the same node
• Parent


  A node is a parent of all the nodes it connects to with outgoing edges
• Subtree


  The set of nodes and edges comprised of a parent and all descendants of the parent
• Leaf node


  A node that has no children
• Constructing a binary search tree

  1. Take the first item as the root

  2. Compare each new item to the root, and branch left or right depending on whether it is less than or greater than the root

  3. Repeat this process for each new item until the tree is complete
• The final tree looks like the one shown in the image
• Child node


  A node that is connected to another node (the parent) by a directed edge
• A node can have one parent node, and it can have children nodes
• A rooted tree has no cycles because there can be no connection between children, or between branches
• A rooted tree is a special case of a connected graph
• Binary search tree


  A binary tree in which items are stored in such a way that the tree can be searched quickly and easily for a particular item, new items can be easily added, and the whole tree can be printed out in sequence
• Binary tree


  A rooted tree in which each node has a maximum of two children
• Constructing a binary search tree

  1. Place the first item at the root

  2. For each item in the list, visit the root, which becomes the current node, and branch left if the item is less than the value at the current node, and right if the item is greater than the value at the current node

  3. Continue down the branch, applying the rule at each node visited, until a leaf node is reached

  4. Place the item to the left or right of this node, depending on whether it is less than or greater than the value at that node
• Searching a binary search tree

  1. Follow the same steps as constructing the tree

  2. Branch right if the item is greater than the current node

  3. Branch left if the item is less than the current node