Tag IV. Tree
*知识点整理：
- 注意 Binary Tree 和Binary Search Tree（左小右大）是不一样的。
1. Search an Element: 小左找，大右找。
2. Insert element into a BST: locate the parent for the new node.
稍微有点绕：
while(current != null) {
if (e < the value in current.element) {
parent = current;
current = current.left;
}
else if (e > the value in current.element) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted.
return true; // element inserted
}
3. Tree Traversal: preorder Inorder postorder depth-first breadth-first
Inorder: Display all the nodes in a BST in increasing order.
Postorder应用：get the size of each file and subdirectory before finding the size of the root directory.
Preorder应用：print a structured document. A tree can be used to represent a structured document such as a book and its chapters and sections.
Depth-First Traversal is the same as Preorder traversal.
Breadth-First Traversal: Level by level. From root to child. From left to right.
4. BST class
interface – Tree
abstract class – AbstractTree (partially implements Tree)
concrete class – BST (extends AbstractTree)
5. Deleting elements from a BST
Case 1: The current node to be delete do not have left child.
6. 注意分清楚 depth of tree. Heights of node.
** Connect the parent with the right child of the current node.
Case 2: The current node has a left child.
Step 1: Find the largest right child in the left sub tree of current node.
Step 2: Replace elements in current node with right most node.
Step 3: Connect the parent of right most node to the left child of right most node.
7. Iterators
- BST is iterable because it is defined as a subtype of the java.lang.Iterable interface.
DFT，BFT的递归和非递归遍历方法都要倒背如流