Python, drzewo binarne

0

Witam. Miałam do zaimplementowania drzewo binarne. Problem powstał w momencie, kiedy musiałam obliczyć wartości każdego poddrzewa wychodzącego z danego węzła. Wartości muszę porównać i jeżeli przekroczą daną wartość to drzewo się rozpada w danym węźle. Próbowałam rozgraniczyc chodzenie po lewym poddrzewie i prawym, ale to mi nie wyszło:

def chodzenie_na_lewo(self,node):
        if node.left is None:
            pass
        else:
            self.wielkosc_lewa.append(node.data) #lista lisci na lewo
            self.chodzenie_na_lewo(node.left)
            if node.right is not None:
                self.chodzenie_na_lewo(node.right)
                self.wielkosc_lewa.append(node.key)

Wiem, że moja metoda nie ma sensu, ale nie mam pojęcia jak to poprawić. Będę wdzięczna za wszelkie podpowiedzi.

0

def chodzenie_na_lewo(self,node):

koszmarne nazwy.

  1. po polsku, co się kiepsko komponuje o tyle, że język Python jak każdy inny język programowania jest po angielsku.
  2. po polsku, więc dłuższe słowo: chodzenie_na_lewo vs. walk_left, wielkosc_lewa vs. left_size
  3. "chodzenie" to imiesłów(jeśli dobrze pamiętam) a nie czasownik, trochę dziwnie brzmi jak na określenie metody

Wartości muszę porównać i jeżeli przekroczą daną wartość

jak to? To chcesz porównać je ze sobą czy z jakąś wartością?

0

Wiem, że po polsku nazwy nie bardzo wyglądają, dlatego staram się tego oduczyć, ale jak widać z marnym skutkiem :) Mam podaną przykładową wartość, np. 10 i muszę do siebie dodać wartości znajdujące się w liściach poddrzewa lewego i prawego danego węzła, żeby sprawdzić czy ich różnica będzie większa niż ta konkretna wartość.

0

Pokaż cały kod. Strzelam (mam nadzieję, że celnie), że masz klasę drzewa, a w tej klasie trzy pola: wartość oraz lewe i prawe drzewo. Stwórz metodę tej klasy, o nazwie np. walk_subtrees, która zwraca sumę wartości drzewa. I później wywołaj ją na lewej i prawej gałęzi (te gałęzie to przecież też drzewa). W twoim przypadku robisz coś dziwnego, mianowicie zamiast wywoływać twoją metodę na instancji lewej gałęzi, przekazujesz ją w parametrze. No i rozgraniczanie się na tylko na prawą bądź lewą stronę (tak jak robisz to ty) nie ma sensu.

0

Mój kod wygląda następująco:


#!/usr/bin/python
import random

class Tree:
    def __init__(self, root=None, size=0):
        self.root=root
        self.size=size
        #self.key_left=[]
        #self.key_right=[]

    def add(self, node, value):
        self.size=self.size+value
        direction=random.choice(['left','right'])
        if self.root is None:
            self.root=Node(value)
            return

        else:
            if direction=='left':
                self.root.add_left(value)
                return

            else:
                self.root.add_right(value)
                return

    def print_tree(self, node):
        if node is None:
            pass
        else:
            self.print_tree(node.left)
            print node.key
            self.print_tree(node.right)

    def walk_left(self,node):
        if node.left is None:
            pass
        else:
            #self.key_left.append(node.key)
            self.walk_left(node.left)
            if node.right is not None:
                self.walk_left(node.right)
                #self.key_left.append(node.key)

    def walk_right(self,node):
        if node.right is None:
            pass
        else:
            if node.left is None:
                self.walk_right(node.right)
                #self.key_right.append(node.key)
            else:
                self.walk_right(node.left)
                #self.key_right.append(node.key)

class Node:
    def __init__(self, key, left=None, right=None):
        self.key=key
        self.left=left
        self.right=right

    def add_left(self, value):
        if self.left is None:
            self.left=Node(value)
        else:
            direction=random.choice(['left','right'])
            if direction=='left':
                self.left.add_left(value)
            else:
                self.left.add_right(value)
        return

    def add_right(self, value):
        if self.right is None:
            self.right=Node(value)
        else:
            direction=random.choice(['left','right'])
            if direction=='right':
                self.right.add_right(value)
            else:
                self.right.add_left(value)
        return

if __name__ == '__main__':
    data=3
    diffrence=10 #dozwolona roznica miedzy dwoma poddrzewami
    tree=Tree()
    node=Node(data)
    tree.add(node,data)
    tree.add(node,data)
    tree.add(node,data)
    tree.add(node,data)
<\code>

Wyrzucę te moje dwie metody: walk_left i walk_right, ale wydaje mi się, że potrzebuję nowej metody w klasie Node, która będzie mi zwracała wielkość każdego węzła na lewo i prawo.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0