class Node: def init(self): self.deca = [] self.stanje = 0 self.g = [[""] * n] * m def…
- User
class Node:
def __init__(self): self.deca = [] self.stanje = 0 self.g = [[""] * n] * mdef proveri(g): for komb in odnosi: if komb[1] == "-": for i in range(m): for j in range(n): if komb[0] == g[i][j]: for k in range(m): if i != k: if g[k][j] == komb[2]: # print("PROVERA - ", g[i][j], g[k][j], "==", komb[2]) return -1 else: for i in range(m): for j in range(n): if komb[0] == g[i][j]: poz = 0 for k in range(m): if i != k: if g[k][j] == komb[2] or g[k][j] == "": poz = 1 if poz == 0: # print("PROVERA + ", g[i][j], "!+", komb[2]) return -1 t = 0 for i in range(m): for j in range(n): if g[i][j] != "": t += 1 if t == m * n: return 1 return 0
"""def izbroj(root): broj = 0 if root.deca: broj += root.deca.len() for i in root.deca: broj += izbroj(i) return broj"""
def preorder(root): print(root.g) print("") for i in root.deca: preorder(i)
def resenja(root, r): if root.stanje == 1 and root.deca.len() == 0: if root.g not in r: r.append(root.g) for i in root.deca: resenja(i, r)
def kreirajStablo(root): for i in range(m): for j in range(n): if root.g[i][j] == "": tr = list(root.g[i]) for vr in grupe[i]: if vr not in tr: novi = Node() for k in range(m): novi.g[k] = list(root.g[k]) novi.g[i][j] = vr novi.stanje = proveri(novi.g) root.deca.append(novi) if novi.stanje == 0: kreirajStablo(novi)
returnotvaranje = int(input("Izaberite nacin unosa: (0 - konzolni unos, 1 - ulaz.txt unos) "))
if otvaranje == 0: m = int(input("m: ")) n = int(input("n: ")) grupe = [] for u in range(m): grupe.append(input(str(u) + ". red grupe: ").split(',')) odnosi = [] while True: s = input("odnos: ") if s == "": break if s.contains("+"): odnosi.append([s.split("+")[0], "+", s.split("+")[1]]) if s.contains("-"): odnosi.append([s.split("-")[0], "-", s.split("-")[1]])
if otvaranje == 1: with open('ulaz.txt', 'r') as f: m = int(f.readline()) n = int(f.readline())
grupe = [] for u in range(m): grupe.append(f.readline().strip("\n").split(',')) odnosi = [] while True: s = f.readline().strip("\n") if not s: break if s.__contains__("+"): odnosi.append([s.split("+")[0], "+", s.split("+")[1]]) if s.__contains__("-"): odnosi.append([s.split("-")[0], "-", s.split("-")[1]]) f.close()pocetna = Node() pocetna.g[0] = grupe[0] kreirajStablo(pocetna) resenjaPocetne = [] resenja(pocetna, resenjaPocetne) trenutna = pocetna
ovo je kod koji imam treba ispraviti funkciju kreirajStablo tako da ne koristi rekurziju, vec iterativno generise stablo
- Assistant
def kreirajStablo(root): stack = [root] while stack: current = stack.pop() for i in range(m): for j in range(n): if current.g[i][j] == "": tr = list(current.g[i]) for vr in grupe[i]: if vr not in tr: novi = Node() for k in range(m): novi.g[k] = list(current.g[k]) novi.g[i][j] = vr novi.stanje = proveri(novi.g) current.deca.append(novi) if novi.stanje == 0: stack.append(novi) return
- User
takodje ispraviti funkciju preorder tako da iterativno obilazi stablo, i ne koristi rekurziju
- Assistant
def preorder(root): stack = [root] while stack: current = stack.pop() print(current.g) print("") for i in reversed(current.deca): stack.append(i)
- User
takodje ispraviti funkciju resenja da ne koristi rekurziju
- Assistant
def resenja(root): r = [] stack = [root] while stack: current = stack.pop() if current.stanje == 1 and current.deca.len() == 0: if current.g not in r: r.append(current.g) for i in reversed(current.deca): stack.append(i) return r
- User
kako ispisati pogodno formatiran, po nivoima, ispis stabla, koristeci preorder traversal
- Assistant
Možemo iskoristiti pre-order traversal da bismo simulirali ispis stabla po nivoima. Ideja je da ispisujemo sadržaj čvora, a zatim sve njegove potomke u narednom redu.
Implementacija bi izgledala ovako:
def ispisStabla(root): queue = [root] current_level = 1 while queue: current = queue.pop(0) if current.stanje == 1: print(f'Level {current_level}: {current.g}') current_level += 1 for child in current.deca: queue.append(child)Ovde prvo inicijalizujemo red sa korenom stabla
root, i brojačem nivoacurrent_level. U petlji sve dok red nije prazan, izvlačimo čvorcurrentiz reda. Ako jecurrentzavršni čvor i nalazi se na trenutnom nivou (korenu počinjemo od 1), ispisujemo njegov sadržaj u formatiranom obliku. Uvećavamo brojač trenutnog nivoa za 1. Nakon toga, dodajemo sve potomke čvoracurrentu red.Ova implementacija nam omogućava ispisivanje stabla po nivoima kako bismo bolje vizualizirali njegovu strukturu.
- User
napisi funkciju ispisStabla sa indentacijom
- Assistant
Možemo dodati indentaciju kako bi dobili jasniju strukturu stabla. Indentaciju ćemo računati kao 4 * nivo čvora.
Implementacija bi izgledala ovako:
def ispisStabla(root): queue = [(root, 1)] current_level = 1 while queue: current, level = queue.pop(0) if current.stanje == 1: indentacija = ' ' * (level - 1) print(f'{indentacija}Level {level}: {current.g}') current_level += 1 for child in current.deca: queue.append((child, level + 1))Ovde lista sadrži parove (čvor, nivo). Inicijalizujemo listu sa korenom
rooti prvim nivoom postavljenim na 1. U petlji sve dok lista nije prazna, izvlačimo čvorcurrenti nivoleveliz liste. Ako jecurrentzavršni čvor i nalazi se na trenutnom nivou, računamo indentaciju na osnovu nivoa. Na kraju ispisujemo sadržaj čvora sa odgovarajućom indentacijom. Uvećavamo brojač trenutnog nivoa za 1. Nakon toga, dodajemo sve potomke čvoracurrentu listu sa nivoom uvećanim za 1.