电子商务网站主要功能,电销crm客户管理系统,杭州软件开发的公司,国内做网站的龙头企业数据结构之二叉查找树的代码实现
定义
二叉查找树#xff08;Binary Search Tree#xff0c;BST#xff09;#xff0c;是一种内存中特殊的树类型的存储结构#xff0c;它允许对存储在其结点的数据进行增删改查#xff0c;或者用作动态的数据集合#xff0c;或是通过k…数据结构之二叉查找树的代码实现
定义
二叉查找树Binary Search TreeBST是一种内存中特殊的树类型的存储结构它允许对存储在其结点的数据进行增删改查或者用作动态的数据集合或是通过key查找对应value的查找表
创建结点
设计可以使用顺序表或链表实现二叉树这里使用链表实现在学习堆时再使用顺序表实现
使用链表结点设计
class Node:def __init__(self, keyNone, valueNone):self.key keyself.value valueself.left Noneself.right Noneleft和right分别代表左右子结点key是可比较的用于进行顺序匹配value储存值
实现的功能
构造方法__init__()root为根结点默认为Nonelen为树的大小
size()获取BST中元素个数put(_key, _value)向树中添加键值对元素元素按key排序返回添加元素后的新树get(_key)通过键获取树中对应元素的值delete(_key)通过键删除树中对应的元素min_key()获取最小的keymax_key()获取最大的key
Python代码实现
import operatorclass Node:def __init__(self, keyNone, valueNone):self.key keyself.value valueself.left Noneself.right Noneclass BinarySearchTree:def __init__(self):self.root Noneself.len 0def size(self):return self.lendef put(self, _key, _value):Put an element into this tree and generate a new BSTdef put_into(node, _key, _value):Adjust position of new inserted nodeby BST character:left root rightif not node:self.len 1return Node(_key, _value)if operator.lt(_key, node.key):node.left put_into(node.left, _key, _value)elif operator.gt(_key, node.key):node.right put_into(node.right, _key, _value)elif operator.eq(_key, node.key):node.value _valuereturn nodeself.root put_into(self.root, _key, _value)return self.rootdef get(self, _key):Get a value responding to the given _key from this treedef get_value_by_key(node, _key):if not node:returnif operator.lt(_key, node.key):return get_value_by_key(node.left, _key)elif operator.gt(_key, node.key):return get_value_by_key(node.right, _key)else:return node.valuereturn get_value_by_key(self.root, _key)def delete(self, _key):Delete a node responding to the giving key(_key)def delete_value_by_key(node, _key):if not node:returnif operator.lt(_key, node.key):node.left delete_value_by_key(node.left, _key)elif operator.gt(_key, node.key):node.right delete_value_by_key(node.right, _key)else:self.len - 1to_delete_node nodeif node self.root:self.root Nonereturn# node Noneif not to_delete_node.left:return to_delete_node.rightelif not to_delete_node.right:return to_delete_node.leftelse:min_right_tree to_delete_node.rightpre min_right_treewhile min_right_tree.left:pre min_right_treemin_right_tree min_right_tree.leftpre.left Nonemin_right_tree.left to_delete_node.leftmin_right_tree.right to_delete_node.rightreturn min_right_treereturn delete_value_by_key(self.root, _key)def min_key(self):Find the minimum keydef min_node(node):while node.left:node node.leftreturn nodereturn min_node(self.root).keydef max_key(self):Find the maximum keydef max_node(node):while node.right:node node.rightreturn nodereturn max_node(self.root).keydef max_depth(self):Calculate the max depth of this treedef max_depth(node):max_left, max_right 0, 0if not node:return 0if node.left:max_left max_depth(node.left)if node.right:max_right max_depth(node.right)return max(max_left, max_right) 1return max_depth(self.root)主要代码解释
put()插入元素使用递归按照从上到下从左到右的顺序依次和插入的元素比较
1.如果当前树中没有任何一个结点则直接把新结点当做根结点使用并返回2.如果当前树不为空, 则从根结点开始与传入的元素的key进行比较 2.1如果新结点的key小于当前结点的key ,则继续找当前结点的左子结点; 2.2如果新结点的key大于当前结点的key ,则继续找当前结点的右子结点; 2.3如果新结点的key等于当前结点的key ,则树中已经存在这样的结点,替换该结点的value值即可。
delete()删除元素跟插入元素类似也是使用递归寻找的顺序按照从上到下从左到右的顺序依次和插入的元素比较如果找到key相等的元素则做删除动作
如果找到key相等的元素则只需要往这个结点的右子树的左边最深处寻找根据排序的规律找到的元素与key相等的元素交换位置即可
代码测试
if __name__ __main__:BST BinarySearchTree()BST.put(e, 5)BST.put(b, 2)BST.put(g, 7)BST.put(a, 1)BST.put(d, 4)BST.put(f, 6)BST.put(h, 8)BST.put(c, 3)print(fThe size of this binary tree now is {BST.size()}\n)key aprint(f\nGet element by key[{key}]: {BST.get(key)})key bBST.delete(key)print(fAfter deleting an node ({key}), the size of this tree: {BST.size()})print(fGet the deleted value (key[{key}]), it should be none: {BST.get(key)})print(fGet the value (key[{a}]), it should be {1}: {BST.get(a)})测试结果
The size of this binary tree now is 8Get element by key[a]: 1
After deleting an node (b), the size of this tree: 7
Get the deleted value (key[b]), it should be none: None
Get the value (key[a]), it should be 1: 1Process finished with exit code 0
