資料結構 之 '樹'

python實作二叉樹的廣度周遊、深度周遊以及排序二叉樹

樹

定義

樹（Tree）是n（n>=0)個結點的有限集。n=0時稱為空樹。在任意一顆非空樹中：

1）有且僅有一個特定的稱為根（Root）的結點；

2）當n>1時，其餘結點可分為m(m>0)個互不相交的有限集T1、T2、......、Tn，其中每一個集合本身又是一棵樹，并且稱為根的子樹。

此外，樹的定義還需要強調以下兩點：

1）n>0時根結點是唯一的，不可能存在多個根結點，資料結構中的樹隻能有一個根結點。

2）m>0時，子樹的個數沒有限制，但它們一定是互不相交的。

示例樹：

圖1.1

由樹的定義可以看出，樹的定義使用了遞歸的方式。遞歸在樹的學習過程中起着重要作用，如果對于遞歸不是十分了解，建議先看看遞歸算法

結點的度

結點擁有的子樹數目稱為結點的度。

圖1.2中标注了圖1.1所示樹的各個結點的度。

圖1.2 度示意圖

結點關系

結點子樹的根結點為該結點的孩子結點。相應該結點稱為孩子結點的雙親結點。

圖1.2中，A為B的雙親結點，B為A的孩子結點。

同一個雙親結點的孩子結點之間互稱兄弟結點。

圖1.2中，結點B與結點C互為兄弟結點。

結點層次

從根開始定義起，根為第一層，根的孩子為第二層，以此類推。

圖1.3表示了圖1.1所示樹的層次關系

圖1.3 層示意圖

樹的深度

樹中結點的最大層次數稱為樹的深度或高度。圖1.1所示樹的深度為4。

二叉樹

二叉樹是n(n>=0)個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分别稱為根結點的左子樹和右子樹組成。

圖2.1展示了一棵普通二叉樹：

圖2.1 二叉樹

二叉樹特點

由二叉樹定義以及圖示分析得出二叉樹有以下特點：

1）每個結點最多有兩顆子樹，是以二叉樹中不存在度大于2的結點。

2）左子樹和右子樹是有順序的，次序不能任意颠倒。

3）即使樹中某結點隻有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹性質

1）在二叉樹的第i層上最多有2i-1 個節點 。（i>=1）

2）二叉樹中如果深度為k,那麼最多有2k-1個節點。(k>=1）

3）n0=n2+1 n0表示度數為0的節點數，n2表示度數為2的節點數。

4）在完全二叉樹中，具有n個節點的完全二叉樹的深度為[log2n]+1，其中[log2n]是向下取整。

5）若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編号，則對完全二叉樹中任意一個編号為 i 的結點有如下特性：

(1) 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編号為 [i/2] 的結點為其雙親結點;

(2) 若 2i>n，則該結點無左孩子， 否則，編号為 2i 的結點為其左孩子結點；

(3) 若 2i+1>n，則該結點無右孩子結點， 否則，編号為2i+1 的結點為其右孩子結點。

斜樹

斜樹：所有的結點都隻有左子樹的二叉樹叫左斜樹。所有結點都是隻有右子樹的二叉樹叫右斜樹。這兩者統稱為斜樹。

圖2.2 左斜樹

圖2.3 右斜樹

滿二叉樹

滿二叉樹：在一棵二叉樹中。如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹的特點有：

1）葉子隻能出現在最下一層。出現在其它層就不可能達成平衡。

2）非葉子結點的度一定是2。

3）在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。

圖2.4 滿二叉樹

完全二叉樹

完全二叉樹：對一顆具有n個結點的二叉樹按層編号，如果編号為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編号為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。

圖2.5展示一棵完全二叉樹

圖2.5 完全二叉樹

特點：

1）葉子結點隻能出現在最下層和次下層。

2）最下層的葉子結點集中在樹的左部。

3）倒數第二層若存在葉子結點，一定在右部連續位置。

4）如果結點度為1，則該結點隻有左孩子，即沒有右子樹。

5）同樣結點數目的二叉樹，完全二叉樹深度最小。

注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。

二叉樹的存儲結構

順序存儲

二叉樹的順序存儲結構就是使用一維數組存儲二叉樹中的結點，并且結點的存儲位置，就是數組的下标索引。

圖2.6

圖2.6所示的一棵完全二叉樹采用順序存儲方式，如圖2.7表示：

圖2.7 順序存儲

由圖2.7可以看出，當二叉樹為完全二叉樹時，結點數剛好填滿數組

Python實作二叉樹的深廣度周遊

class Node(object):
    """
    封裝節點
    """
    def __init__(self, item):
        # 根節點
        self.item = item
        # 左葉子節點
        self.left = None
        # 右葉子節點
        self.right = None


class Tree(object):
    def __init__(self):
        """
        初始化一個空樹
        """
        self.root = None

    def addNode(self, item):
        """
        添加節點
        :param item:
        :return:
        """
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        cur = self.root
        q_list = [cur]

        while True:
            first_item = q_list.pop(0)
            if first_item.left != None:
                q_list.append(first_item.left)
            else:
                first_item.left = node
                break

            if first_item.right != None:
                q_list.append(first_item.right)
            else:
                first_item.right = node
                break

    def travel(self):
        """
        廣度周遊
        :return:
        """
        cur = self.root
        q_list = [cur]
        while q_list:
            first_item = q_list.pop(0)
            print(first_item.item)
            if first_item.left != None:
                q_list.append(first_item.left)

            if first_item.right != None:
                q_list.append(first_item.right)

    def forward(self, root):
        """
        深度周遊（前序周遊 —— 根左右）
        :param root: 子樹的根節點
        :return:
        """
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)

    def middle(self, root):
        """
        深度周遊（中序周遊 —— 左根右）
        :param root: 子樹的根節點
        :return:
        """
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)

    def back(self, root):
        """
        深度周遊（後序周遊 —— 左右根）
        :param root: 子樹的根節點
        :return:
        """
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 16):
        tree.addNode(i)

    # tree.travel()

    # tree.forward(tree.root)
    # tree.middle(tree.root)
    # tree.back(tree.root)

           

排序二叉樹

具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

（3）左、右子樹也分别為二叉排序樹；

（4）沒有鍵值相等的結點。

中序周遊作用在排序二叉樹中，周遊的結果為有序！

class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


class SortTree(object):
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return

        cur = self.root
        while True:
            if cur.item < item:
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right

            else:
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left

    def middle(self, root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)


if __name__ == '__main__':
    tree = SortTree()
    for i in [2, 5, 7, 1, 3, 8, 4, 10]:
        tree.add(i)

    tree.middle(tree.root)
    
    
# 1
# 2
# 3
# 4
# 5
# 7
# 8
# 10    

           

抟扶搖而上者九萬裡