Binary Tree

Terminology

A binary tree is made of nodes,where each node contains a "left" reference, a "right" reference, and a data element, the topmost node is called the root.
1.The depth of a node is the number of edges from the root to the node.
2.The hight of a node is the number of edges from the node to the deepest leave.
3.A full binary tree is a binary tree in which each node has exactly zero or two children.
4.A complete binary tree is a binary tree which is completely filled, with the possible exception of the bottom level, which is fulled from left to right.（缺少右边若干节点）

补充：完全二叉树特点：
1.按层序给节点编号k=1,2,3,....n,每个节点的父节点为 int(k/2)
2.如果2K=n，则左子结点为2k，否则该结无子节点。
3.如果2k+1=n，则右子节点为2k+1，否则无右子节点。

Traversals

A traversals is processer that visit all the nodes in the tree. 

1.depth-first traversal

   -PreOrder traversal: Visit parent node firstly, and left child then right child.

   -InOrder traversal: Visit left children then parent and right children.

   -PostOrder traversal: Visit left children then right children, and thiers parents at the end.

2.breadth-first traversal

   -LeverOrder traversal: Visit nodes by lever from top to bottom and from left to right.