Problemi di programmazione orientata agli oggetti in Python durante l'implementazione di un albero di ricerca binario

Question

Problemi di programmazione orientata agli oggetti in Python durante l'implementazione di un albero di ricerca binario

#1 da (2 voti)

0

Sto passando dalla programmazione procedurale C alla programmazione OOP di Python e ho affrontato alcuni problemi durante l'implementazione di alberi di ricerca binari.

Non posso rendere il mio Tree_Node nullo in caso di cancellazione. In C ho potuto fare questo perché avrei gestito il caso nella funzione come segue:

    void insert(Node tree, int key)
    {
      if (tree == null)
      {
        // deal with it
      }
    }

Ma in Python usando OOP non posso rendere null il mio Tree_Node dato che è una classe e contiene tutti i miei metodi.

class Tree:
  # Tree methods

t = Tree()
t = None  # Cannot do this as then how would I call its methods

Q1) Come risolvete questo problema in generale? (non solo per gli alberi di ricerca binari) Qual è la pratica OOP standard per questo?

Il secondo problema è che non posso modificare autonomamente in Python. In C potrei fare come segue:

void foo(Node tree, int key)
{
  tree = tree->left
}

Ma nella classe Python non posso fare come segue:

class Tree:
  def foo(self, key):
    self = self.left  # Cannot do this

Q2) Quindi come risolvo tali problemi? Qualche pratica OOP standard?

Q3) Una meta domanda. Ho pensato che l'OOP faciliti la programmazione. Ma in questo caso, trovo molto difficile implementare una struttura dati piuttosto semplice. Aggiunge restrizioni come non essere in grado di modificare se stessi, non in grado di renderlo nulla ecc. Sto facendo qualcosa di sbagliato?

object-oriented python binary-tree

posta clereamusjd 14.07.2015 - 15:39

fonte

1 risposta

Leggi altre domande sui tag object-oriented python binary-tree

Gestione degli errori nelle funzioni della libreria matematica Alla ricerca di un paradigma di programmazione specifico [chiuso]

score 2 · Answer 1

Il modo OOP è combinare insieme polimorfismo e ricorsione. Un albero binario è definito come vuoto o un insieme di valori, sinistro e destro, dove sia la sinistra che la destra sono alberi binari. Per rappresentarlo correttamente, destra e sinistra devono essere essi stessi alberi binari, anche se sono vuoti.

Per rappresentarlo in modo orientato agli oggetti, avremo una sottoclasse albero base e nodo e vuoto . Queste sottoclassi conterranno implementazioni del metodo che accedono direttamente ai campi e la classe base può contenere metodi che utilizzano questi metodi:

from abc import ABCMeta, abstractmethod

class Tree(metaclass=ABCMeta):
    @abstractmethod
    def infix(self):
        pass

    def set(self):
        return set(self.infix())


class EmptyTree(Tree):
    def infix(self):
        yield from ()


class TreeNode(Tree):
    def __init__(self, value, left=EmptyTree(), right=EmptyTree()):
        self.value = value
        self.left = left
        self.right = right

    def depth(self):
        return 1 + max(self.left.depth(), self.right.depth())

    def infix(self):
        yield from self.left.infix()
        yield self.value
        yield from self.right.infix()


tree = TreeNode(1, TreeNode(2), TreeNode(3, EmptyTree(), TreeNode(4)))

assert list(tree.infix()) == [2, 1, 3, 4]

assert tree.set() == {1, 2, 3, 4}

assert list(EmptyTree().infix()) == []

assert EmptyTree().set() == set()

Il metodo infix è nelle sottoclassi, perché si comporta in modo diverso per EmptyTree e per TreeNode . Il metodo set è definito nella classe base, poiché si basa solo sul metodo infix definito per tutti gli alberi.

L'idea è che non ti controlli se un albero è vuoto - invochi semplicemente i suoi metodi, che possono essere diversi a seconda che l'albero sia vuoto (istanza di EmptyTree ) o meno (istanza di TreeNode ).