手机微网站,东莞设计网站建设,开彩票网站做私庄,大学生网站设计作业动画树的介绍
树不同于链表或哈希表#xff0c;是一种非线性数据结构#xff0c;树分为二叉树、二叉搜索树、B树、B树、红黑树等等。
树是一种数据结构#xff0c;它是由n个有限节点组成的一个具有层次关系的集合。用图片来表示的话#xff0c;可以看到它很像一棵倒挂着的树。…树的介绍
树不同于链表或哈希表是一种非线性数据结构树分为二叉树、二叉搜索树、B树、B树、红黑树等等。
树是一种数据结构它是由n个有限节点组成的一个具有层次关系的集合。用图片来表示的话可以看到它很像一棵倒挂着的树。因此我们将这类数据结构统称为树树根在上面树叶在下面。一般的树具有以下特点
每个节点有0个或者多个子节点没有父节点的节点被称为根节点每个非根节点有且只有一个父节点每个子结点都可以分为多个不相交的子树
二叉树的定义是每个节点最多有两个子节点。即每个节点只能有以下四种情况
左子树和右子树均为空只存在左子树只存在右子树左子树和右子树均存在
二叉搜索树
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树列举几种Python中几种常见的实现方式
1.使用类和递归函数实现
通过定义一个节点类包含节点值、左右子节点等属性然后通过递归函数实现插入、查找、删除等操作。代码示例如下
class Node:def __init__(self, data):self.data dataself.left Noneself.right None
class BST:def __init__(self):self.root None
def insert(self, value):if self.root is None:self.root Node(value)else:self._insert(value, self.root)
def _insert(self, value, node):if value node.data:if node.left is None:node.left Node(value)else:self._insert(value, node.left)elif value node.data:if node.right is None:node.right Node(value)else:self._insert(value, node.right)
def search(self, value):if self.root is None:return Falseelse:return self._search(value, self.root)
def _search(self, value, node):if node is None:return Falseelif node.data value:return Trueelif value node.data:return self._search(value, node.left)else:return self._search(value, node.right)
def delete(self, value):if self.root is None:return Falseelse:self.root self._delete(value, self.root)
def _delete(self, value, node):if node is None:return nodeelif value node.data:node.left self._delete(value, node.left)elif value node.data:node.right self._delete(value, node.right)else:if node.left is None and node.right is None:del nodereturn Noneelif node.left is None:temp node.rightdel nodereturn tempelif node.right is None:temp node.leftdel nodereturn tempelse:temp self._find_min(node.right)node.data temp.datanode.right self._delete(temp.data, node.right)return node
def _find_min(self, node):while node.left is not None:node node.leftreturn node
2.使用列表实现
通过使用一个列表来存储二叉搜索树的元素然后通过列表中元素的位置关系来实现插入、查找、删除等操作。代码示例如下
class BST:def __init__(self):self.values []
def insert(self, value):if len(self.values) 0:self.values.append(value)else:self._insert(value, 0)
def _insert(self, value, index):if value self.values[index]:left_child_index 2 * index 1if left_child_index len(self.values):self.values.extend([None] * (left_child_index - len(self.values) 1))if self.values[left_child_index] is None:self.values[left_child_index] valueelse:self._insert(value, left_child_index)else:right_child_index 2 * index 2if right_child_index len(self.values):self.values.extend([None] * (right_child_index - len(self.values) 1))if self.values[right_child_index] is None:self.values[right_child_index] valueelse:self._insert(value, right_child_index)
def search(self, value):if value in self.values:return Trueelse:return False
def delete(self, value):if value not in self.values:return Falseelse:index self.values.index(value)self._delete(index)return True
def _delete(self, index):left_child_index 2 * index 1right_child_index 2 * index 2if left_child_index len(self.values) and self.values[left_child_index] is not None:self._delete(left_child_index)if right_child_index len(self.values) and self.values[right_child_index] is not None:self
3.使用字典实现
其中字典的键表示节点值字典的值是一个包含左右子节点的字典。代码示例如下
def insert(tree, value):if not tree:return {value: {}}elif value list(tree.keys())[0]:tree[list(tree.keys())[0]] insert(tree[list(tree.keys())[0]], value)else:tree[list(tree.keys())[0]][value] {}return tree
def search(tree, value):if not tree:return Falseelif list(tree.keys())[0] value:return Trueelif value list(tree.keys())[0]:return search(tree[list(tree.keys())[0]], value)else:return search(tree[list(tree.keys())[0]].get(value), value)
def delete(tree, value):if not search(tree, value):return Falseelse:if list(tree.keys())[0] value:if not tree[list(tree.keys())[0]]:del tree[list(tree.keys())[0]]elif len(tree[list(tree.keys())[0]]) 1:tree[list(tree.keys())[0]] list(tree[list(tree.keys())[0]].values())[0]else:min_key min(list(tree[list(tree.keys())[0]1].keys()))tree[min_key] tree[list(tree.keys())[0]1][min_key]tree[min_key][list(tree.keys())[0]] tree[list(tree.keys())[0]]del tree[list(tree.keys())[0]]elif value list(tree.keys())[0]:tree[list(tree.keys())[0]] delete(tree[list(tree.keys())[0]], value)else:tree[list(tree.keys())[0]][value] delete(tree[list(tree.keys())[0]].get(value), value)return tree
由于字典是无序的因此该实现方式可能会导致二叉搜索树不平衡影响插入、查找和删除操作的效率。
4.使用堆栈实现
使用堆栈Stack可以实现一种简单的二叉搜索树可以通过迭代方式实现插入、查找、删除等操作。具体实现过程如下
定义一个节点类包含节点值、左右子节点等属性。定义一个堆栈初始时将根节点入栈。当栈不为空时取出栈顶元素并对其进行操作如果要插入的值小于当前节点值则将要插入的值作为左子节点插入并将左子节点入栈如果要插入的值大于当前节点值则将要插入的值作为右子节点插入并将右子节点入栈如果要查找或删除的值等于当前节点值则返回或删除该节点。操作完成后继续从堆栈中取出下一个节点进行操作直到堆栈为空。
需要注意的是在这种实现方式中由于使用了堆栈来存储遍历树的过程因此可能会导致内存占用较高。另外由于堆栈的特性这种实现方式只能支持深度优先遍历Depth-First SearchDFS不能支持广度优先遍历Breadth-First SearchBFS。
以下是伪代码示例
class Node:def __init__(self, data):self.data dataself.left Noneself.right None
def insert(root, value):if not root:return Node(value)stack [root]while stack:node stack.pop()if value node.data:if node.left is None:node.left Node(value)breakelse:stack.append(node.left)elif value node.data:if node.right is None:node.right Node(value)breakelse:stack.append(node.right)
def search(root, value):stack [root]while stack:node stack.pop()if node.data value:return Trueelif value node.data and node.left:stack.append(node.left)elif value node.data and node.right:stack.append(node.right)return False
def delete(root, value):if root is None:return Noneif value root.data:root.left delete(root.left, value)elif value root.data:root.right delete(root.right, value)else:if root.left is None:temp root.rightdel rootreturn tempelif root.right is None:temp root.leftdel rootreturn tempelse:temp root.rightwhile temp.left is not None:temp temp.leftroot.data temp.dataroot.right delete(root.right, temp.data)return root
以上是四种在Python中实现二叉搜索树的方法在具体使用过程中还是需要合理选择尽量以运行速度快、内存占用少为出发点最后觉得有帮助的话请多多关注和赞同
