Como posso implementar uma árvore em Python?

Respostas:

232

anytree

Eu recomendo https://pypi.python.org/pypi/anytree (eu sou o autor)

Exemplo

from anytree import Node, RenderTree

udo = Node("Udo")
marc = Node("Marc", parent=udo)
lian = Node("Lian", parent=marc)
dan = Node("Dan", parent=udo)
jet = Node("Jet", parent=dan)
jan = Node("Jan", parent=dan)
joe = Node("Joe", parent=dan)

print(udo)
Node('/Udo')
print(joe)
Node('/Udo/Dan/Joe')

for pre, fill, node in RenderTree(udo):
    print("%s%s" % (pre, node.name))
Udo
├── Marc
   └── Lian
└── Dan
    ├── Jet
    ├── Jan
    └── Joe

print(dan.children)
(Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))

Recursos

anytree também possui uma API poderosa com:

  • criação simples de árvore
  • modificação simples da árvore
  • pré-ordenar a iteração da árvore
  • iteração de árvore de pós-ordem
  • resolver caminhos de nó relativos e absolutos
  • andando de um nó para outro.
  • renderização em árvore (veja o exemplo acima)
  • conexões de conexão / desconexão de nó
c0fec0de
fonte
31
Simplesmente a melhor resposta, outros estão reinventando a roda.
Ondrej
66
É uma boa forma de divulgar que você é o autor do pacote que está recomendando em sua resposta.
John Y
3
@ c0fec0de eu te amo !!!! Esta biblioteca é incrível, ainda tem uma funcionalidade de visualização
layser
2
@Ondrej bem, as outras respostas são menos dependentes e a pergunta original perguntou sobre estruturas de dados internas. Embora anytreeseja provavelmente uma ótima biblioteca, esta é uma questão de python, não uma questão do Node.js.
Rob Rose
Me deparei com esta resposta via Google. Essa biblioteca é muito legal. Adoro especialmente a capacidade de usar a classe mixin para criar uma árvore de qualquer objeto!
Rÿck Nöthing 8/03/19
104

O Python não possui a ampla variedade de estruturas de dados "internas", como o Java. No entanto, como o Python é dinâmico, é fácil criar uma árvore geral. Por exemplo, uma árvore binária pode ser:

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

Você pode usá-lo assim:

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"
Greg Hewgill
fonte
109
Isso realmente não explica muito sobre como fazer uma implementação de árvore útil.
Mike Graham
14
A questão é marcado com Python3, não há nenhuma necessidade para derivar class Treede objeto, em seguida,
TPI
3
@cfi Derivar de objectàs vezes é apenas uma diretriz: se uma classe não herda de nenhuma outra classe base, herda explicitamente do objeto. Isso também se aplica a classes aninhadas. Veja o Guia de estilos do Google Python
Konrad Reiche
16
@platzhirsch: Leia e cite completamente a diretriz: o Google indica explicitamente que isso é necessário para que o código Python 2 funcione conforme o esperado e recomendado para melhorar a compatibilidade com o Py3. Aqui estamos falando sobre código Py3. Não há necessidade de digitar legados extras.
TPI
13
Essa é uma árvore binária, não geral, conforme solicitado.
Michael Dorner
49

Uma árvore genérica é um nó com zero ou mais filhos, cada um um nó (árvore) apropriado. Não é o mesmo que uma árvore binária, são estruturas de dados diferentes, embora ambas compartilhem alguma terminologia.

Não existe nenhuma estrutura de dados integrada para árvores genéricas no Python, mas é facilmente implementada com classes.

class Tree(object):
    "Generic tree node."
    def __init__(self, name='root', children=None):
        self.name = name
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)
    def __repr__(self):
        return self.name
    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children.append(node)
#    *
#   /|\
#  1 2 +
#     / \
#    3   4
t = Tree('*', [Tree('1'),
               Tree('2'),
               Tree('+', [Tree('3'),
                          Tree('4')])])
Rudá Moura
fonte
Incrível, isso também pode ser facilmente usado como gráfico! O único problema que vi foi: Como posso diferenciar o nó esquerdo do nó direito?
Ângelo Polotto
3
Pelo índice de crianças. Esquerda sempre terá filhos [0] nesse caso.
Freund Allein
38

Podes tentar:

from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

Conforme sugerido aqui: https://gist.github.com/2012250

Ib33X
fonte
Se você deseja estender a um uma quantidade arbitrária de níveis verificar: stackoverflow.com/a/43237270/511809
natbusa
isso oculta o hash da função integrada.
precisa saber é o seguinte
20
class Node:
    """
    Class Node
    """
    def __init__(self, value):
        self.left = None
        self.data = value
        self.right = None

class Tree:
    """
    Class tree will provide a tree as well as utility functions.
    """

    def createNode(self, data):
        """
        Utility function to create a node.
        """
        return Node(data)

    def insert(self, node , data):
        """
        Insert function will insert a node into tree.
        Duplicate keys are not allowed.
        """
        #if tree is empty , return a root node
        if node is None:
            return self.createNode(data)
        # if data is smaller than parent , insert it into left side
        if data < node.data:
            node.left = self.insert(node.left, data)
        elif data > node.data:
            node.right = self.insert(node.right, data)

        return node


    def search(self, node, data):
        """
        Search function will search a node into tree.
        """
        # if root is None or root is the search data.
        if node is None or node.data == data:
            return node

        if node.data < data:
            return self.search(node.right, data)
        else:
            return self.search(node.left, data)



    def deleteNode(self,node,data):
        """
        Delete function will delete a node into tree.
        Not complete , may need some more scenarion that we can handle
        Now it is handling only leaf.
        """

        # Check if tree is empty.
        if node is None:
            return None

        # searching key into BST.
        if data < node.data:
            node.left = self.deleteNode(node.left, data)
        elif data > node.data:
            node.right = self.deleteNode(node.right, data)
        else: # reach to the node that need to delete from BST.
            if node.left is None and node.right is None:
                del node
            if node.left == None:
                temp = node.right
                del node
                return  temp
            elif node.right == None:
                temp = node.left
                del node
                return temp

        return node






    def traverseInorder(self, root):
        """
        traverse function will print all the node in the tree.
        """
        if root is not None:
            self.traverseInorder(root.left)
            print root.data
            self.traverseInorder(root.right)

    def traversePreorder(self, root):
        """
        traverse function will print all the node in the tree.
        """
        if root is not None:
            print root.data
            self.traversePreorder(root.left)
            self.traversePreorder(root.right)

    def traversePostorder(self, root):
        """
        traverse function will print all the node in the tree.
        """
        if root is not None:
            self.traversePostorder(root.left)
            self.traversePostorder(root.right)
            print root.data


def main():
    root = None
    tree = Tree()
    root = tree.insert(root, 10)
    print root
    tree.insert(root, 20)
    tree.insert(root, 30)
    tree.insert(root, 40)
    tree.insert(root, 70)
    tree.insert(root, 60)
    tree.insert(root, 80)

    print "Traverse Inorder"
    tree.traverseInorder(root)

    print "Traverse Preorder"
    tree.traversePreorder(root)

    print "Traverse Postorder"
    tree.traversePostorder(root)


if __name__ == "__main__":
    main()
shivam garg
fonte
3
Você pode adicionar apenas algumas notas para apresentar seu código e sua implementação?
Michele d'Amico
Obrigado pela implementação completa da Árvore Binária com funções utilitárias. Como é o Python 2, criei uma essência para a implementação da Árvore Binária (Py3) para pessoas que precisam de uma versão do Python 3.
CᴴᴀZ
16

Não há árvores embutidas, mas você pode facilmente construir uma subclassificando um tipo de Nó da Lista e escrevendo os métodos de deslocamento. Se você fizer isso, achei a bissetriz útil.

Também há muitas implementações no PyPi que você pode navegar.

Se bem me lembro, a lib padrão do Python não inclui estruturas de dados em árvore pelo mesmo motivo que a biblioteca de classes base .NET não: a localidade da memória é reduzida, resultando em mais falhas de cache. Nos processadores modernos, geralmente é mais rápido inserir apenas uma grande parte da memória no cache, e as estruturas de dados "ricas em ponteiros" negam o benefício.

Justin R.
fonte
2
FYI: As interwebs estão cheias de ódio contra Boost. Aparentemente, é uma dor enorme para lidar, especialmente porque o suporte a ela foi interrompido. Então, eu recomendo ficar longe de que
inspectorG4dget
Obrigado. Não tive nenhum problema pessoalmente, mas não quero enganar, por isso removi essa referência.
Justin R.
11

Eu implementei uma árvore enraizada como um dicionário {child:parent}. Por exemplo, com o nó raiz 0, uma árvore pode se parecer com isso:

tree={1:0, 2:0, 3:1, 4:2, 5:3}

Essa estrutura facilitou a subida ao longo de um caminho de qualquer nó até a raiz, o que era relevante para o problema em que eu estava trabalhando.

pata
fonte
1
Era assim que eu pensava em fazê-lo, até ver a resposta. Embora como uma árvore seja pai de dois filhos, e se você quiser descer, pode fazê-lo {parent:[leftchild,rightchild]}.
JFA
1
Outra maneira é usar listas de listas em que o primeiro (ou mais) elemento da lista é o valor do nó e as duas listas aninhadas a seguir representam suas subárvores esquerda e direita (ou mais para a árvore n-ária).
pepr
9

A resposta de Greg Hewgill é ótima, mas se você precisar de mais nós por nível, poderá usar um dicionário de lista | para criá-los: E use o método para acessá-los por nome ou ordem (como id)

class node(object):
    def __init__(self):
        self.name=None
        self.node=[]
        self.otherInfo = None
        self.prev=None
    def nex(self,child):
        "Gets a node by number"
        return self.node[child]
    def prev(self):
        return self.prev
    def goto(self,data):
        "Gets the node by name"
        for child in range(0,len(self.node)):
            if(self.node[child].name==data):
                return self.node[child]
    def add(self):
        node1=node()
        self.node.append(node1)
        node1.prev=self
        return node1

Agora, basta criar uma raiz e construí-la: ex:

tree=node()  #create a node
tree.name="root" #name it root
tree.otherInfo="blue" #or what ever 
tree=tree.add() #add a node to the root
tree.name="node1" #name it

    root
   /
child1

tree=tree.add()
tree.name="grandchild1"

       root
      /
   child1
   /
grandchild1

tree=tree.prev()
tree=tree.add()
tree.name="gchild2"

          root
           /
        child1
        /    \
grandchild1 gchild2

tree=tree.prev()
tree=tree.prev()
tree=tree.add()
tree=tree.name="child2"

              root
             /   \
        child1  child2
       /     \
grandchild1 gchild2


tree=tree.prev()
tree=tree.goto("child1") or tree=tree.nex(0)
tree.name="changed"

              root
              /   \
         changed   child2
        /      \
  grandchild1  gchild2

Isso deve ser o suficiente para você começar a descobrir como fazer isso funcionar

Bruno
fonte
Falta algo nesta resposta. Eu estava tentando esta solução nos últimos 2 dias e acho que você tem algum fluxo lógico no método de adição de objeto. Vou enviar minha resposta a esta pergunta. Verifique isso e me informe se posso ajudar.
MAULIK MODI
8
class Tree(dict):
    """A tree implementation using python's autovivification feature."""
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

    #cast a (nested) dict to a (nested) Tree class
    def __init__(self, data={}):
        for k, data in data.items():
            if isinstance(data, dict):
                self[k] = type(self)(data)
            else:
                self[k] = data

funciona como um dicionário, mas fornece quantos dicionários aninhados você deseja. Tente o seguinte:

your_tree = Tree()

your_tree['a']['1']['x']  = '@'
your_tree['a']['1']['y']  = '#'
your_tree['a']['2']['x']  = '$'
your_tree['a']['3']       = '%'
your_tree['b']            = '*'

entregará um ditado aninhado ... que funciona como uma árvore.

{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}

... Se você já possui um ditado, ele converterá cada nível em uma árvore:

d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)

print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch

Dessa forma, você pode manter a edição / adição / remoção de cada nível de ditado, conforme desejar. Todos os métodos de ditado para travessia etc, ainda se aplicam.

natbusa
fonte
2
Existe uma razão pela qual você optou por estender em dictvez de defaultdict? Nos meus testes, estender em defaultdictvez de dict e depois adicionar self.default_factory = type(self)ao topo do init deve funcionar da mesma maneira.
Rob Rose
provavelmente estou perdendo alguma coisa aqui, como você navega nessa estrutura? Parece muito difícil para ir de filhos aos pais, por exemplo, ou irmãos
Stormsson
6

Implementei árvores usando dict aninhados. É muito fácil de fazer e funcionou para mim com conjuntos de dados bastante grandes. Publiquei uma amostra abaixo e você pode ver mais no código do Google

  def addBallotToTree(self, tree, ballotIndex, ballot=""):
    """Add one ballot to the tree.

    The root of the tree is a dictionary that has as keys the indicies of all 
    continuing and winning candidates.  For each candidate, the value is also
    a dictionary, and the keys of that dictionary include "n" and "bi".
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.

    If candidate c is a winning candidate, then that portion of the tree is
    expanded to indicate the breakdown of the subsequently ranked candidates.
    In this situation, additional keys are added to the tree[c] dictionary
    corresponding to subsequently ranked candidates.
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
    tree[c][d]["n"] is the number of ballots that rank c first and d second.
    tree[c][d]["bi"] is a list of the corresponding ballot indices.

    Where the second ranked candidates is also a winner, then the tree is 
    expanded to the next level.  

    Losing candidates are ignored and treated as if they do not appear on the 
    ballots.  For example, tree[c][d]["n"] is the total number of ballots
    where candidate c is the first non-losing candidate, c is a winner, and
    d is the next non-losing candidate.  This will include the following
    ballots, where x represents a losing candidate:
    [c d]
    [x c d]
    [c x d]
    [x c x x d]

    During the count, the tree is dynamically updated as candidates change
    their status.  The parameter "tree" to this method may be the root of the
    tree or may be a sub-tree.
    """

    if ballot == "":
      # Add the complete ballot to the tree
      weight, ballot = self.b.getWeightedBallot(ballotIndex)
    else:
      # When ballot is not "", we are adding a truncated ballot to the tree,
      # because a higher-ranked candidate is a winner.
      weight = self.b.getWeight(ballotIndex)

    # Get the top choice among candidates still in the running
    # Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
    # we are looking for the top choice over a truncated ballot.
    for c in ballot:
      if c in self.continuing | self.winners:
        break # c is the top choice so stop
    else:
      c = None # no candidates left on this ballot

    if c is None:
      # This will happen if the ballot contains only winning and losing
      # candidates.  The ballot index will not need to be transferred
      # again so it can be thrown away.
      return

    # Create space if necessary.
    if not tree.has_key(c):
      tree[c] = {}
      tree[c]["n"] = 0
      tree[c]["bi"] = []

    tree[c]["n"] += weight

    if c in self.winners:
      # Because candidate is a winner, a portion of the ballot goes to
      # the next candidate.  Pass on a truncated ballot so that the same
      # candidate doesn't get counted twice.
      i = ballot.index(c)
      ballot2 = ballot[i+1:]
      self.addBallotToTree(tree[c], ballotIndex, ballot2)
    else:
      # Candidate is in continuing so we stop here.
      tree[c]["bi"].append(ballotIndex)
gaefan
fonte
5

Publiquei uma implementação em árvore do Python [3] no meu site: http://www.quesucede.com/page/show/id/python_3_tree_implementation .

Espero que seja útil,

Ok, aqui está o código:

import uuid

def sanitize_id(id):
    return id.strip().replace(" ", "")

(_ADD, _DELETE, _INSERT) = range(3)
(_ROOT, _DEPTH, _WIDTH) = range(3)

class Node:

    def __init__(self, name, identifier=None, expanded=True):
        self.__identifier = (str(uuid.uuid1()) if identifier is None else
                sanitize_id(str(identifier)))
        self.name = name
        self.expanded = expanded
        self.__bpointer = None
        self.__fpointer = []

    @property
    def identifier(self):
        return self.__identifier

    @property
    def bpointer(self):
        return self.__bpointer

    @bpointer.setter
    def bpointer(self, value):
        if value is not None:
            self.__bpointer = sanitize_id(value)

    @property
    def fpointer(self):
        return self.__fpointer

    def update_fpointer(self, identifier, mode=_ADD):
        if mode is _ADD:
            self.__fpointer.append(sanitize_id(identifier))
        elif mode is _DELETE:
            self.__fpointer.remove(sanitize_id(identifier))
        elif mode is _INSERT:
            self.__fpointer = [sanitize_id(identifier)]

class Tree:

    def __init__(self):
        self.nodes = []

    def get_index(self, position):
        for index, node in enumerate(self.nodes):
            if node.identifier == position:
                break
        return index

    def create_node(self, name, identifier=None, parent=None):

        node = Node(name, identifier)
        self.nodes.append(node)
        self.__update_fpointer(parent, node.identifier, _ADD)
        node.bpointer = parent
        return node

    def show(self, position, level=_ROOT):
        queue = self[position].fpointer
        if level == _ROOT:
            print("{0} [{1}]".format(self[position].name,
                                     self[position].identifier))
        else:
            print("\t"*level, "{0} [{1}]".format(self[position].name,
                                                 self[position].identifier))
        if self[position].expanded:
            level += 1
            for element in queue:
                self.show(element, level)  # recursive call

    def expand_tree(self, position, mode=_DEPTH):
        # Python generator. Loosly based on an algorithm from 'Essential LISP' by
        # John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241
        yield position
        queue = self[position].fpointer
        while queue:
            yield queue[0]
            expansion = self[queue[0]].fpointer
            if mode is _DEPTH:
                queue = expansion + queue[1:]  # depth-first
            elif mode is _WIDTH:
                queue = queue[1:] + expansion  # width-first

    def is_branch(self, position):
        return self[position].fpointer

    def __update_fpointer(self, position, identifier, mode):
        if position is None:
            return
        else:
            self[position].update_fpointer(identifier, mode)

    def __update_bpointer(self, position, identifier):
        self[position].bpointer = identifier

    def __getitem__(self, key):
        return self.nodes[self.get_index(key)]

    def __setitem__(self, key, item):
        self.nodes[self.get_index(key)] = item

    def __len__(self):
        return len(self.nodes)

    def __contains__(self, identifier):
        return [node.identifier for node in self.nodes
                if node.identifier is identifier]

if __name__ == "__main__":

    tree = Tree()
    tree.create_node("Harry", "harry")  # root node
    tree.create_node("Jane", "jane", parent = "harry")
    tree.create_node("Bill", "bill", parent = "harry")
    tree.create_node("Joe", "joe", parent = "jane")
    tree.create_node("Diane", "diane", parent = "jane")
    tree.create_node("George", "george", parent = "diane")
    tree.create_node("Mary", "mary", parent = "diane")
    tree.create_node("Jill", "jill", parent = "george")
    tree.create_node("Carol", "carol", parent = "jill")
    tree.create_node("Grace", "grace", parent = "bill")
    tree.create_node("Mark", "mark", parent = "jane")

    print("="*80)
    tree.show("harry")
    print("="*80)
    for node in tree.expand_tree("harry", mode=_WIDTH):
        print(node)
    print("="*80)
Brett Kromkamp
fonte
4

Se alguém precisar de uma maneira mais simples de fazer isso, uma árvore será apenas uma lista aninhada recursivamente (já que o conjunto não é lavável):

[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]

Onde cada ramo é um par: [ object, [children] ]
e cada folha é um par:[ object, [] ]

Mas se você precisar de uma classe com métodos, poderá usar anytree.

Hugo Trentesaux
fonte
1

Quais operações você precisa? Geralmente, existe uma boa solução no Python usando um dict ou uma lista com o módulo bisect.

Existem muitas implementações de árvores no PyPI e muitos tipos de árvores são quase triviais para se implementar no Python puro. No entanto, isso raramente é necessário.

Mike Graham
fonte
0

Outra implementação de árvore baseada vagamente na resposta de Bruno :

class Node:
    def __init__(self):
        self.name: str = ''
        self.children: List[Node] = []
        self.parent: Node = self

    def __getitem__(self, i: int) -> 'Node':
        return self.children[i]

    def add_child(self):
        child = Node()
        self.children.append(child)
        child.parent = self
        return child

    def __str__(self) -> str:
        def _get_character(x, left, right) -> str:
            if x < left:
                return '/'
            elif x >= right:
                return '\\'
            else:
                return '|'

        if len(self.children):
            children_lines: Sequence[List[str]] = list(map(lambda child: str(child).split('\n'), self.children))
            widths: Sequence[int] = list(map(lambda child_lines: len(child_lines[0]), children_lines))
            max_height: int = max(map(len, children_lines))
            total_width: int = sum(widths) + len(widths) - 1
            left: int = (total_width - len(self.name) + 1) // 2
            right: int = left + len(self.name)

            return '\n'.join((
                self.name.center(total_width),
                ' '.join(map(lambda width, position: _get_character(position - width // 2, left, right).center(width),
                             widths, accumulate(widths, add))),
                *map(
                    lambda row: ' '.join(map(
                        lambda child_lines: child_lines[row] if row < len(child_lines) else ' ' * len(child_lines[0]),
                        children_lines)),
                    range(max_height))))
        else:
            return self.name

E um exemplo de como usá-lo:

tree = Node()
tree.name = 'Root node'
tree.add_child()
tree[0].name = 'Child node 0'
tree.add_child()
tree[1].name = 'Child node 1'
tree.add_child()
tree[2].name = 'Child node 2'
tree[1].add_child()
tree[1][0].name = 'Grandchild 1.0'
tree[2].add_child()
tree[2][0].name = 'Grandchild 2.0'
tree[2].add_child()
tree[2][1].name = 'Grandchild 2.1'
print(tree)

Qual deve ser a saída:

                        Nó raiz                        
     / / \              
Nó filho 0 Nó filho 1 Nó filho 2        
                   | / \       
             Neto 1.0 Neto 2.0 Neto 2.1
Solomon Ucko
fonte
0

Eu sugiro a biblioteca networkx .

NetworkX é um pacote Python para a criação, manipulação e estudo da estrutura, dinâmica e funções de redes complexas.

Um exemplo de construção de uma árvore:

import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('B', 'D')
G.add_edge('A', 'E')
G.add_edge('E', 'F')

Não sei ao certo o que você quer dizer com " Árvore Geral ",
mas a biblioteca permite que cada nó seja um objeto hashável , e não há restrição no número de filhos de cada nó.

A biblioteca também fornece algoritmos gráficos relacionados a árvores e recursos de visualização .

Gal Avineri
fonte
-2

Se você deseja criar uma estrutura de dados em árvore, primeiro é necessário criar o objeto treeElement. Se você criar o objeto treeElement, poderá decidir como sua árvore se comporta.

Para fazer isso a seguir é a classe TreeElement:

class TreeElement (object):

def __init__(self):
    self.elementName = None
    self.element = []
    self.previous = None
    self.elementScore = None
    self.elementParent = None
    self.elementPath = []
    self.treeLevel = 0

def goto(self, data):
    for child in range(0, len(self.element)):
        if (self.element[child].elementName == data):
            return self.element[child]

def add(self):

    single_element = TreeElement()
    single_element.elementName = self.elementName
    single_element.previous = self.elementParent
    single_element.elementScore = self.elementScore
    single_element.elementPath = self.elementPath
    single_element.treeLevel = self.treeLevel

    self.element.append(single_element)

    return single_element

Agora, precisamos usar esse elemento para criar a árvore. Estou usando a árvore A * neste exemplo.

class AStarAgent(Agent):
# Initialization Function: Called one time when the game starts
def registerInitialState(self, state):
    return;

# GetAction Function: Called with every frame
def getAction(self, state):

    # Sorting function for the queue
    def sortByHeuristic(each_element):

        if each_element.elementScore:
            individual_score = each_element.elementScore[0][0] + each_element.treeLevel
        else:
            individual_score = admissibleHeuristic(each_element)

        return individual_score

    # check the game is over or not
    if state.isWin():
        print('Job is done')
        return Directions.STOP
    elif state.isLose():
        print('you lost')
        return Directions.STOP

    # Create empty list for the next states
    astar_queue = []
    astar_leaf_queue = []
    astar_tree_level = 0
    parent_tree_level = 0

    # Create Tree from the give node element
    astar_tree = TreeElement()
    astar_tree.elementName = state
    astar_tree.treeLevel = astar_tree_level
    astar_tree = astar_tree.add()

    # Add first element into the queue
    astar_queue.append(astar_tree)

    # Traverse all the elements of the queue
    while astar_queue:

        # Sort the element from the queue
        if len(astar_queue) > 1:
            astar_queue.sort(key=lambda x: sortByHeuristic(x))

        # Get the first node from the queue
        astar_child_object = astar_queue.pop(0)
        astar_child_state = astar_child_object.elementName

        # get all legal actions for the current node
        current_actions = astar_child_state.getLegalPacmanActions()

        if current_actions:

            # get all the successor state for these actions
            for action in current_actions:

                # Get the successor of the current node
                next_state = astar_child_state.generatePacmanSuccessor(action)

                if next_state:

                    # evaluate the successor states using scoreEvaluation heuristic
                    element_scored = [(admissibleHeuristic(next_state), action)]

                    # Increase the level for the child
                    parent_tree_level = astar_tree.goto(astar_child_state)
                    if parent_tree_level:
                        astar_tree_level = parent_tree_level.treeLevel + 1
                    else:
                        astar_tree_level += 1

                    # create tree for the finding the data
                    astar_tree.elementName = next_state
                    astar_tree.elementParent = astar_child_state
                    astar_tree.elementScore = element_scored
                    astar_tree.elementPath.append(astar_child_state)
                    astar_tree.treeLevel = astar_tree_level
                    astar_object = astar_tree.add()

                    # If the state exists then add that to the queue
                    astar_queue.append(astar_object)

                else:
                    # Update the value leaf into the queue
                    astar_leaf_state = astar_tree.goto(astar_child_state)
                    astar_leaf_queue.append(astar_leaf_state)

Você pode adicionar / remover qualquer elemento do objeto, mas tornar a estrutura intacta.

MAULIK MODI
fonte
-4
def iterative_bfs(graph, start):
    '''iterative breadth first search from start'''
    bfs_tree = {start: {"parents":[], "children":[], "level":0}}
    q = [start]
    while q:
        current = q.pop(0)
        for v in graph[current]:
            if not v in bfs_tree:
                bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1}
                bfs_tree[current]["children"].append(v)
                q.append(v)
            else:
                if bfs_tree[v]["level"] > bfs_tree[current]["level"]:
                    bfs_tree[current]["children"].append(v)
                    bfs_tree[v]["parents"].append(current)
Gagan Nirmal
fonte
Isso não parece responder à pergunta de maneira legível.
AlBlue