python中的樹資料結構

線性資料中的典型順序表和連結清單已經講完：

《

順序表資料結構在python中的應用 》 python實作單向連結清單資料結構及其基本方法 python實作單向循環連結清單資料結構及其方法 python實作雙向連結清單基本結構及其基本方法 python實作雙向循環連結清單基本結構及其基本方法 python實作堆棧資料結構及其基本方法 Python實作雙端隊列資料結構及其基本方法

下面将說圖形結構中的典型資料機構：樹；是一種重要的非線性資料結構，直覺地看，它是資料元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。

樹的一些基礎概念：

• 節點的度：一個節點含有的子樹的個數稱為該節點的度；
• 樹的度：一棵樹中，最大的節點的度稱為樹的度；
• 葉節點或終端節點：度為零的節點；
• 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
• 樹的高度或深度：樹中節點的最大層次；
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

• 路徑：對于一棵子樹中的任意兩個不同的結點，如果從一個結點出發，按層次自上而下沿着一個個樹枝能到達另一結點，稱它們之間存在着一條路徑

        常用樹的分類：

無序樹：樹中任意節點的子節點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節點的子節點之間有順序關系，這種樹稱為有序樹；

    二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；

    完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹;

    平衡二叉樹（AVL樹）：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹；

    排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜尋樹、有序二叉樹）；

    霍夫曼樹（用于資訊編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；

    B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多餘兩個子樹。

樹的儲存：

在python中一切皆對象，樹也不列外，樹在python中可以通過清單和連結清單來儲存。通過清單是将每個節點對象儲存，在邏輯上不過形象，基本不用；用的最多的是通過連結清單建構一個樹對象，其基本屬性是根節點，根節點的左樹屬性和右樹屬性連接配接不同的節點，依次建構一顆龐大的樹。

class Node(object):

    """節點類"""

    def __init__(self, elem=-1, lchild=None, rchild=None):

        self.elem = elem

        self.lchild = lchild

        self.rchild = rchild


class Tree(object):

    """樹類"""

    def __init__(self, root=None):

        self.root = root           

後面将主要說二叉樹、平衡二叉樹、紅黑樹及其相關的一些重要方法的python實作。