樹 是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。它具有以下特點(diǎn)：每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為 根 節(jié)點(diǎn)；每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè) 父節(jié)點(diǎn) ；除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹。

二叉樹是每個(gè)節(jié)點(diǎn)最多有兩棵子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。二叉樹的相關(guān)性質(zhì)：
二叉樹的每個(gè)結(jié)點(diǎn)至多只有2棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹的第i層至多有2^(i-1) 個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)。
一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)的二叉樹稱之為 滿二叉樹 ；
深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為 完全二叉樹 。

二叉樹的三種遍歷方法：
在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的節(jié)點(diǎn)，或者對(duì)樹中全部節(jié)點(diǎn)進(jìn)行某種處理，這就涉及到二叉樹的遍歷。二叉樹主要是由3個(gè)基本單元組成，根節(jié)點(diǎn)、左子樹和右子樹。如果限定先左后右，那么根據(jù)這三個(gè)部分遍歷的順序不同，可以分為先序遍歷、中序遍歷和后續(xù)遍歷三種。

(1) 先序遍歷 若二叉樹為空，則空操作，否則先訪問根節(jié)點(diǎn)，再先序遍歷左子樹，最后先序遍歷右子樹。 (2) 中序遍歷 若二叉樹為空，則空操作，否則先中序遍歷左子樹，再訪問根節(jié)點(diǎn)，最后中序遍歷右子樹。(3) 后序遍歷 若二叉樹為空，則空操作，否則先后序遍歷左子樹訪問根節(jié)點(diǎn)，再后序遍歷右子樹，最后訪問根節(jié)點(diǎn)。

二叉查找樹就是二叉排序樹，也叫二叉搜索樹。二叉查找樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： (1) 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2) 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3) 左、右子樹也分別為二叉排序樹；(4) 沒有鍵值相等的結(jié)點(diǎn)。

含有n個(gè)節(jié)點(diǎn)的二叉查找樹的平均查找長度和樹的形態(tài)有關(guān)。最壞情況下，當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉查找樹蛻變?yōu)閱沃洌瑯涞纳疃葹閚，其平均查找長度(n+1)/2(和順序查找相同），最好的情況是二叉查找樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(n)成正比。平均情況下，二叉查找樹的平均查找長度和logn是等數(shù)量級(jí)的，所以為了獲得更好的性能，通常在二叉查找樹的構(gòu)建過程需要進(jìn)行“平衡化處理”，之后我們將介紹平衡二叉樹和紅黑樹，這些均可以使查找樹的高度為O(log(n))。

//二叉樹的節(jié)點(diǎn)
class TreeNode<E> {
  E element;
  TreeNode<E> left;
  TreeNode<E> right;

  public TreeNode(E e) {
    element = e;
  }
}

二叉查找樹的三種遍歷都可以直接用遞歸的方法來實(shí)現(xiàn)：

//先序遍歷
protected void preorder(TreeNode<E> root) {

  if (root == null)
    return;

  System.out.println(root.element + " ");
  preorder(root.left);
  preorder(root.right);
}

//中序遍歷
protected void inorder(TreeNode<E> root) {

  if (root == null)
    return;

  inorder(root.left);
  System.out.println(root.element + " ");
  inorder(root.right);
}

//后序遍歷
protected void postorder(TreeNode<E> root) {

  if(root == null)
    return;

  postorder(root.left);
  postorder(root.right);
  System.out.println(root.element + " ");
}

二叉查找樹的簡單實(shí)現(xiàn):

public class BST<E extends Comparable<E>> {
  private TreeNode<E> root;
  // 默認(rèn)構(gòu)造函數(shù)
  public BST() {
  }

  // 二叉查找樹的搜索
  public boolean search(E e) {
    TreeNode<E> current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        current = current.left;
       }
      else if (e.compareTo(current.element) > 0) {
        current = current.right;
      }
      else {
        return true;
      }
    }
    return false;
  }

  // 二叉查找樹的插入
public boolean insert(E e) {
  if (root == null) {
    root = creatNewNode(e);
  }
  else {
    TreeNode<E> parent = null;
    TreeNode<E> current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else {
        return false;
      }
    }

    //插入
    if (e.compareTo(parent.element) < 0) {
      parent.left = creatNewNode(e);
    }
    else {
      parent.right = creatNewNode(e);
    }
  }
  return true;
}

  // 創(chuàng)建新的節(jié)點(diǎn)
  protected TreeNode<E> creatNewNode(E e) {
    return new TreeNode(e);
  }
}

// 二叉樹的節(jié)點(diǎn)
class TreeNode<E extends Comparable<E>> {
  E element;
  TreeNode<E> left;
  TreeNode<E> right;
  public TreeNode(E e) {
    element = e;
  }
}

平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。
AVL樹是最先發(fā)明的自平衡二叉查找樹算法。在AVL中任何節(jié)點(diǎn)的兩個(gè)兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹，n個(gè)結(jié)點(diǎn)的AVL樹最大深度約1.44log2n。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。
紅黑樹是平衡二叉樹的一種，它保證在最壞情況下基本動(dòng)態(tài)集合操作的事件復(fù)雜度為O(log n)。紅黑樹和平衡二叉樹區(qū)別如下：(1) 紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時(shí)間復(fù)雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實(shí)現(xiàn)起來也更為簡單。(2) 平衡二叉樹追求絕對(duì)平衡，條件比較苛刻，實(shí)現(xiàn)起來比較麻煩，每次插入新節(jié)點(diǎn)之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。