大飞

关注TA

挑战一切!

  • 世界的顶端
  • 混口饭吃

可爱的留言者

Python 二叉树的查找算法和节点插入

2018年12月05 18:11 417 0

  二叉树的查找,需要先排序好二叉树,最终结果如图,排序算法参照上篇:https://www.link-nemo.com/u/10025/post/66629

  实例GitHub地址:https://github.com/tzz2015/DTF/tree/develop

WX20181203-210934@2x.png一.查找算法,如果要查找的数据小于当前节点,则向二叉树的左支查询,否者向右查询。代码如下:

# 搜索
def do_search(self, node, parent, data):
# 如果节点为空 搜索不到
if node is None:
return False, node, parent
# 如果节点数据跟搜索的数据相同 则返回到相应的数据
if node.data == data:
return True, node, parent
# 如果搜索的数据大于节点数据 则向右查询 否则向左查询
if data > node.data:
return self.do_search(node.right, node, data)
else:
return self.do_search(node.left, node, data)

二.插入算法,如果插入的数据大于当前节点,则向二叉树的右侧插入,否者向左侧插入。代码如下:

# 插入数据
def add_node(self, data):
flag, node, parent = self.do_search(self.root, self.root, data)
# 如果数据不存在 则需要进行插入操作
if not flag:
new_node = Node(data)
# 如果当前数据大于最后一个节点的数据 则盖数据为父节点的右节点
if data > parent.data:
parent.right = new_node
else:
parent.left = new_node


C686C0AF-5F73-4814-AA96-1DB1C2DC711E.png

所有代码:

import json

"""
1.二叉树排序
2.二叉树查找
3.二叉树插入
4.二叉树删除
"""


class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None

# 插入左节点
def insert_left(self, value):
self.left = Node(value)
return self.left

# 插入右节点
def insert_right(self, value):
self.right = Node(value)
return self.right

# 输出节点数据
def show(self):
print(self.data)


class BST:
def __init__(self, data_list):
# 设置根节点
self.root = Node(data_list[0])
# 生成二叉树
for data in data_list[1:]:
self.insert(self.root, data)

# 对二叉树进行排序
def insert(self, node, value):
# 插入右节点
if value > node.data:
if node.right:
self.insert(node.right, value)
else:
node.insert_right(value)
# 插入左节点
else:
if node.left:
self.insert(node.left, value)
else:
node.insert_left(value)

# 中序排序 从小到大 左根右
def mid_order(self, node):
if node.data:
# 左
if node.left:
self.mid_order(node.left)
# 根
node.show()
# 右
if node.right:
self.mid_order(node.right)

# 遍历从大到小排序 右根左
def big_to_small_order(self, node):
# 右
if node.right:
self.big_to_small_order(node.right)
# 根
node.show()
# 左
if node.left:
self.big_to_small_order(node.left)

# 搜索
def do_search(self, node, parent, data):
# 如果节点为空 搜索不到
if node is None:
return False, node, parent
# 如果节点数据跟搜索的数据相同 则返回到相应的数据
if node.data == data:
return True, node, parent
# 如果搜索的数据大于节点数据 则向右查询 否则向左查询
if data > node.data:
return self.do_search(node.right, node, data)
else:
return self.do_search(node.left, node, data)

# 插入数据
def add_node(self, data):
flag, node, parent = self.do_search(self.root, self.root, data)
# 如果数据不存在 则需要进行插入操作
if not flag:
new_node = Node(data)
# 如果当前数据大于最后一个节点的数据 则盖数据为父节点的右节点
if data > parent.data:
parent.right = new_node
else:
parent.left = new_node


if __name__ == '__main__':
L = [4, 2, 9, 1, 7, 6, 5, 3, 8]
bst = BST(L)
# 输出排序后的二叉树json
print(json.dumps(bst, default=lambda obj: obj.__dict__))
print('--------------小到大----------------')
# 输出中序排序 从小到大
bst.mid_order(bst.root)
print('--------------大到小----------------')
# 输出中序排序 从大到小
bst.big_to_small_order(bst.root)
print('--------------查询----------------')
so, node, parent = bst.do_search(bst.root, None, 2)
print('查询到结果:%s 当前节点:%s 父节点:%s' % (so, node.data, parent.data))
print('--------------插入数据----------------')
bst.add_node(11)
print(json.dumps(bst, default=lambda obj: obj.__dict__))


"""
1.先序遍历:先访问跟节点 后左节点 最后右节点
2.中序遍历:先访问左节点 后跟节点 最后右节点
3.后序遍历:先访问左节点 后右节点 最后跟节点
"""
点赞(0)
本文标签算法 python

上一个文章:Python 工厂模式

下一个文章:Python 二叉树排序

点了个评