資料結構與算法 5.樹

樹

樹的基本概念
    每個節點有0個或多個子節點
    沒有父節點的節點稱為根節點
    每一個非根節點有且隻有一個父節點
    除根節點外，每個子節點可以分為多個不相交的子樹
    一棵樹可以沒有任何節點，稱為空樹，可以隻有1個節點，即根節點

    節點、根節點、子節點、父節點、兄弟節點

    子樹、左子樹、右子樹

    節點的度（degree）：子樹的個數
    樹的度：所有節點度中的最大值
    葉子節點（leaf）：度為0的節點

    層數（level）：根節點在第1層，根節點的子節點在第2層，以此類推

    節點的深度（depth）：從根節點到目前節點的唯一路徑上的節點總數
    節點的高度（height）：從目前節點到最遠葉子節點的路徑上的節點總數

    樹的深度：所有節點深度中的最大值
    樹的高度：所有節點高度中的最大值
    樹的深度等于樹的高度

    有序樹：樹中任意節點的子節點之間有順序關系
    無序樹：樹中任意節點的子節點之間沒有順序關系，也叫自由樹
    森林：由m（m>=0）棵互不相交的樹組成的集合

樹的種類
    二叉樹：每個節點最多含有兩個子樹的樹
    完全二叉樹：對于一棵二叉樹，設其深度為d（d>1），除了第d層，其他各層的節點數均已達最大值，且d層所有節點從左向右緊密排列
    滿二叉樹：所有葉節點都在最底層的完全二叉樹
    平衡二叉樹（AVL樹）：任何節點的兩棵子樹的高度差不大于1的二叉樹
    排序二叉樹（binary search tree）：也叫二叉查找樹
    霍夫曼樹：帶權路徑最短的二叉樹，也叫最優二叉樹，用于資訊編碼
    B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多于兩個子樹

常見應用場景：
    xml、html等，編寫解析器時
    路由協定
    mysql資料庫索引
    檔案系統的目錄結構
    很多AI算法都是樹搜尋，此外機器學習中的decision tree也是樹結構