線性數(shù)據(jù)中的典型順序表和鏈表已經(jīng)講完：

《順序表數(shù)據(jù)結(jié)構(gòu)在python中的應用》

《python實現(xiàn)單向鏈表數(shù)據(jù)結(jié)構(gòu)及其基本方法》

《python實現(xiàn)單向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)及其方法》

《python實現(xiàn)雙向鏈表基本結(jié)構(gòu)及其基本方法》

《python實現(xiàn)雙向循環(huán)鏈表基本結(jié)構(gòu)及其基本方法》

《python實現(xiàn)堆棧數(shù)據(jù)結(jié)構(gòu)及其基本方法》

《Python實現(xiàn)雙端隊列數(shù)據(jù)結(jié)構(gòu)及其基本方法》

下面將說圖形結(jié)構(gòu)中的典型數(shù)據(jù)機構(gòu)：樹；是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點）按分支關系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。

image

image

樹的一些基礎概念：

• 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；
• 樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；
• 葉節(jié)點或終端節(jié)點：度為零的節(jié)點；
• 節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
• 樹的高度或深度：樹中節(jié)點的最大層次；
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
• 路徑：對于一棵子樹中的任意兩個不同的結(jié)點，如果從一個結(jié)點出發(fā)，按層次自上而下沿著一個個樹枝能到達另一結(jié)點，稱它們之間存在著一條路徑

常用樹的分類：

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

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

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

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

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

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

霍夫曼樹（用于信息編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；

B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序，擁有多余兩個子樹。

樹的儲存：

在python中一切皆對象，樹也不列外，樹在python中可以通過列表和鏈表來儲存。通過列表是將每個節(jié)點對象儲存，在邏輯上不過形象，基本不用；用的最多的是通過鏈表構(gòu)建一個樹對象，其基本屬性是根節(jié)點，根節(jié)點的左樹屬性和右樹屬性連接不同的節(jié)點，依次構(gòu)建一顆龐大的樹。

class Node(object):
    """節(jié)點類"""
    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實現(xiàn)。

image