Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: вежбе - 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]