深圳大学 数据结构OJ—二叉树(Python)_深圳大学 oj

深圳大学 数据结构OJ—二叉树(Python)

前言

本文是深圳大学数据结构实验课的一些记录，考虑到现在这门课基本没有Python版本的题解。所以特此整理出来，让Python programmer也可以更好地掌握这门课的内容。同时也是督促自己更高质量地完成实验。

A. DS二叉树—二叉树构建与遍历

题目描述

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘#’表示，连续输入t行。

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘#’表示，连续输入t行

输出

输出每个二叉树的先序遍历、中序遍历和后序遍历结果。

题解

class BiTreeNode():
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class BiTree():
    # 用先序遍历的结果创建二叉树，空节点用'#'表示
    # 采用递归建树
    def createBiTree(self, PreOrderResult: str):
        self.Treestring = PreOrderResult
        if len(self.Treestring) == 0:
            return None
        if self.Treestring[0] == '#':
            return None
        root = BiTreeNode(self.Treestring[0])
        self.Treestring = self.Treestring[1:]
        root.lchild = self.createBiTree(self.Treestring)
        self.Treestring = self.Treestring[1:]
        root.rchild = self.createBiTree(self.Treestring)
        return root

    def preOrder(self, root):
        if root == None:
            return
        print(root.data, end='')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print(root.data, end='')
        self.inOrder(root.rchild)

    def postOrder(self, root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print(root.data, end='')

if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        PreOrderResult = input()
        tree = BiTree()
        root = tree.createBiTree(PreOrderResult)
        tree.preOrder(root)
        print()
        tree.inOrder(root)
        print()
        tree.postOrder(root)
        print()
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

PS

值得注意的是，这道题的题解和之后的建树有点不一样。A题的建树函数参数是字符串，但是在后面的题中，空结点用‘0’表示而非本题的‘#’。如果用同样的建树函数，会出现不知原因的错误，导致在所有的输出中都出现一个不知来源的None。所以之后的建树函数的参数会变成list的形式。

B. DS二叉树–叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。

提示：叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

逐行输出每个二叉树的包含的叶子数量

题解

class BiTreeNode():
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class BiTree():
    # 用先序遍历的结果创建二叉树，空节点用'0'表示
    # 采用递归建树
    def createBiTree(self, PreOrderResult: str):
        self.Treestring = PreOrderResult
        self.leafCount = 0
        if len(self.Treestring) == 0:
            return None
        if self.Treestring[0] == '0':
            return None
        root = BiTreeNode(self.Treestring[0])
        self.Treestring = self.Treestring[1:]
        root.lchild = self.createBiTree(self.Treestring)
        self.Treestring = self.Treestring[1:]
        root.rchild = self.createBiTree(self.Treestring)
        return root

    def preOrder(self, root):
        if root == None:
            return
        print(root.data, end='')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print(root.data, end='')
        self.inOrder(root.rchild)

    def postOrder(self, root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print(root.data, end='')

    def countLeaf(self, root):
        if root == None:
            return
        if root.lchild == None and root.rchild == None:
            self.leafCount += 1
        self.countLeaf(root.lchild)
        self.countLeaf(root.rchild)
        return self.leafCount

if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        PreOrderResult = input()
        tree = BiTree()
        root = tree.createBiTree(PreOrderResult)
        print(tree.countLeaf(root))
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

C. DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行

输出

第一行按先序遍历，输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

题解

class BiTreeNode():
    def __init__(self, data, parent=None, lchild=None, rchild=None):
        self.data = data
        self.parent = parent
        self.lchild = lchild
        self.rchild = rchild

class BiTree():
    # 用先序遍历的结果创建二叉树，空节点用'0'表示
    # 采用递归建树
    def createBiTree(self, PreOrderResult: list):
        if len(PreOrderResult) == 0:
            return None
        if PreOrderResult[0] == '0':
            PreOrderResult.pop(0)
            return None
        root = BiTreeNode(PreOrderResult[0])
        PreOrderResult.pop(0)
        root.lchild = self.createBiTree(PreOrderResult)
        if root.lchild != None:
            root.lchild.parent = root
        root.rchild = self.createBiTree(PreOrderResult)
        if root.rchild != None:
            root.rchild.parent = root
        return root

    def preOrder(self, root):
        if root == None:
            return
        print(root.data, end='')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print(root.data, end='')
        self.inOrder(root.rchild)

    def postOrder(self, root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print(root.data, end='')

    def findLeaf(self, root):
        if root == None:
            return
        if root.lchild == None and root.rchild == None:
            print(root.data, end=' ')
        self.findLeaf(root.lchild)
        self.findLeaf(root.rchild)

    def findLeafParent(self, root):
        if root == None:
            return
        if root.lchild == None and root.rchild == None:
            print(root.parent.data, end=' ')
        self.findLeafParent(root.lchild)
        self.findLeafParent(root.rchild)

if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        PreOrderResult = input()
        PreOrderResult = list(PreOrderResult)
        tree = BiTree()
        root = tree.createBiTree(PreOrderResult)
        tree.findLeaf(root)
        print()
        tree.findLeafParent(root)
        print()
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

D. DS二叉树–层次遍历

题目描述

层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。

建树方法采用“先序遍历+空树用0表示”的方法

建议使用队列结构实现，算法框架如下：

定义一个空白队列和一个树结点指针p

设T是指向根结点的指针变量，若二叉树为空，则返回；否则，令p=T，p入队，执行以下循环：

(1)队首元素出队到p；

(2)访问p所指向的结点；

(3)p所指向的结点的左、右子结点依次入队。

(4)跳转步骤1循环，直到队列空为止

例如把上述算法中的访问操作定义为输出，算法结果就是把二叉树按层次遍历输出

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

逐行输出每个二叉树的层次遍历结果

题解

class BiTreeNode():
    def __init__(self, data, parent=None, lchild=None, rchild=None):
        self.data = data
        self.parent = parent
        self.lchild = lchild
        self.rchild = rchild

class BiTree():
    # 用先序遍历的结果创建二叉树，空节点用'0'表示
    # 采用递归建树
    def createBiTree(self, PreOrderResult: list):
        if len(PreOrderResult) == 0:
            return None
        if PreOrderResult[0] == '0':
            PreOrderResult.pop(0)
            return None
        root = BiTreeNode(PreOrderResult[0])
        PreOrderResult.pop(0)
        root.lchild = self.createBiTree(PreOrderResult)
        if root.lchild != None:
            root.lchild.parent = root
        root.rchild = self.createBiTree(PreOrderResult)
        if root.rchild != None:
            root.rchild.parent = root
        return root

    def preOrder(self, root):
        if root == None:
            return
        print(root.data, end='')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print(root.data, end='')
        self.inOrder(root.rchild)

    def postOrder(self, root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print(root.data, end='')

    # 层次遍历从上至下，从左至右访问每个节点并输出值
    def levelOrder(self, root):
        if root == None:
            return
        queue = []
        queue.append(root)
        while len(queue) != 0:
            node = queue.pop(0)
            print(node.data, end='')
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        PreOrderResult = input()
        PreOrderResult = list(PreOrderResult)
        tree = BiTree()
        root = tree.createBiTree(PreOrderResult)
        tree.levelOrder(root)
        print()
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

E. DS树–二叉树高度

题目描述

给出一棵二叉树，求它的高度。

注意，二叉树的层数是从1开始

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每行输出一个二叉树的高度

题解

class BiTreeNode():
    def __init__(self, data, parent=None, lchild=None, rchild=None):
        self.data = data
        self.parent = parent
        self.lchild = lchild
        self.rchild = rchild

class BiTree():
    # 用先序遍历的结果创建二叉树，空节点用'0'表示
    # 采用递归建树
    def createBiTree(self, PreOrderResult: list):
        if len(PreOrderResult) == 0:
            return None
        if PreOrderResult[0] == '0':
            PreOrderResult.pop(0)
            return None
        root = BiTreeNode(PreOrderResult[0])
        PreOrderResult.pop(0)
        root.lchild = self.createBiTree(PreOrderResult)
        if root.lchild != None:
            root.lchild.parent = root
        root.rchild = self.createBiTree(PreOrderResult)
        if root.rchild != None:
            root.rchild.parent = root
        return root

    def preOrder(self, root):
        if root == None:
            return
        print(root.data, end='')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print(root.data, end='')
        self.inOrder(root.rchild)

    def postOrder(self, root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print(root.data, end='')

    def BiDepth(self, root):
        if root == None:
            return 0
        ldepth = self.BiDepth(root.lchild)
        rdepth = self.BiDepth(root.rchild)
        return max(ldepth, rdepth) + 1

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        PreOrderResult = input()
        PreOrderResult = list(PreOrderResult)
        tree = BiTree()
        root = tree.createBiTree(PreOrderResult)
        print(tree.BiDepth(root))
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

F. DS二叉树——二叉树之数组存储

题目描述

二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。

从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。

结点存储的数据均为非负整数

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数

连续输入t行

输出

每行输出一个示例的先序遍历结果，每个结点之间用空格隔开

题解

def read_int_list():
    s = list(map(int, input().split()))
    return s[0], s[1:]
class BiTreeNode():
    def __init__(self, data, parent=None, lchild=None, rchild=None):
        self.data = data
        self.parent = parent
        self.lchild = lchild
        self.rchild = rchild

class BiTree():
# 用一个以数组方式储存的二叉树，建立一个二叉树
    def createBiTree(self, TreeArray: list):
        # 用层次遍历的顺序建立完全二叉树，空节点用'0'表示
        if len(TreeArray) == 0:
            return None
        root = BiTreeNode(TreeArray[0])
        queue = []
        queue.append(root)
        TreeArray.pop(0)
        while len(queue) != 0:
            node = queue.pop(0)
            if len(TreeArray) != 0:
                node.lchild = BiTreeNode(TreeArray[0])
                TreeArray.pop(0)
                node.lchild.parent = node
                queue.append(node.lchild)
            if len(TreeArray) != 0:
                node.rchild = BiTreeNode(TreeArray[0])
                TreeArray.pop(0)
                node.rchild.parent = node
                queue.append(node.rchild)
        return root

    def preOrder(self, root):
        if root == None:
            return
        if root.data != 0:
            print(root.data, end=' ')
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        index, TreeArray = read_int_list()
        tree = BiTree()
        root = tree.createBiTree(TreeArray)
        tree.preOrder(root)
        print()
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