使用 Python 學習資料結構（三）：二元樹

Data Structures
, ,

前言

本文為〈資料結構與演算法〉一文的學習筆記。

二元樹

二元樹（Binary tree）是每個節點最多只有兩個分支的樹結構。二元樹的分支具有左右次序，不能隨意顛倒。

二元樹有以下特性：

  • 二元樹的節點個數可以為 0。
  • 二元樹節點的最大分支度為 2。
  • 二元樹的節點有左、右次序之分。

二元樹的走訪：

  • 前序走訪（Pre-order）：先根後左再右。
  • 中序走訪（In-order）：先左後根再右。
  • 後序走訪（Post-order）：先左後右再根。

函數實作

節點類別

一個 Node 類別的建構函式如下：

1
2
3
4
5
6
7
8
>>> class Node(object):
        def __init__(self, data):
            # 根節點
            self.data = data
            # 左子節點
            self.left = None
            # 右子節點
            self.right = None

新增節點

在 Node 類別建立一個 insert() 函式，以新增節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> def insert(self, data):
        # 如果新增節點等於根（或當前）節點，則返回 False
        if self.data == data:
            return False
        # 如果新增節點小於根（或當前）節點，則新增到左子節點
        elif data < self.data:
            if self.left:
                return self.left.insert(data)
            else:
                self.left = Node(data)
                return True
        # 如果新增節點大於根（或當前）節點，則新增到右子節點
        else:
            if self.right:
                return self.right.insert(data)
            else:
                self.right = Node(data)
                return True

查找節點

在 Node 類別建立一個 find() 函式，以查找節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def find(self, data):
    # 如果新增節點等於根（或當前）節點，則返回 True
    if data == self.data:
        return True
    # 如果新增節點小於根（或當前）節點
    elif data < self.data:
        # 如果左子節點存在，則繼續查找
        if self.left:
            return self.left.find(data)
        # 否則返回 False
        else:
            return False
    # 如果新增節點大於根（或當前）節點
    else:
        # 如果右子節點存在，則繼續查找
        if self.right:
            return self.right.find(data)
        # 否則返回 False
        else:
            return False

印出節點

在 Node 類別建立 pre_order()、in_order() 與 post_order() 函式，以印出節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
>>> def pre_order(self): # 前序走訪
        # 如果根（或當前）節點存在
        if self:
            # 印出根（或當前）節點
            print(str(self.data), end = ' ')
            # 如果左子節點存在，則繼續執行 pre_order() 函式
            if self.left:
                self.left.pre_order()
            # 印出右子節點存在，則繼續執行 pre_order() 函式
            if self.right:
                self.right.pre_order()

>>> def in_order(self): # 中序走訪
        # 如果根（或當前）節點存在
        if self:
            # 如果左子節點存在，則繼續執行 pre_order() 函式
            if self.left:
                self.left.in_order()
            # 印出根（或當前）節點
            print(str(self.data), end = ' ')
            # 印出右子節點存在，則繼續執行 pre_order() 函式
            if self.right:
                self.right.in_order()

>>> def post_order(self): # 後序走訪
        # 如果根（或當前）節點存在
        if self:
            # 如果左子節點存在，則繼續執行 pre_order() 函式
            if self.left:
                self.left.post_order()
            # 印出右子節點存在，則繼續執行 pre_order() 函式
            if self.right:
                self.right.post_order()
            # 印出根（或當前）節點
            print(str(self.data), end = ' ')

樹類別

一個 Tree 類別的基本函式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Tree(object):
    def __init__(self):
        self.root = None

    # 新增節點
    def insert(self, data):
        # 如果根節點存在，則執行 Node 類別的 insert() 函式
        if self.root:
            return self.root.insert(data)
        # 否則設根節點為新增節點
        else:
            self.root = Node(data)
            return True

    # 查找節點
    def find(self, data):
        # 如果根節點存在，則執行 Node 類別的 find() 函式
        if self.root:
            return self.root.find(data)
        # 否則返回 False
        else:
            return False

    # 前序走訪
    def pre_order(self):
        print()
        # 如果根節點存在，則執行 Node 類別的 pre_order() 函式
        if self.root is not None:
            print('Pre-order: ')
            self.root.pre_order()

    # 中序走訪
    def in_order(self):
        print()
        # 如果根節點存在，則執行 Node 類別的 in_order() 函式
        if self.root is not None:
            print('In-order: ')
            self.root.in_order()

    # 後序走訪
    def post_order(self):
        print()
        # 如果根節點存在，則執行 Node 類別的 post_order() 函式
        if self.root is not None:
            print('Post-order: ')
            self.root.post_order()

實例化一個 Tree 類別。

1
>>> tree = Tree()

新增幾個節點。

1
2
3
4
5
6
7
8
9
>>> tree.insert(10)
    tree.insert(12)
    tree.insert(5)
    tree.insert(4)
    tree.insert(20)
    tree.insert(8)
    tree.insert(7)
    tree.insert(15)
    tree.insert(13)

查找節點

1
2
3
4
>>> print(tree.find(1))
False
>>> print(tree.find(12))
True

前序走訪。

1
2
3
>>> tree.pre_order()
Pre-order:
10 5 4 8 7 12 20 15 13

中序走訪。

1
2
3
>>> tree.in_order()
In-order:
4 5 7 8 10 12 13 15 20

後序走訪。

1
2
3
>>> tree.post_order()
Post-order:
4 7 8 5 13 15 20 12 10

程式碼

參考資料