基于python实现二叉搜索树和Huffman树的原理
时间: 2023-07-24 07:26:29 浏览: 53
二叉搜索树(Binary Search Tree)是一种特殊的二叉树,它满足以下两个条件:
1. 左子树上所有节点的值均小于根节点的值。
2. 右子树上所有节点的值均大于根节点的值。
这种特殊的结构使得我们可以非常高效地进行查找、插入和删除操作。
在 Python 中,我们可以使用类来实现二叉搜索树。一个二叉搜索树的节点一般包含一个值、指向左子树的指针和指向右子树的指针。我们可以定义一个 `Node` 类来表示一个节点,再定义一个 `BinarySearchTree` 类来表示整个树。具体实现可以参考以下代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
node = Node(value)
if self.root is None:
self.root = node
else:
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = node
return
else:
current = current.left
else:
if current.right is None:
current.right = node
return
else:
current = current.right
def search(self, value):
current = self.root
while current is not None:
if current.value == value:
return True
elif value < current.value:
current = current.left
else:
current = current.right
return False
def delete(self, value):
parent = None
current = self.root
while current is not None:
if current.value == value:
# 如果当前节点没有左右子树
if current.left is None and current.right is None:
if parent is None:
self.root = None
elif parent.left == current:
parent.left = None
else:
parent.right = None
# 如果当前节点只有左子树或只有右子树
elif current.left is None:
if parent is None:
self.root = current.right
elif parent.left == current:
parent.left = current.right
else:
parent.right = current.right
elif current.right is None:
if parent is None:
self.root = current.left
elif parent.left == current:
parent.left = current.left
else:
parent.right = current.left
# 如果当前节点既有左子树又有右子树
else:
successor = current.right
successor_parent = current
while successor.left is not None:
successor_parent = successor
successor = successor.left
current.value = successor.value
if successor_parent.left == successor:
successor_parent.left = successor.right
else:
successor_parent.right = successor.right
return
elif value < current.value:
parent = current
current = current.left
else:
parent = current
current = current.right
```
Huffman 树(Huffman Tree)是一种用于数据编码的树形结构。它可以根据数据的出现频率构建一个最优编码方案,从而实现数据的高效压缩。在 Huffman 树中,出现频率较高的数据节点会被放到树的上层,出现频率较低的数据节点则会被放到树的下层。
在 Python 中,我们可以使用类来实现 Huffman 树。一个 Huffman 树的节点一般包含一个权值、指向左子树的指针和指向右子树的指针。我们可以定义一个 `Node` 类来表示一个节点,再定义一个 `HuffmanTree` 类来表示整个树。具体实现可以参考以下代码:
```python
class Node:
def __init__(self, value, freq):
self.value = value
self.freq = freq
self.left = None
self.right = None
class HuffmanTree:
def __init__(self, data):
self.root = None
self.leaves = []
self.build_tree(data)
def build_tree(self, data):
freq = {}
for c in data:
freq[c] = freq.get(c, 0) + 1
nodes = [Node(c, f) for c, f in freq.items()]
self.leaves = nodes[:]
while len(nodes) > 1:
nodes.sort(key=lambda n: n.freq)
left = nodes.pop(0)
right = nodes.pop(0)
parent = Node(None, left.freq + right.freq)
parent.left = left
parent.right = right
nodes.append(parent)
self.root = nodes[0]
def encode(self, data):
code = {}
for leaf in self.leaves:
path = []
current = leaf
while current is not self.root:
parent = self._get_parent(current)
if current is parent.left:
path.append('0')
else:
path.append('1')
current = parent
path.reverse()
code[leaf.value] = ''.join(path)
encoded = ''.join([code[c] for c in data])
return encoded, code
def decode(self, encoded, code):
data = []
current = self.root
for bit in encoded:
if bit == '0':
current = current.left
else:
current = current.right
if current.value is not None:
data.append(current.value)
current = self.root
decoded = ''.join(data)
return decoded
def _get_parent(self, node):
if node is self.root:
return None
current = self.root
while True:
if current.left is node or current.right is node:
return current
elif node.freq < current.freq:
current = current.left
else:
current = current.right
```
以上就是基于 Python 实现二叉搜索树和 Huffman 树的原理及代码实现。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)