wanpiqiu123's Blog HomeAboutArchivesTagsCategories
数据结构复习2--二叉树
|Data Structure
Word count: 1k|Reading time: 5 min

二叉树的实现

二叉树的结点

1
2
3
4
5
class treeNode():
    def __init__(self, value=None):
        self.data = value
        self.left = None
        self.right = None

和单链表结点差不多，不过都设置成了公有变量。

二叉树的定义

构造函数

1
2
3
4
5
class Tree():
    def __init__(self):
        self.__root = treeNode()
        self.__root.left = None
        self.__root.right = None

定义了二叉树的根结点，以及它的左右子树。初始的根结点的值为0，但是本身是存在的。

基本函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def setRoot(self, root):
    self.__root = root

def addToLeft(self, root, treeNode):
    root.left = treeNode

def addToRight(self, root, treeNode):
    root.right = treeNode

def getRoot(self):
    return self.__root

def size(self):
    p, l, cnt = None, [self.__root], 0
    while l:
        p = l.pop()
        cnt += 1
        if p.left:
            l.append(l.left)
        if p.right:
            l.append(l.right)
    return cnt

size()用来计算整个树的结点个数，这里使用迭代的方法，没有用递归。

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
def hierTraverse(self):
    if not self.__root.data:
        return None
    arr, l = [], [self.__root]
    while l:
        p = l.pop(0)
        arr.append(p.data)
        if p.left:
            l.append(p.left)
        if p.right:
            l.append(p.right)
    return arr

从数组建立与可视化

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
47
48
49
50
51
def establishFromList(self, arr):
    if not arr:
        return
    else:
        p, l, i, res = None, [self.__root], 0, []
        length = len(arr)
        while l:
            p = l.pop(0)
            if arr[i] == '*':
                i += 1
                if i == length:
                    break
            else:
                p.data = arr[i]
                i += 1
                if i == length:
                    break
                p.left, p.right = treeNode(), treeNode()
                l.append(p.left)
                l.append(p.right)
                res.append(p)
        while(res):
            p = res.pop()
            if not p.left.data:
                p.left = None
            if not p.right.data:
                p.right = None

def display(self):
    arr = []
    if not self.__root.data:
        return arr

    def traverseHelper(level, node):

        data = node.data if node else '*'
        if len(arr) <= level:
            arr.append([data])
        else:
            arr[level].append(data)
        if not node:
            return
        traverseHelper(level+1, node.left)
        traverseHelper(level+1, node.right)
    traverseHelper(0, self.__root)
    for i in range(len(arr)-1):
        for j in range(len(arr[i])):
            if arr[i][j] == '*':
                arr[i+1].insert(j*2, '*')
                arr[i+1].insert(j*2, '*')
    return arr[0:-1]

establishFromList()从数组建立二叉树，*代表左/右子树为空，整个二叉树的层次遍历和数组一致。display()用来进行可视化，返回二维数组，外层数组的元素为每层的遍历结果，空的部分用*表示。每层的元素个数为2^n。

前中后序遍历

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def firstTraverse(self):
    if not self.__root.data:
        return []
    arr = []

    def helper(root):
        if not root:
            return
        arr.append(root.data)
        helper(root.left)
        helper(root.right)
    helper(self.__root)
    return arr

def firstTraverseNR(self):
    if not self.__root.data:
        return []
    arr, stack = [], [self.__root]
    while stack:
        node = stack.pop()
        arr.append(node.data)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return arr
    # arr, stack, node = [], [], self.__root
    # while stack or node:
    #     while node:
    #         arr.append(node.data)
    #         stack.append(node)
    #         node = node.left
    #     node = stack.pop()
    #     node = node.right
    # return arr

def middleTraverse(self):
    if not self.__root.data:
        return []
    arr = []

    def helper(root):
        if not root:
            return
        helper(root.left)
        arr.append(root.data)
        helper(root.right)
    helper(self.__root)
    return arr

def middleTraverseNR(self):
    if not self.__root.data:
        return []
    arr, stack, node = [], [], self.__root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        arr.append(node.data)
        node = node.right
    return arr

def postTraverse(self):
    if not self.__root.data:
        return []
    arr = []

    def helper(root):
        if not root:
            return
        helper(root.left)
        helper(root.right)
        arr.append(root.data)
    helper(self.__root)
    return arr

def postTraverseNR(self):
    if not self.__root.data:
        return []
    arr, stack = [], [self.__root]
    while stack:
        node = stack.pop()
        arr.append(node.data)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return arr[::-1]

每一种遍历都使用了递归和非递归(NR)方法实现。前序遍历的非递归方法有两种思路。后序遍历的非递归实现取巧采用中右左的倒序进行输出。

其他做题的时候遇到的函数

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
def getHeight(self):
    if not self.__root.data:
        return 0

    def helper(root, height):
        if not root:
            return height
        return max(helper(root.left, height+1), helper(root.right, height+1))
    return helper(self.__root, 0)

def longestPath(self):
    if not self.__root.data:
        return 0

    def helper(root, length):
        if not root:
            return length
        return max(helper(root.left, length+1), helper(root.right, length+1))
    return 1+helper(self.__root.left, 0)+helper(self.__root.right, 0)

def switch(self):
    if not self.__root.data:
        return

    def helper(root):
        if not root:
            return
        root.left, root.right = root.right, root.left
        if root.left:
            helper(root.left)
        if root.right:
            helper(root.right)
    helper(self.__root)

getHeight()返回数的高度，longestPath()返回树中的最长路径，switch让左右子树递归交换（相当于沿着中轴线对称）。

测试代码

最后是测试代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def testTree():
    tree = Tree()
    tree.establishFromList([1, 2, 3, '*', 4, 5, '*', 6, 7, 8])
    # tree.establishFromList([])
    # tree.establishFromList([1])
    # tree.setRoot(treeNode(2))
    print(tree.hierTraverse())
    print(tree.display())
    print(tree.firstTraverse())
    print(tree.firstTraverseNR())
    print(tree.middleTraverse())
    print(tree.middleTraverseNR())
    print(tree.postTraverse())
    print(tree.postTraverseNR())
    print(tree.getHeight())
    print(tree.longestPath())
    tree.switch()
    print(tree.display())
Author: Jiaming Luo
Link: http://wanpiqiu123.github.io/2020/04/16/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%A4%8D%E4%B9%A02-%E4%BA%8C%E5%8F%89%E6%A0%91/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
PythonAlgorithm