week10_trees.md

Trees

A Tree is a directed (has one-way links between nodes) and acyclic (no path wraps back around to the same node twice) structure of linked nodes.

Using a recursive definition, a tree is either empty (null)

OR

has a root node that contains: data, a left subtree, and a right subtree.

The left and/or right subtree can be empty.

A binary tree is one where each node has no more than two children.

Tree node: an object containing data and a left and right node children.

Root: the top node of the tree.

Leaf: A node without children.

Branch: any node that is neither the roof nor a leaf.

Tree height: the length of the longest path from root to a node.

Tree applications Organizational charts, directories and files on a computer, AI decision trees.

The Java Collections framework has a TreeMap and TreeSet implementations.

Binary Trees average time complexity of Binary Trees for access/search and insert/delete is O(log(n).

*Images credit: Wikipedia *

Reading

zyBooks 9.1 - 9.7

Examples

https://github.com/ava11235/it212/blob/main/IntTreeNode.java

https://github.com/ava11235/it212/blob/main/IntTree.java

https://github.com/ava11235/it212/blob/main/TestIntTree.java

Reference

https://www.cs.usfca.edu/~galles/visualization/BST.html

https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

Practice

zyBooks Ch 9.1 - 9.7 Participation Activities

Learning Outcomes

Upon successful completion of the material, students will be able to:

• Define a tree and its terminology such as nodes, leafs, height, etc.
• Define binary tree search, insert and remove algorithms.
• Use inorder traversal.
• Implement a binary search tree class.