使用二叉树之二叉排序树

发布于 | 分类： .
字数统计

本文参考链接：https://github.com/qiwsir/algorithm/blob/master/binary_tree.md

这里介绍一下一种特殊的二叉树，从定义，构建以及基本的操作来介绍。

二叉排序树（Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

  1. 如果它的左子树不空，那么左子树上的所有节点的值都小于它的根节点的值；
  2. 如果它的右子树不空，那么右子树上的所有节点的值都大于它的根节点的值；
  3. 它的左右子树也分别是二叉排序树。
  4. 没有键值相等的结点。

二叉排序树又叫做二叉查找树，它的查找过程和次优二叉树类似。也就是当二叉排序树不为空的时候，把给定的关键词先和根节点的值作比较，如果小于根节点的值，就再和左孩子的值进行比较；反之，则和右孩子的值进行比较，这样循环往复，直到查找成功。

接下来先构建一棵二叉排序树，有图作参考（图片来自网络）：

构建二叉排序树

python实现这个算法。

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
# coding:utf-8
"关于二叉排序树"
class Node:
    """构造节点类"""
    def __init__(self,data):
        """节点结构"""
        self.lchild = None
        self.rchild = None
        self.data = data
    
    # 创建一个只有根节点的树，然后根据这个根节点进行插入，完成一棵完整的二叉排序树,这里默认从列表的第一个元素开始构建
    def insertnode(self,data):
        """插入节点的数据"""
            # 如果要插入的节点的值小于根节点的值
        if data < self.data:
            if self.lchild is None:
                self.lchild = Node(data)
            else:
                self.lchild.insertnode(data)
        elif data > self.data:
            if self.rchild is None:
                self.rchild = Node(data)
            else:
                self.rchild.insertnode(data)
    # 接下来就是遍历了，二叉排序树也是二叉树，所以二叉树的遍历方式我们都能用在二叉排序树上，这里采用中序遍历的方法，因为中序遍历得到的序列是一个有序的列表。
    def print_tree(self):
        """按照顺序来打印"""
        orderlist = []
        if self.lchild:
            self.lchild.print_tree()
        print(self.data)
        if self.rchild:
            self.rchild.print_tree()
    # 得到一个输入的列表
while True:
    jiedianlist = []
    mystr = input("please input the elements that could be sorted. The elements should not be repetitive, and divided them with space:")
    print(mystr)
    for i in mystr.split():
        jiedianlist.append(int(i))
    print(jiedianlist)
    if len(jiedianlist) == 0:
        print("Error, empty list. Try again!")
        continue
    elif len(jiedianlist) == len(set(jiedianlist)):
    	print("debug!")
    	break
    else:
        print("Sorry, there are some elements repetitive in the list, please input again!")
        continue
root = Node(jiedianlist.pop(0))
print(root.data)
if len(jiedianlist):
    for i in range(0,len(jiedianlist)):
        root.insertnode(jiedianlist.pop(0))
    print("insert ok!")
root.print_tree()

上面代码亲测可用，记下遇到坑。首先就是接收键盘输入部分的代码应该放在外面，class Node中就是有关node的所有操作，为什么要抽象出类，就是尽可能的把可能重复的内容集中到一起。‘

下一个坑就是缩进格式的问题，python中的格式是一个很重要的点，缩进格式可能会导致一些灾难。

还有一个就是range()函数，range()函数的前两个参数是起始位置和最终位置，比如在这个例子中，如果是

1
2
3
for i in range(0,len(jiedianlist)-1):
    root.insertnode(jiedianlist.pop(0))
print("insert ok!")

这样的结果就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
peter@peter-VirtualBox:~/DataStructure$ python3 binsorttree.py
please input the elements that could be sorted. The elements should not be repetitive, and divided them with space:2 1 4 9 0 5 3 8
2 1 4 9 0 5 3 8
[2, 1, 4, 9, 0, 5, 3, 8]
debug!
2
insert ok!
0
1
2
3
4
5
9

结果是丢掉了8，所以修改之后，结果就正确了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
peter@peter-VirtualBox:~/DataStructure$ python3 binsorttree.py
please input the elements that could be sorted. The elements should not be repetitive, and divided them with space:2 1 4 9 0 5 3 8
2 1 4 9 0 5 3 8
[2, 1, 4, 9, 0, 5, 3, 8]
debug!
2
insert ok!
0
1
2
3
4
5
8
9

接下来继续研究怎样去删除二叉排序树的节点，这是一个比较复杂的工作，先看代码：

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
# coding:utf-8
"接下来实现节点的删除"
class Node:
    """构造节点类"""
    def __init__(self,data):
        """节点结构"""
        self.lchild = None
        self.rchild = None
        self.data = data
    
    # 创建一个只有根节点的树，然后根据这个根节点进行插入，完成一棵完整的二叉排序树,这里默认从列表的第一个元素开始构建
    def insertnode(self,data):
        """插入节点的数据"""
            # 如果要插入的节点的值小于根节点的值
        if data < self.data:
            if self.lchild is None:
                self.lchild = Node(data)
            else:
                self.lchild.insertnode(data)
        elif data > self.data:
            if self.rchild is None:
                self.rchild = Node(data)
            else:
                self.rchild.insertnode(data)
    # 接下来就是遍历了，二叉排序树也是二叉树，所以二叉树的遍历方式我们都能用在二叉排序树上，这里采用中序遍历的方法，因为中序遍历得到的序列是一个有序的列表。
    def lookup(self,data,parent = None):
        """遍历二叉树"""
        if data < self.data:
            if self.lchild is None:
                print("Error, can not find it!")
                return None,None
            return self.lchild.lookup(data,self)
        elif data > self.data:
            if self.rchild is None:
                print("Error, can not find it!")
                return None,None
            return self.rchild.lookup(data,self)
        else:
            return self,parent
            print("OK, find it !")
    # 接下来是将二叉树中的节点的值打印出来的函数
    def print_tree(self):
        """按照顺序来打印"""
        orderlist = []
        if self.lchild:
            self.lchild.print_tree()
        print(self.data)
        if self.rchild:
            self.rchild.print_tree()
    # 删除节点的函数，这里分三种情况
    def deletenode(self,data):
        """删除节点"""
        node,parent = self.lookup(data)
        if node is not None:
            # 先判断子节点数目
            children_count = node.children_count()
            if node.children_count == 0:
                # 如果这个节点下面没有子节点，就直接将该节点删除
                if parent.lchild is node:
                    parent.lchild = None
                else:
                    parent.rchild = None
                del node
            elif children_count == 1:
                # 如果有一个子节点，则让子节点上移替换该节点(该节点消失)
                if node.lchild:
                    n = node.lchild
                else:
                    n = node.rchild
                if parent:
                    if parent.lchild is node:
                        parent.lchild = n
                    else:
                        parent.rchild = n
                del node
            else:
                # 如果要删除的节点的左右子节点都存在，那需要判断节点下面的所有的叶子
                parent = node
                successor = node.rchild
                while successor.lchild:
                    parent = successor
                    successor = successor.lchild
                node.data = successor.data
                if parent.lchild == successor:
                    parent.lchild = successor.rchild
                else:
                    parent.rchild = successor.rchild
    # 上面用到了统计的函数，这里补充
    def children_count(self):
        """统计子节点的个数"""
        cnt = 0
        if self.lchild:
            cnt += 1
        if self.rchild:
            cnt += 1
        return cnt            
# 测试函数。这里从键盘输入中获得一个整型数的列表，测试二叉排序树的构建，查找和删除等功能。
while True:
    jiedianlist = []
    mystr = input("please input the elements that could be sorted. The elements should not be repetitive, and divided them with space:")
    print(mystr)
    for i in mystr.split():
        jiedianlist.append(int(i))
    print(jiedianlist)
    if len(jiedianlist) == 0:
        print("Error, empty list. Try again!")
        continue
    elif len(jiedianlist) == len(set(jiedianlist)):
    	print("debug!")
    	break
    else:
        print("Sorry, there are some elements repetitive in the list, please input again!")
        continue
root = Node(jiedianlist.pop(0))
print(root.data)
if len(jiedianlist):
    for i in range(0,len(jiedianlist)):
        root.insertnode(jiedianlist.pop(0))
    print("insert ok!")
root.print_tree()
# 测试查找和删除
a = int(input("Please tell me the elements you want to find:"))
print(a)
root.lookup(a)
#root.deletenode(a)

这样写的结果就是可以检测到要删除选项的输入，但是不能成功的调用lookup()函数，这和lookup()函数有关系，明天再继续的研究下。