简介
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵
空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均
小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点
的值； 它的左、右子树也分别为二叉排序树。
原理
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。
中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，
构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，
在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。
搜索,插入,删除的复杂度等于树高，O(log(n)).
例子
1
2
3
4
5
6
7
|
16
/ \
9 18
/ \ / \
6 12 17 25
/ /
1 10
|
图上的就是一个二叉搜索树，
接下来的代码都会用这颗树的结点作例子
树的节点
二叉树的节点可用以下代码表示：
1
2
3
4
5
|
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
|
二叉搜索树的插入
上述例子用一个列表存起来：
tree_nodes = [16,9,6,12,1,10,18,17,25]
打乱顺序:
1
2
|
import random
random.shuffle(tree_nodes) # 输出: [10, 1, 12, 16, 9, 18, 25, 6, 17]
|
树的插入代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def insert(root,val):
if not root:
return TreeNode(val)
if val <= root.val:
if not root.left:
root.left = TreeNode(val)
else:
insert(root.left,val)
elif val > root.val:
if not root.right:
root.right = TreeNode(val)
else:
insert(root.right,val)
return root
|
插入操作为:
1
2
3
|
root = None
for i in tree_nodes:
root = insert(root, i)
|
其中root为根节点， 最终得到的结果为:
1
2
3
4
5
6
7
8
9
|
10
/ \
9 12
/ \
6 16
\
18
/ \
17 25
|
左节点始终小于右节点， 确认过眼神， 是一颗二叉搜索树。
二叉搜索树的遍历
遍历就是跟普通树的遍历一样
前序遍历: 根 -> 左 -> 右
中序遍历: 左 -> 根 -> 右
后序遍历: 左 -> 右 -> 根
前序遍历
1
2
3
4
5
6
7
8
|
result = []
def pre_order_traverse(root):
if not root:
return
result.append(root.val)
pre_order_traverse(root.left)
pre_order_traverse(root.right)
|
中序遍历
1
2
3
4
5
6
7
8
9
|
result = []
def in_order_traverse(root):
if not root:
return
in_order_traverse(root.left)
if root:
result.append(root.val)
in_order_traverse(root.right)
|
后序遍历
1
2
3
4
5
6
7
8
9
|
result = []
def post_order_traverse(root):
if not root:
return
post_order_traverse(root.left)
post_order_traverse(root.right)
if root:
result.append(root.val)
|
二叉搜索树的查询
查询有迭代和递归两种:
迭代查询
1
2
3
4
5
6
7
8
9
|
def search(root, val):
temp = root
while temp:
if val < temp.val:
temp = temp.left
elif val > temp.val:
temp = temp.right
else:
return temp
|
递归查询
1
2
3
4
5
6
7
8
9
|
def search(root, val):
if not root:
return
if val < root.val:
return search(root.left,val)
elif val > root.val:
return search(root.right,val)
else:
return root
|
二叉搜索树的删除
待续