Основи програмирања: вежбе - XV недеља
Пример како из небалансираног бинарног стабла претраживања добијамо балансирано стабло претраживања
Решење
# Дефиниција чвора бинарног стабла
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
def inorder(root,nodes):
# Основни случај
if not root:
return
inorder(root.left,nodes)
nodes.append(root)
inorder(root.right,nodes)
# Из сортираног низа добијамо балансирано бинарно стабло претраживања
def buildTreeUtil(nodes,start,end):
# Основни случај
if start>end:
return None
# Узимамо средњи елемент да буде root
mid=(start+end)//2
node=nodes[mid]
# користећи се индексима рекуризвно позивамо функцију да би добили балансирано стабло
node.left=buildTreeUtil(nodes,start,mid-1)
node.right=buildTreeUtil(nodes,mid+1,end)
return node
# Функција која као аргуемнт прима корен небалансираног стабла, и позива пређашње функције како би добили балансирано стабло
def buildTree(root):
# Store nodes of given BST in sorted order
nodes=[]
inorder(root,nodes)
# Constructs BST from nodes[]
n=len(nodes)
return buildTreeUtil(nodes,0,n-1)
def preOrder(root):
if not root:
return
print("{} ".format(root.data),end="")
preOrder(root.left)
preOrder(root.right)
# Конструкција бинарног стабла
# 10
# /
# 8
# /
# 7
# /
# 6
# /
# 5
root = Node(10)
root.left = Node(8)
root.left.left = Node(7)
root.left.left.left = Node(6)
root.left.left.left.left = Node(5)
print("Preorder небалансираног стабла је :")
preOrder(root)
# 'балансирамо' стабло
root = buildTree(root)
print("Preorder балансираног стабла је :")
preOrder(root)
Задатак 1
За дате корене p и q бинарних стабала, написати функцију која одређује да ли су идентични или не. Два бинарна стабла се сматрају идентичним ако су структурално идентични и њихови чворови имају исте вредности.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def isSameTree(p, q):
#kada oba korena ne postoje
if not p and not q:
return True
#kada jedan ne postoji
if (not p and q) or (not q and p):
return False
#oba postoje ali
#su im vrednosti razlicite
if p.val != q.val:
return False
#oba postoje ali
#su im vrednosti iste
return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
Задатак 2
За дате корен root бинарног стабла, написати функцију која ће изокренути стабло и вратити корен тог стабла.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def invertTree(root):
# base case
if not root:
return None
#zamenimo levo dete i desno dete
root.left, root.right = root.right, root.left
#pozovemo rekurziju za levo dete i desno dete
invertTree(root.left)
invertTree(root.right)
return root
Задатак 3
За дате корен root бинарног стабла, написати функцију која ће дубину тог стабла.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left),maxDepth(root.right))
Задатак 4
За дате корене root и subRoot бинарних стабала, вратити true ако се subRoot налази као подстабло у стаблу root, у супротном вратити false.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def isSubtree(root, subRoot):
def isSametree(p,q):
if (not p and q) or (not q and p):
return False
if not p and not q:
return True
if p.val != q.val:
return False
return isSametree(p.left,q.left) and isSametree(p.right,q.right)
if not subRoot:
return True
if not root:
return False
if isSametree(root,subRoot):
return True
return isSubtree(root.left,subRoot) or isSubtree(root.right,subRoot)
Задатак 5
За дат корен root бинарног стабла, вратити дужину дијаметра тог стабла. Дијаметар бинарног стабла је дужина најдуже путање између два чвора у стаблу. А та дужина се мери бројем ивица измећу њих.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def diameterOfBinaryTree(root):
res = [0]
def f(root):
if not root:
return -1
left_height=f(root.left)
right_height=f(root.right)
res[0] = max(res[0],2+left_height+right_height)
return 1 + max(left_height,right_height)
f(root)
return res[0]