python 树与二叉树的实现

import operatorclass BinaryTree:
"""
A recursive implementation of Binary Tree
Using links and Nodes approach. Modified to allow for trees to be constructed from other trees
rather than always creating a new tree in the insert_feft or insert_right
""" def __init__(self, key):
"""Create new tree"""
self._key = key
self._child_left = None
self._child_right = None def get_root_val(self):
"""Get root key value"""
return self._key def set_root_val(self, key):
"""Set root key value"""
self._key = key root = property(get_root_val, set_root_val) def get_child_left(self):
"""Get left child"""
return self._child_left def set_child_left(self, node):
"""Set left child"""
self._child_left = node child_left = property(get_child_left, set_child_left) def get_child_right(self):
"""Get right child"""
return self._child_right def set_child_right(self, node):
"""Set right child"""
self._child_right = node child_right = property(get_child_right, set_child_right) def is_leaf(self):
"""Check if a node is leaf"""
return (not self._child_left) and (not self._child_right) def insert_left(self, new_node):
"""Insert left subtree"""
if isinstance(new_node, BinaryTree):
new_subtree = new_node
else:
new_subtree = BinaryTree(new_node) if self._child_left:
new_subtree.set_child_left(self._child_left) self._child_left = new_subtree def insert_right(self, new_node):
"""Insert right subtree"""
if isinstance(new_node, BinaryTree):
new_subtree = new_node
else:
new_subtree = BinaryTree(new_node) if self._child_right:
new_subtree.set_child_right(self._child_right)
self._child_right = new_subtree def preorder(self):
"""Pre-order tree traversal"""
print(self._key, end=" ")
if self._child_left:
self._child_left.preorder()
if self._child_right:
self._child_right.preorder() def inorder(self):
"""In-order tree traversal"""
if self._child_left:
self._child_left.inorder()
print(self._key, end=" ")
if self._child_right:
self._child_right.inorder() def postorder(self):
"""Post-order tree traversal"""
if self._child_left:
self._child_left.postorder()
if self._child_right:
self._child_right.postorder()
print(self._key, end=" ") def print_exp(self):
"""Print an expression"""
if self._child_left:
print("(", end=" ")
self._child_left.print_exp()
print(self._key, end=" ")
if self._child_right:
self._child_right.print_exp()
print(")", end=" ") def postorder_eval(self):
"""Postorder evaluation"""
operations = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}
result_1 = None
result_2 = None
if self._child_left:
result_1 = self._child_left.postorder_eval()
if self._child_right:
result_2 = self._child_right.postorder_eval()
if result_1 and result_2:
return operations[self._key](result_1, result_2)
return self._key def height(self):
"""Height of a tree"""
if not self._key:
return -1
if self._child_left:
height_left = self._child_left.height()
else:
height_left = -1 if self._child_right:
height_right = self._child_right.height()
else:
height_right = -1 return 1 + max(height_left, height_right) def __len__(self):
"""Size of a tree"""
return self.size() def size(self):
"""Count nodes in a tree"""
if not self._key:
return 0
if self._child_left:
children_left = self._child_left.size()
else:
children_left = 0 if self._child_right:
children_right = self._child_right.size()
else:
children_right = 0 return 1 + children_left + children_right

class BinaryTreeNode:
"""Binary Tree Node class""" def __init__(self, key, value, left=None, right=None, parent=None):
"""Create new Tree Node"""
self._key = key
self._value = value
self._child_left = left
self._child_right = right
self._parent = parent def get_child_left(self):
"""Return the node's left child"""
return self._child_left def set_child_left(self, node):
"""Assign the node's left child"""
self._child_left = node child_left = property(get_child_left, set_child_left) def get_child_right(self):
"""Return the node's right child"""
return self._child_right def set_child_right(self, node):
"""Assign the node's right child"""
self._child_right = node child_right = property(get_child_right, set_child_right) def get_parent(self):
"""Return the node's parent"""
return self._parent def set_parent(self, node):
"""Assign the node's parent"""
self._parent = node parent = property(get_parent, set_parent) def is_child_left(self):
"""Check if the node is a left child"""
return self._parent and self._parent.child_left == self def is_child_right(self):
"""Check if the node is a right child"""
return self._parent and self._parent.child_right == self def is_root(self):
"""Check if the node is a tree root"""
return not self._parent def is_leaf(self):
"""Check if the node is a leaf"""
return not (self._child_right or self._child_left) def has_a_child(self):
"""Check if the node has any child"""
return self._child_right or self._child_left def has_children(self):
"""Check if the node has both children"""
return self._child_right and self._child_left def get_key(self):
"""Get node key"""
return self._key def set_key(self, key):
"""Set node key"""
self._key = key key = property(get_key, set_key) def get_value(self):
"""Get node value"""
return self._value def set_value(self, value):
"""Set node value"""
self._value = value value = property(get_value, set_value) def replace_payload(self, key, value, left, right):
"""Change node payload"""
self._key = key
self._value = value
self._child_left = left
self._child_right = right
if self.child_left:
self._child_left.parent = self
if self.child_right:
self._child_right.parent = self def find_successor(self):
"""Find the node's successor"""
successor = None
if self._child_right:
successor = self._child_right.find_min()
else:
if self._parent:
if self.is_child_left():
successor = self._parent
else:
self._parent.child_right = None
successor = self._parent.find_successor()
self._parent.child_right = self
return successor def find_min(self):
"""Find the smallest node in the right subtree"""
current = self
while current.child_left:
current = current.child_left
return current def splice_out(self):
"""Splice out"""
if self.is_leaf():
if self.is_child_left():
self._parent.child_left = None
else:
self._parent.child_right = None
elif self.has_a_child():
if self.child_left:
if self.is_child_left():
self._parent.child_left = self._child_left
else:
self._parent.child_right = self._child_left
self._child_left.parent = self._parent
else:
if self.is_child_left():
self._parent.child_left = self._child_right
else:
self._parent.child_right = self._child_right
self._child_right.parent = self._parent def __iter__(self):
"""The standard inorder traversal of a binary tree"""
if self:
if self._child_left:
for elem in self._child_left:
yield elem
yield self._key
if self._child_right:
for elem in self._child_right:
yield elemclass BinarySearchTree:
"""Binary search tree implementation""" def __init__(self):
self._root = None
self._size = 0 def __len__(self):
"""Tree size"""
return self._size def size(self):
"""Tree size"""
return self._size def __iter__(self):
"""Iterator"""
return self._root.__iter__() def __getitem__(self, key):
"""[] getter operator override"""
result = self.get(key)
if result:
return result
raise KeyError("Error, key not in tree") def get_root(self):
"""Get tree root"""
return self._root def set_root(self, node):
"""Set tree root"""
self._root = node root = property(get_root, set_root) def get(self, key):
"""Retrieve a value by the key"""
if self._root:
result = self._get(key, self._root)
if result:
return result.value
return None
else:
return None def _get(self, key, current_node):
"""Retrieve a value by the key (helper function)"""
if not current_node:
return None
if current_node.key == key:
return current_node
elif key < current_node.key:
return self._get(key, current_node.child_left)
else:
return self._get(key, current_node.child_right) def __setitem__(self, key, value):
"""[] setter operator override"""
self.put(key, value) def put(self, key, value):
"""Add new node"""
if self._root:
self._put(key, value, self._root)
else:
self._root = BinaryTreeNode(key, value)
self._size = self._size + 1 def _put(self, key, value, current_node):
"""Add new node (helper function)"""
if key < current_node.key:
if current_node.child_left:
self._put(key, value, current_node.child_left)
else:
current_node.child_left = BinaryTreeNode(
key, value, parent=current_node
)
else:
if current_node.child_right:
self._put(key, value, current_node.child_right)
else:
current_node.child_right = BinaryTreeNode(
key, value, parent=current_node
) def __contains__(self, key):
"""in operator override"""
return bool(self._get(key, self._root)) def __delitem__(self, key):
"""del operator override"""
self.delete(key) def delete(self, key):
"""Remove a node by its key"""
if self._size > 1:
node_to_remove = self._get(key, self._root)
if node_to_remove:
self._delete(node_to_remove)
self._size = self._size - 1
else:
raise KeyError("Error, key not in tree")
elif self._size == 1 and self._root.key == key:
self._root = None
self._size = self._size - 1
else:
raise KeyError("Error, key not in tree") def _delete(self, current_node):
"""Remove a node by its key (helper function)"""
if current_node.is_leaf(): # removing a leaf
if current_node == current_node.parent.child_left:
current_node.parent.child_left = None
else:
current_node.parent.child_right = None
elif current_node.has_children(): # removing a node with two children
successor = current_node.find_successor()
successor.splice_out()
current_node.key = successor.key
current_node.value = successor.value
else: # removing a node with one child
if current_node.get_child_left():
if current_node.is_child_left():
current_node.child_left.parent = current_node.parent
current_node.parent.child_left = current_node.child_left
elif current_node.is_child_right():
current_node.child_left.parent = current_node.parent
current_node.parent.child_right = current_node.child_left
else:
current_node.replace_payload(
current_node.child_left.key,
current_node.child_left.value,
current_node.child_left.child_left,
current_node.child_left.child_right,
)
else:
if current_node.is_child_left():
current_node.child_right.parent = current_node.parent
current_node.parent.child_left = current_node.child_right
elif current_node.is_child_right():
current_node.child_right.parent = current_node.parent
current_node.parent.child_right = current_node.child_right
else:
current_node.replace_payload(
current_node.child_right.key,
current_node.child_right.value,
current_node.child_right.child_left,
current_node.child_right.child_right,
) def inorder(self):
"""In-order tree traversal"""
self._inorder(self._root) def _inorder(self, tree):
"""In-order tree traversal (helper function)"""
if tree:
self._inorder(tree.child_left)
print(tree.key, end=" ")
self._inorder(tree.child_right) def postorder(self):
"""Post-order tree traversal"""
self._postorder(self._root) def _postorder(self, tree):
"""Post-order tree traversal (helper function)"""
if tree:
self._postorder(tree.child_left)
self._postorder(tree.child_right)
print(tree.key, end=" ") def preorder(self):
"""Pre-order tree traversal"""
self._preorder(self._root) def _preorder(self, tree):
"""Pre-order tree traversal (helper function)"""
if tree:
print(tree.key, end=" ")
self._preorder(tree.child_left)
self._preorder(tree.child_right) def clear(self):
"""Remove all nodes"""
while self._root:
self.delete(self._root.key)

from pythonds3.trees.binary_search_tree import BinarySearchTree
from pythonds3.trees.binary_search_tree import BinaryTreeNodeclass AVLTreeNode(BinaryTreeNode):
"""AVL Tree Node""" def __init__(self, key, val, balance_factor, left=None, right=None, parent=None):
"""Create an AVL tree node"""
BinaryTreeNode.__init__(self, key, val, left, right, parent)
self._balance_factor = balance_factor def get_balance_factor(self):
"""Get the node balance factor"""
return self._balance_factor def set_balance_factor(self, value):
"""Set the node balance factor"""
self._balance_factor = value balance_factor = property(get_balance_factor, set_balance_factor)class AVLTree(BinarySearchTree):
"""AVL tree implementation""" def __init__(self):
"""Create a new AVL tree"""
BinarySearchTree.__init__(self) def put(self, key, value):
"""Add new node"""
if self._root:
self._put(key, value, self._root)
else:
self._root = AVLTreeNode(key, value, 0)
self._size = self._size + 1 def _put(self, key, value, current_node):
"""Add a new node to the tree (helper function)"""
if key < current_node.key:
if current_node.get_child_left():
self._put(key, value, current_node.child_left)
else:
current_node.child_left = AVLTreeNode(
key, value, 0, parent=current_node
)
self.update_balance(current_node.child_left)
else:
if current_node.get_child_right():
self._put(key, value, current_node.child_right)
else:
current_node.child_right = AVLTreeNode(
key, value, 0, parent=current_node
)
self.update_balance(current_node.child_right) def update_balance(self, node):
"""Update the tree balance"""
if node.balance_factor > 1 or node.balance_factor < -1:
self.rebalance(node)
return
if node.parent:
if node.is_child_left():
node.parent.balance_factor += 1
elif node.is_child_right():
node.parent.balance_factor -= 1 if node.parent.balance_factor != 0:
self.update_balance(node.parent) def rebalance(self, node):
"""Rebalance the tree"""
if node.balance_factor < 0:
if node.child_right.balance_factor > 0:
# Do an LR Rotation
self.rotate_right(node.child_right)
self.rotate_left(node)
else:
# single left
self.rotate_left(node)
elif node.balance_factor > 0:
if node.child_left.balance_factor < 0:
# Do an RL Rotation
self.rotate_left(node.child_left)
self.rotate_right(node)
else:
# single right
self.rotate_right(node) def rotate_left(self, rotation_root):
"""Left rotation"""
new_root = rotation_root.child_right
rotation_root.child_right = new_root.child_left
if new_root.child_left:
new_root.child_left.parent = rotation_root
new_root.parent = rotation_root.parent
if rotation_root.is_root():
self._root = new_root
else:
if rotation_root.is_child_left():
rotation_root.parent.child_left = new_root
else:
rotation_root.parent.child_right = new_root
new_root.child_left = rotation_root
rotation_root.parent = new_root
rotation_root.balance_factor = (
rotation_root.balance_factor + 1 - min(new_root.balance_factor, 0)
)
new_root.balance_factor = (
new_root.balance_factor + 1 + max(rotation_root.balance_factor, 0)
) def rotate_right(self, rotation_root):
"""Right rotation"""
new_root = rotation_root.child_left
rotation_root.child_left = new_root.child_right
if new_root.child_right:
new_root.child_right.parent = rotation_root
new_root.parent = rotation_root.parent
if rotation_root.is_root():
self._root = new_root
else:
if rotation_root.is_child_right():
rotation_root.parent.child_right = new_root
else:
rotation_root.parent.child_left = new_root
new_root.child_right = rotation_root
rotation_root.parent = new_root
rotation_root.balance_factor = (
rotation_root.balance_factor - 1 - max(new_root.balance_factor, 0)
)
new_root.balance_factor = (
new_root.balance_factor - 1 + min(rotation_root.balance_factor, 0)
)

class BinaryHeap:
"""Minimal Binary Heap""" def __init__(self):
"""Create a heap"""
self._heap = [] def _perc_up(self, cur_idx):
"""Move a node up"""
while (cur_idx - 1) // 2 >= 0:
parent_idx = (cur_idx - 1) // 2
if self._heap[cur_idx] < self._heap[parent_idx]:
self._heap[cur_idx], self._heap[parent_idx] = (
self._heap[parent_idx],
self._heap[cur_idx],
)
cur_idx = parent_idx def _perc_down(self, cur_idx):
"""Move a node down"""
while 2 * cur_idx + 1 < len(self._heap):
min_child_idx = self._get_min_child(cur_idx)
if self._heap[cur_idx] > self._heap[min_child_idx]:
self._heap[cur_idx], self._heap[min_child_idx] = (
self._heap[min_child_idx],
self._heap[cur_idx],
)
else:
return
cur_idx = min_child_idx def _get_min_child(self, parent_idx):
"""Get a smaller child"""
if 2 * parent_idx + 2 > len(self._heap) - 1:
return 2 * parent_idx + 1
if self._heap[2 * parent_idx + 1] < self._heap[2 * parent_idx + 2]:
return 2 * parent_idx + 1
return 2 * parent_idx + 2 def heapify(self, not_a_heap, show_details=False):
"""Build a heap from any list"""
self._heap = not_a_heap[:]
cur_idx = len(self._heap) // 2 - 1
while cur_idx >= 0:
self._perc_down(cur_idx)
cur_idx = cur_idx - 1
if show_details:
print(self._heap) def insert(self, item):
"""Add a new item"""
self._heap.append(item)
self._perc_up(len(self._heap) - 1) def delete(self):
"""Remove an item"""
self._heap[0], self._heap[-1] = self._heap[-1], self._heap[0]
result = self._heap.pop()
self._perc_down(0)
return result def is_empty(self):
"""Check if the heap is empty"""
return not bool(self._heap) def __len__(self):
"""Get heap size"""
return len(self._heap) def __str__(self):
"""Heap as a string"""
return str(self._heap) def __contains__(self, item):
"""__contains__in method override"""
return item in self._heap