python kód pre binárny vyhľadávací strom
#Complete Binary Search Tree Using Python 3
class node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class binarytree:
def __init__(self):
self.root=None
#INSERT
def insert(self,data):
if self.root==None:
self.root=node(data)
else:
self._insert(data,self.root)
def _insert(self,data,cur_node):
if data<cur_node.data:
if cur_node.left==None:
cur_node.left=node(data)
else:
self._insert(data,cur_node.left)
elif data>cur_node.data:
if cur_node.right==None:
cur_node.right=node(data)
else:
self._insert(data,cur_node.right)
else:
print('Data In Treee Already')
#REMOVE
def remove(self,data):
if self.root!=None:
self._remove(data,self.root)
def _remove(self,data,cur_node):
if cur_node == None:
return cur_node
if data<cur_node.data:
cur_node.left=self._remove(data,cur_node.left)
elif data>cur_node.data:
cur_node.right=self._remove(data,cur_node.right)
else:
if cur_node.left is None and cur_node.right is None:
print('Removing Leaf Node')
if cur_node==self.root:
self.root=None
del cur_node
return None
if cur_node.left is None:
print('Removing None with Right Child')
if cur_node==self.root:
self.root=cur_node.right
tempnode=cur_node.right
del cur_node
return tempnode
elif cur_node.right is None:
print('Removing None with Left Child')
if cur_node==self.root:
self.root=cur_node.left
tempnode=cur_node.left
del cur_node
return tempnode
print('Removing Node with 2 Children')
tempnode=self.getpred(cur_node.left)
cur_node.data=tempnode.data
cur_node.left=self._remove(cur_node.data,cur_node.left)
return cur_node
def getpred(self,cur_node):
if cur_node.right!=None:
return self.getpred(cur_node.right)
return cur_node
#INORDER TRAVERSAL
def inorder(self):
if self.root!=None:
self._inorder(self.root)
def _inorder(self,cur_node):
if cur_node!=None:
self._inorder(cur_node.left)
print(cur_node.data)
self._inorder(cur_node.right)
#PREORDER TRAVERSAL
def preorder(self):
if self.root!=None:
self._preorder(self.root)
def _preorder(self,cur_node):
if cur_node!=None:
print(cur_node.data)
self._preorder(cur_node.left)
self._preorder(cur_node.right)
#POSTORDER TRAVERSAL
def postorder(self):
if self.root!=None:
self._postorder(self.root)
def _postorder(self,cur_node):
if cur_node!=None:
self._postorder(cur_node.left)
self._postorder(cur_node.right)
print(cur_node.data)
#MINIMUM VALUE
def minval(self):
if self.root!=None:
return self._minval(self.root)
def _minval(self,cur_node):
if cur_node.left!=None:
return self._minval(cur_node.left)
return cur_node.data
#MAXIMUM VALUE
def maxval(self):
if self.root!=None:
return self._maxval(self.root)
def _maxval(self,cur_node):
if cur_node.right!=None:
return self._maxval(cur_node.right)
return cur_node.data
tree=binarytree()
tree.insert(100)
tree.insert(90) # 100
tree.insert(110) # / \
tree.insert(95) # 90 110
tree.insert(30) # / \
# 30 95
tree.remove(110)
tree.remove(90)
tree.inorder()
#tree.preorder()
#tree.postorder()
print(tree.minval())
print(tree.maxval())
binárny vyhľadávací strom v jazyku python
Binary Search Tree at this link:
https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/BinaryTrees
Binárny vyhľadávací strom v jazyku python
# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root নোডের পরিবর্তন ঘটবে।
এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none),
then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change.
This is why we return to the root node.
'''
# second system:
class TreeNode:
def __init__(self,data):
self.data = data
self.parent = None
self.left = None
self.right = None
def __repr__(self):
return repr(self.data)
def add_left(self, node):
self.left = node
if node is not None:
node.parent = self
def add_right(self, node):
self.right = node
node.parent = self
# now bst_insert:
def bst_insert(root,node):
last_node = None
current_node = root
while current_node is not None:
last_node = current_node
if node.data < current_node.data:
current_node = current_node.left
else:
current_node = current_node.right
if last_node is None:
# tree was empty. node is the only node, hence root
root = node # new node add
elif node.data < last_node.data:
last_node.add_left(node)
else:
last_node.add_right(node)
return root
'''
_10_
/ \
5 17
/ / \
3 12 19
/ \
1 4
'''
# now create_bst:
def create_bst():
root = TreeNode(10)
for item in [5,17,3,7,12,19,1,4]:
node = TreeNode(item)
root = bst_insert(root, node)
return root
# In_order tree traverse:
def in_order(node):
if node.left:
in_order(node.left)
print(node)
if node.right:
in_order(node.right)
# bst- tree minimum node:
def bst_minimum(root):
while root.left is not None:
root = root.left
print(root)
# Node transfer:
def bst_transfer(root, current_node, new_node):
if current_node.parent is None:
root = new_node
elif current_node == current_node.parent.left:
current_node.parent.add_left(new_node)
else:
current_node.parent.add_right(new_node)
return root
# Node delete:
def bst_delete(root,node):
if node.left is None:
root = bst_transfer(root,node,node.right)
elif node.right is None:
root = bst_transfer(root,node,node.left)
else:
min_node = bst_minimum(node.right)
if min_node.parent != node:
root = bst_transfer(root,min_node,min_node.right)
min_node.add_right(node.right)
root = bst_transfer(root,node,min_node)
min_node.add_left(node.left)
return root
# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
while node is not None:
if node.data == key:
return node
if key < node.data:
node = node.left
else:
node = node.right
return node
# Now check to your code:
if __name__ == "__main__":
root = create_bst()
print("Tree is root =",root)
print()
print("BST:")
in_order(root)
for key in [1,5,10]:
node = best_search(root,key)
print("will delete =", node)
root = bst_delete(root,node)
print("BST:")
in_order(root)
binárny strom v jazyku python
Binary Tree implementation at this link:
https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/BinaryTrees
"""
17
/ \
/ \
/ \
4 20
/\ /\
/ \ / \
/ \ / \
1 9 18 23
\
\
\
34
"""
# Binary Search Tree implementation in Python
class BinaryTreeNode():
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add_child(self, data):
if data == self.data: # check if the of new data exist already in the tree, if yes don't add
return
if data < self.data:
# Add to left subtree
if self.left:
self.left.add_child(data) # Recursively call the add_child method to add the data to an appropriate place
else:
self.left = BinaryTreeNode(data)
else:
# Add to right subtree
if self.right:
self.right.add_child(data) # Recursively call the add_child method to add the data to an appropriate place
else:
self.right = BinaryTreeNode(data)
# Visit Left subtree, then Root node and finaly Right subtree
def in_order_traversal(self): # Left - Root - Right
elements = []
# Getting all elements of the Left Subtree
if self.left:
elements += self.left.in_order_traversal() # Recursively get all the elements of the left subtree and add them into the list
elements.append(self.data) # Adding the root node to the list
# Getting all elements of the Right Subtree
if self.right:
elements += self.right.in_order_traversal() # Recursively get all the elements of the right subtree and add them into the list
return elements
# Get all elements from the Root node then the left subtree and finanally the Right subtree
def pre_order_traversal(self): # Root - Left - Right
elements = []
elements.append(self.data)
if self.left:
elements += self.left.pre_order_traversal() # Recursively get all the elements of the left subtree and add them into the list
if self.right:
elements += self.right.pre_order_traversal() # Recursively get all the elements of the right subtree and add them into the list
return elements # get the Root node element
# Get all elements from the Right subtree then the left subtree and finally the Root node
def post_order_traversal(self):
elements = []
if self.left:
elements += self.left.post_order_traversal() # Recursively get all the elements of the left subtree and add them into the list
if self.right:
elements += self.right.post_order_traversal() # Recursively get all the elements of the right subtree and add them into the list
elements.append(self.data) # Get the Root node element
return elements
def search_element(self, elem): # complexity of log n O(log n)
if self.data == elem:
return True
elif elem < self.data:
# This means if present, element would be on the left
if self.left:
return self.left.search_element(elem)
else:
return False
else:
# This means if present, element would be on the right
if self.right:
return self.right.search_element(elem)
else:
return False
def sum_of_all_elements_in_tree(self):
return sum(self.in_order_traversal())
def max_element_in_tree(self):
return max(self.in_order_traversal())
def min_element_in_tree(self):
return min(self.in_order_traversal())
# Tree Builder helper method
def build_binary_tree(lst_elem: list):
if len(lst_elem) >1:
root_node = BinaryTreeNode(lst_elem[0])
for i in lst_elem[1:]:
root_node.add_child(i)
#root_node.search_element(20)
#print(root_node.in_order_traversal())
return root_node
else:
return print("Insufficient number of elements")
if __name__ == '__main__':
mt = build_binary_tree([17, -5, 4, 1, 20, 9, -1, 23, 18, 0, 34])
print("In Order Traversal", mt.in_order_traversal())
print("Post Order Traversal", mt.post_order_traversal())
print("Pre Order Traversal", mt.pre_order_traversal())
print(mt.search_element(20))
print("Sum of all elemnts in tree", mt.sum_of_all_elements_in_tree())
print("Max element in tree is", mt.max_element_in_tree())
print("Min element in tree is", mt.min_element_in_tree())
binárny strom v Pythone
Binary Tree implementation at this link:
https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/BinaryTrees
binárne vyhľadávanie v Pythone
def binary_search(group, suspect):
group.sort()
midpoint = len(group)//2
while(True):
if(group[midpoint] == suspect):
return midpoint
if(suspect > group[midpoint]):
group = group[midpoint]
if(suspect < group[midpoint]):
group = group[0: midpoint]
midpoint = (len(group)//2)
class BSTNode:
def __init__(self, key=None):
self.left = None
self.right = None
self.key = key
# Insert method can add a list of nodes to the BST
def insert(self, keyList):
for i in keyList:
self.insertKey(i)
# This insertKey
def insertKey(self, key):
if not self.key:
self.key = key
return
if self.key == key:
return
if key < self.key:
if self.left:
self.left.insertKey(key)
return
self.left = BSTNode(key)
return
if self.right:
self.right.insertKey(key)
return
self.right = BSTNode(key)
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = '%s' % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
#Inorder Walk
def inorder(self):
if self.left:
self.left.inorder()
print(self.key)
if self.right:
self.right.inorder()
a = BSTNode()
a.insert([5,7,4,3,5,1,3,6]) #inserting some random numbers in the form of list
a.inorder()
a.display()
vložte binárny vyhľadávací strom
void BSNode::insert(std::string value) {
if (this->_data == value) {
_count++;
return;
}
if (this->_data > value) {
if (this->getLeft() == nullptr) {
this->_left = new BSNode(value);
}
this->getLeft()->insert(value);
return;
}
if (this->getRight() == nullptr) {
this->_right = new BSNode(value);
return;
}
this->getRight()->insert(value);
}
binárny vyhľadávací strom v Pythone
Binary Search Tree at this link:
https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/BinaryTrees