什么是树

树的实现

树的实现主要有两种方式:列表之列表和节点之引用

文章使用节点之引用实现。

  • BinaryTree() 创建一个二叉树
  • getLeft()返回当前节点的左子节点所对应的树
  • getRight() 返回当前节点的右子节点所对应的树
  • setVal(val) 在当前节点中存储val
  • insertLeft(val)新建一颗二叉树，并将其作为当前节点的左子节点
  • insertRight(val) 新建一颗二叉树，并将其作为当前节点的右子节点

  1. 首先定义一个简单的类。

    1
    2
    3
    4
    5
    class BinaryTree:
        def __init__(self,val=None):
            self.val = val
            self.left = None
            self.right = None

  2. 节点之引用 的要点是，属性left和right 会指向BinaryTree类的其他实例。也就是说，向树中插入新的左子树，我们会创建另一个BinaryTree实例，并将根节点的self.left 指向新树。

    下面是插入左子节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 插入左子节点
    def insertLeft(self,newNode):
        if self.left == None:
            self.left = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.left
            self.left = t

    ​ 在插入左子树时，必须考虑两种情况，一种是原本没有左子节点。此时，只需在树种添加一个节点即可。第二种情况是已经存在左子节点。此时，插入一个节点，并将已有的左子节点降一层。

    插入右子节点同理。

    1
    2
    3
    4
    5
    6
    7
    8
    # 插入右子节点
    def insertRight(self,newNode):
        if self.right == None:
            self.right = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.right
            self.right = t

  3. 节点访问函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 访问当前节点的左子树
    def getLeft(self):
        return self.left
    # 访问当前节点的右子树
    def getRight(self):
        return self.right
    # 设置当前的节点的值
    def setVal(self,val):
        self.val = val
    # 获取当前节点的值
    def getVal(self,val):
        return self.val

遍历二叉树

前序遍历

1
2
3
4
5
6
def pre_order(root):
    if not root:
        return
    print(root.val)
    pre_order(root.left)
    pre_order(root.right)

中序遍历

1
2
3
4
5
6
def mid_order(root):
    if not root:
        return
    mid_order(root.left)
    print(root.val)
    mid_order(root.right)

后续遍历

1
2
3
4
5
6
def post_order(root):
    if not root:
        return
    mid_order(root.left)
    mid_order(root.right)
     print(root.val)

将有序的整数数组转换成二叉树

二叉排序树

任意节点node: 如果有左孩子节点left,则left小于node

​ 如果有右孩子节点right，则right的值大于node

按中序遍历，节点就是有序输出

例如:数组[1,2,3,4,5,6,7,8,9,10]

分析

6是中位数,分成1，2，3，4，5和7，8，9，10；1，2，3，4其中3是中位数，分为1，2和4，5；7，8，9，10分为7，8和10，继续递归….

image-20230220201701035

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
class BinaryTree:
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None

    def insertLeft(self,newNode):
        if  self.left == None:
            self.left = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.left
            self.left = t
    def insertRight(self,newNode):
        if  self.right == None:
            self.right = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.right
            self.right = t

    # 访问函数
    def getLeft(self):
        return self.left
    def getRight(self):
        return self.right
    def getVal(self):
        return self.val
    def setVal(self,val):
        self.val = val

# 数组转换成树
def array_to_tree(arr,start,end):
    root = None
    if end >= start:
        root = BinaryTree()
        mid = (start+end+1)//2
        root.val = arr[mid]
        root.left = array_to_tree(arr,start,mid-1)
        root.right = array_to_tree(arr, mid+1, end)
    else:
        root = None
    return root

# 中序遍历
def mid_order(root):
    if not root:
        return
    mid_order(root.left)
    print(root.val)
    mid_order(root.right)

if __name__ == '__main__':
    arr = [1,2,3,4,5,6,7,8,9,10]
    print('原始数据:',arr)
    root=array_to_tree(arr,0,len(arr)-1)
    mid_order(root)

树的应用