树

二叉查找树

1. 是TreeSet、TreeMap实现的基础

2. 树的术语

   • 没有子节点的节点叫做树叶
   • 具有相同父亲节点的叫做兄弟
   • 深度：从根到某一节点的唯一路径的长。
   • 长：是指改路径上的边的个数
   • 高： 是从某一节点到树叶的最长路径的长。
   • 树的高度等于根节点的高度。
   • 先序遍历：根左右
   • 后序遍历: 叶左右（先访问左叶至上，再右叶至上，至根）
   • 中序遍历: 左，节点，右。

3. 树的基本节点:

   class TreeNode {
     Object element;
     TreeNode firstChild;
     TreeNode nextSibling;
   }

   二叉树

   1. 特点
      • 二叉树是一种树，其中每个节点不能多于2个儿子。
      • 性质：一颗平均二叉树的深度要比节点个数N小得多。
      • 平均深度O(sqrt(N))
      • 特殊的二叉树：二叉查找树,其深度（O(logN)）

4. 节点实现

   class TreeNode {
     Object element;
     TreeNode left;
     TreeNode right;
   }

   二叉查找树

   1. 性质：节点左侧所有项均小于节点，右侧所有项均大于节点。

   AVL 树

   1. AVL树是一种高度平衡的平衡二叉树，树中的任意节点的左右子树的高度之差不超过1。