二叉樹的Python實(shí)現(xiàn)

dinghj 2019-04-22

展開全文

樹的定義與基本術(shù)語

??樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)；在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一；在機(jī)器學(xué)習(xí)中，決策樹，隨機(jī)森林，GBDT等是常見的樹模型。

??樹（Tree）是 $n(n\geq 0)$ 個(gè)結(jié)點(diǎn)的有限集。在任意一棵樹中：（1）有且僅有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)；（2）當(dāng) n>1 時(shí)，其余節(jié)點(diǎn)可分為 m(m>0) 個(gè)互不相交的有限集 T_1,T_2,...,T_m, 其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

圖1 樹型結(jié)構(gòu)

??在圖1，該樹一共有13個(gè)節(jié)點(diǎn)，其中A是根，其余節(jié)點(diǎn)分成3個(gè)互不相交的子集： $T_1=\{B,E,F,K,L\}$ , $T_2=\{C,G\}$ , $T_3=\{D,H,I,J,M\}$ ; T_1,T_2和T_3 都是根A的子樹，且本身也是一棵樹。例如 T_1 ，其根為B，其余節(jié)點(diǎn)分為兩個(gè)互不相交的子集； $T_{11}=\{E,K,L\}$ , $T_{12}=\{F\}$ 。 $T_{11}$ 和 $T_{12}$ 都是B的子樹。而在 $T_{11}$ 中E是根， $\{K\}$ 和 $\{L\}$ 是E的兩棵互不相交的子樹，其本身又是只有一個(gè)根節(jié)點(diǎn)的樹。

??接下來講一下樹的基本術(shù)語。

??樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。節(jié)點(diǎn)擁有的子樹數(shù)量稱為節(jié)點(diǎn)的度（Degree）。在圖1中，A的度為3，B的度為2，C的度為1，F(xiàn)的度為0。度為0的結(jié)點(diǎn)稱為葉子（Leaf）結(jié)點(diǎn)。在圖1中，K,L,F,G,M,I,J都是該樹的葉子。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。樹的度是指樹內(nèi)個(gè)結(jié)點(diǎn)的度的最大值。

??結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（Child），相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親（Parent）。在圖1,中，D是A的孩子，A是D的雙親。同一個(gè)雙親的孩子之間互稱兄弟（Sibling）。在圖1中，H,I,J互為兄弟。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。在圖1中，M的祖先為A,D,H。對(duì)應(yīng)地，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。在圖1中，B的子孫為E,F,K,L。

??樹的層次(Level)是從根開始，根為第一層，根的孩子為第二層等。雙親在同一層的結(jié)點(diǎn)互為同兄弟，在圖1中，K,L,M互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Depth)或高度，在圖1中，樹的深度為4。

??如果將樹中結(jié)點(diǎn)的各子樹看成從左到右是有次序的（即不能交換），則稱該樹為有序樹，否則為無序樹。

??森林（Forest）是 $m(m\geq 0)$ 棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。在機(jī)器學(xué)習(xí)模型中，決策樹為樹型結(jié)構(gòu)，而隨機(jī)森林為森林，是由若干決策樹組成的森林。

二叉樹的定義與基本性質(zhì)

??二叉樹（Binary Tree）是一種特殊的樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），且二叉樹的子樹有左右之分，其次序不能任意顛倒（有序樹）。

??根據(jù)二叉樹的定義，其具有下列重要性質(zhì)：（這里不給出證明，證明細(xì)節(jié)可參考清華大學(xué)出版社嚴(yán)蔚敏吳偉民的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》）

性質(zhì)1）在二叉樹的第層上至多有 $2^{i-1}$ 個(gè)結(jié)點(diǎn) $(i\geq 1)$ 。

性質(zhì)2）深度為的二叉樹至多有 $2^{k}-1$ 個(gè)結(jié)點(diǎn) $(k\geq 1)$ 。

性質(zhì)3）對(duì)任何一棵二叉樹，如果其葉子節(jié)點(diǎn)數(shù)為 $n_{0}$ ,度為2的結(jié)點(diǎn)數(shù)為 n_2 ，則 n_0=n_2+1 。

??一棵深度為且有 2^k-1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。深度為，結(jié)點(diǎn)數(shù)數(shù)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為的滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。在下圖2中，（a）為滿二叉樹，（b）為完全二叉樹。

圖2 特殊形態(tài)的二叉樹

??下面介紹完全二叉樹的兩個(gè)特性：

性質(zhì)4）具有個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 $[log_{2}n]+1$ ,其中 [x] 表示不大于x的最大整數(shù)。

性質(zhì)5）如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第一層到最后一層，每層從左到右），則對(duì)任一結(jié)點(diǎn) $i(1\leq i\leq n)$ ,有：

（1）如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1,則其雙親結(jié)點(diǎn)為[1/2]。

（2）如果2i>n，則結(jié)點(diǎn)i無左孩子；否則其左孩子是結(jié)點(diǎn)2i。

（3）如果2i+1>n，則結(jié)點(diǎn)i無右孩子；否則其右孩子是結(jié)點(diǎn)2i+1。

??介紹完了二叉樹的定義及基本性質(zhì)，接下來，我們需要了解二叉樹的遍歷。所謂二叉樹的遍歷，指的是如何按某種搜索路徑巡防樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。對(duì)于二叉樹，常見的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷。這些遍歷方法一般使用遞歸算法實(shí)現(xiàn)。

??先序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）訪問根節(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

??中序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。

??后序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。

??層序遍歷的操作定義為：若二叉樹為空，為空操作；否則從上到下、從左到右按層次進(jìn)行訪問。

??如對(duì)于下圖3，

圖3 示例二叉樹

其先序遍歷、中序遍歷、后序遍歷、層序遍歷的結(jié)果為：

先序遍歷為:
18 7 3 4 11 5 1 3 6 2 4 
中序遍歷為:
3 7 4 18 1 5 3 11 2 6 4 
后序遍歷為:
3 4 7 1 3 5 2 4 6 11 18 
層序遍歷為:
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]

??關(guān)于二叉樹的存儲(chǔ)結(jié)構(gòu)，可以選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于表示二叉樹的鏈表中的結(jié)點(diǎn)至少包含3個(gè)域：數(shù)據(jù)域和左、右指針。下面會(huì)給出如何利用利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹（Python實(shí)現(xiàn)）。

二叉樹的Python實(shí)現(xiàn)

??了解了二叉樹的基本情況后，筆者使用Python實(shí)現(xiàn)了二叉樹，其完整的Python代碼（Binary_Tree.py）如下：

from graphviz import Digraph
import uuid
from random import sample

# 二叉樹類
class BTree(object):

    # 初始化
    def __init__(self, data=None, left=None, right=None):
        self.data = data    # 數(shù)據(jù)域
        self.left = left    # 左子樹
        self.right = right  # 右子樹
        self.dot = Digraph(comment='Binary Tree')

    # 前序遍歷
    def preorder(self):

        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()

    # 中序遍歷
    def inorder(self):

        if self.left is not None:
            self.left.inorder()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.inorder()

    # 后序遍歷
    def postorder(self):

        if self.left is not None:
            self.left.postorder()
        if self.right is not None:
            self.right.postorder()
        if self.data is not None:
            print(self.data, end=' ')

    # 層序遍歷
    def levelorder(self):

        # 返回某個(gè)節(jié)點(diǎn)的左孩子
        def LChild_Of_Node(node):
            return node.left if node.left is not None else None
        # 返回某個(gè)節(jié)點(diǎn)的右孩子
        def RChild_Of_Node(node):
            return node.right if node.right is not None else None

        # 層序遍歷列表
        level_order = []
        # 是否添加根節(jié)點(diǎn)中的數(shù)據(jù)
        if self.data is not None:
            level_order.append([self])

        # 二叉樹的高度
        height = self.height()
        if height >= 1:
            # 對(duì)第二層及其以后的層數(shù)進(jìn)行操作, 在level_order中添加節(jié)點(diǎn)而不是數(shù)據(jù)
            for _ in range(2, height + 1):
                level = []  # 該層的節(jié)點(diǎn)
                for node in level_order[-1]:
                    # 如果左孩子非空，則添加左孩子
                    if LChild_Of_Node(node):
                        level.append(LChild_Of_Node(node))
                    # 如果右孩子非空，則添加右孩子
                    if RChild_Of_Node(node):
                        level.append(RChild_Of_Node(node))
                # 如果該層非空，則添加該層
                if level:
                    level_order.append(level)

            # 取出每層中的數(shù)據(jù)
            for i in range(0, height):  # 層數(shù)
                for index in range(len(level_order[i])):
                    level_order[i][index] = level_order[i][index].data

        return level_order

    # 二叉樹的高度
    def height(self):
        # 空的樹高度為0, 只有root節(jié)點(diǎn)的樹高度為1
        if self.data is None:
            return 0
        elif self.left is None and self.right is None:
            return 1
        elif self.left is None and self.right is not None:
            return 1 + self.right.height()
        elif self.left is not None and self.right is None:
            return 1 + self.left.height()
        else:
            return 1 + max(self.left.height(), self.right.height())

    # 二叉樹的葉子節(jié)點(diǎn)
    def leaves(self):

        if self.data is None:
            return None
        elif self.left is None and self.right is None:
            print(self.data, end=' ')
        elif self.left is None and self.right is not None:
            self.right.leaves()
        elif self.right is None and self.left is not None:
            self.left.leaves()
        else:
            self.left.leaves()
            self.right.leaves()

    # 利用Graphviz實(shí)現(xiàn)二叉樹的可視化
    def print_tree(self, save_path='./Binary_Tree.gv', label=False):

        # colors for labels of nodes
        colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red']

        # 繪制以某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的二叉樹
        def print_node(node, node_tag):
            # 節(jié)點(diǎn)顏色
            color = sample(colors,1)[0]
            if node.left is not None:
                left_tag = str(uuid.uuid1())            # 左節(jié)點(diǎn)的數(shù)據(jù)
                self.dot.node(left_tag, str(node.left.data), style='filled', color=color)    # 左節(jié)點(diǎn)
                label_string = 'L' if label else ''    # 是否在連接線上寫上標(biāo)簽，表明為左子樹
                self.dot.edge(node_tag, left_tag, label=label_string)   # 左節(jié)點(diǎn)與其父節(jié)點(diǎn)的連線
                print_node(node.left, left_tag)

            if node.right is not None:
                right_tag = str(uuid.uuid1())
                self.dot.node(right_tag, str(node.right.data), style='filled', color=color)
                label_string = 'R' if label else ''  # 是否在連接線上寫上標(biāo)簽，表明為右子樹
                self.dot.edge(node_tag, right_tag, label=label_string)
                print_node(node.right, right_tag)

        # 如果樹非空
        if self.data is not None:
            root_tag = str(uuid.uuid1())                # 根節(jié)點(diǎn)標(biāo)簽
            self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1)[0])     # 創(chuàng)建根節(jié)點(diǎn)
            print_node(self, root_tag)

        self.dot.render(save_path)                              # 保存文件為指定文件

??在上述代碼中，筆者創(chuàng)建了二叉樹類BTree，實(shí)現(xiàn)了如下方法：

初始化方法：該樹存放的數(shù)據(jù)為data,左子樹，右子樹為left和right，默認(rèn)均為None;

preorder()方法：遞歸實(shí)現(xiàn)二叉樹的先序遍歷；

inorder()方法：遞歸實(shí)現(xiàn)二叉樹的中序遍歷；

postorder()方法：遞歸實(shí)現(xiàn)二叉樹的后序遍歷；

levelorder()方法：遞歸實(shí)現(xiàn)二叉樹的層序遍歷；

height()方法：計(jì)算二叉樹的高度；

leaves()方法：計(jì)算二叉樹的葉子結(jié)點(diǎn)；

print_tree()方法：利用Graphviz實(shí)現(xiàn)二叉樹的可視化，需要設(shè)置的參數(shù)為save_path和label，save_path為文件保存路徑，默認(rèn)的保存路徑為當(dāng)前路徑下的Binary_Tree.gv,可以用戶自己設(shè)置；label為是否在Graphviz文件中添加二叉樹的左右子樹的標(biāo)簽，用于分清哪棵是左子樹，哪棵是右子樹，可以用用戶自己設(shè)置。

??若我們需要實(shí)現(xiàn)圖3的示例二叉樹，完整的Python代碼如下：

from Binary_Tree import BTree

# 構(gòu)造二叉樹, BOTTOM-UP METHOD
right_tree = BTree(6)
right_tree.left = BTree(2)
right_tree.right = BTree(4)

left_tree = BTree(5)
left_tree.left = BTree(1)
left_tree.right = BTree(3)

tree = BTree(11)
tree.left = left_tree
tree.right = right_tree

left_tree = BTree(7)
left_tree.left = BTree(3)
left_tree.right = BTree(4)

right_tree = tree # 增加新的變量
tree = BTree(18)
tree.left = left_tree
tree.right = right_tree

print('先序遍歷為:')
tree.preorder()
print()

print('中序遍歷為:')
tree.inorder()
print()

print('后序遍歷為:')
tree.postorder()
print()

print('層序遍歷為:')
level_order = tree.levelorder()
print(level_order)
print()

height = tree.height()
print('樹的高度為%s.' % height)

print('葉子節(jié)點(diǎn)為：')
tree.leaves()
print()

# 利用Graphviz進(jìn)行二叉樹的可視化
tree.print_tree(save_path='E://BTree.gv', label=True)

??OK,當(dāng)我們運(yùn)行上述代碼時(shí)，可以得到該二叉樹的一些信息，輸出結(jié)果如下：

先序遍歷為:
18 7 3 4 11 5 1 3 6 2 4 
中序遍歷為:
3 7 4 18 1 5 3 11 2 6 4 
后序遍歷為:
3 4 7 1 3 5 2 4 6 11 18 
層序遍歷為:
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]

樹的高度為4.
葉子節(jié)點(diǎn)為：
3 4 1 3 2 4

該P(yáng)ython代碼的優(yōu)勢在于利用Graphviz實(shí)現(xiàn)了二叉樹的可視化，可以形象直觀地得到二叉樹的圖形。在上面的代碼中，我們可以看到，構(gòu)建二叉樹不是很方便，需要手動(dòng)地一個(gè)個(gè)結(jié)點(diǎn)去添加。那么，如果當(dāng)我們需要根據(jù)某個(gè)列表，按列表順序去構(gòu)建二叉樹時(shí)，即二叉樹的層序遍歷為該列表，那又該怎么辦呢？有什么好的辦法嗎？

??答案是必須有！按照某個(gè)列表去構(gòu)建二叉樹的完整Python代碼如下：

from Binary_Tree import BTree

# 利用列表構(gòu)造二叉樹
# 列表中至少有一個(gè)元素
def create_BTree_By_List(array):

    i = 1
    # 將原數(shù)組拆成層次遍歷的數(shù)組，每一項(xiàng)都儲(chǔ)存這一層所有的節(jié)點(diǎn)的數(shù)據(jù)
    level_order = []
    sum = 1

    while sum < len(array):
        level_order.append(array[i-1:2*i-1])
        i *= 2
        sum += i
    level_order.append(array[i-1:])
    # print(level_order)

    # BTree_list: 這一層所有的節(jié)點(diǎn)組成的列表
    # forword_level: 上一層節(jié)點(diǎn)的數(shù)據(jù)組成的列表
    def Create_BTree_One_Step_Up(BTree_list, forword_level):

        new_BTree_list = []
        i = 0
        for elem in forword_level:
            root = BTree(elem)
            if 2*i < len(BTree_list):
                root.left = BTree_list[2*i]
            if 2*i+1 < len(BTree_list):
                root.right = BTree_list[2*i+1]
            new_BTree_list.append(root)
            i += 1

        return new_BTree_list

    # 如果只有一個(gè)節(jié)點(diǎn)
    if len(level_order) == 1:
        return BTree(level_order[0][0])
    else: # 二叉樹的層數(shù)大于1

        # 創(chuàng)建最后一層的節(jié)點(diǎn)列表
        BTree_list = [BTree(elem) for elem in level_order[-1]]

        # 從下往上，逐層創(chuàng)建二叉樹
        for i in range(len(level_order)-2, -1, -1):
            BTree_list = Create_BTree_One_Step_Up(BTree_list, level_order[i])

        return BTree_list[0]

#array = list(range(1,19))
array = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
tree = create_BTree_By_List(array)

print('先序遍歷為:')
tree.preorder()
print()

height = tree.height()
print('\n樹的高度為%s.\n'%height)

print('層序遍歷為:')
level_order = tree.levelorder()
print(level_order)
print()

print('葉子節(jié)點(diǎn)為：')
tree.leaves()
print()

# 利用Graphviz進(jìn)行二叉樹的可視化
tree.print_tree(save_path='E://create_btree_by_list.gv', label=True)

在上述程序中，筆者利用create_BTree_By_List()函數(shù)實(shí)現(xiàn)了按照某個(gè)列表去構(gòu)建二叉樹，輸入的參數(shù)array為列表，要求列表中至少有一個(gè)元素。運(yùn)行上述程序，我們得到的26個(gè)大寫字母列表所構(gòu)建的二叉樹的圖像如下：

圖4 26個(gè)大寫字母列表所構(gòu)建的二叉樹

輸出的結(jié)果如下：

先序遍歷為:
A B D H P Q I R S E J T U K V W C F L X Y M Z G N O 

樹的高度為5.

層序遍歷為:
[['A'], ['B', 'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']]

葉子節(jié)點(diǎn)為：
P Q R S T U V W X Y Z N O

總結(jié)

??二叉樹是很多重要算法及模型的基礎(chǔ)，比如二叉搜索樹（BST），哈夫曼樹(Huffman Tree)，CART決策樹等。本文先介紹了樹的基本術(shù)語，二叉樹的定義與性質(zhì)及遍歷、儲(chǔ)存，然后筆者自己用Python實(shí)現(xiàn)了二叉樹的上述方法，筆者代碼的最大亮點(diǎn)在于實(shí)現(xiàn)了二叉樹的可視化，這個(gè)功能是激動(dòng)人心的。

??在Python中，已有別人實(shí)現(xiàn)好的二叉樹的模塊，它是binarytree模塊，其官方文檔的網(wǎng)址為：https:///project/binarytree/。其使用的例子如下：

binarytree模塊演示

關(guān)于這個(gè)模塊的更多功能，可參考其官方文檔。當(dāng)然，筆者還是建議您親自實(shí)現(xiàn)一下二叉樹哦，這樣能夠加深對(duì)二叉樹的理解~

??在后面的文章中，筆者將會(huì)介紹二叉搜索樹（BST），哈夫曼樹(Huffman Tree)等，歡迎大家關(guān)注~

注意：本人現(xiàn)已開通微信公眾號(hào)： Python爬蟲與算法（微信號(hào)為：easy_web_scrape），歡迎大家關(guān)注哦~~

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： dinghj > 《web編程》

舉報(bào)/認(rèn)領(lǐng)