Jak mogę zaimplementować drzewo w Pythonie?

Odpowiedzi:

232

kiedykolwiek

Polecam https://pypi.python.org/pypi/anytree (jestem autorem)

Przykład

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'))

cechy

Anyree ma również potężne API z:

  • proste tworzenie drzewa
  • prosta modyfikacja drzewa
  • iteracja drzewa w przedsprzedaży
  • iteracja drzewa po zamówieniu
  • rozwiązać względne i bezwzględne ścieżki węzłów
  • przechodząc od jednego węzła do drugiego.
  • renderowanie drzewa (patrz przykład powyżej)
  • przyłączanie / odłączanie węzłów
c0fec0de
źródło
31
Po prostu najlepsza odpowiedź, inni odkrywają koło.
Ondrej
66
Dobrą formą jest ujawnienie, że jesteś autorem pakietu, który rekomendujesz w swojej odpowiedzi.
John Y,
3
@ c0fec0de Kocham cię !!!! Ta biblioteka jest niesamowita, ma nawet funkcję wizualizacji
Layser
2
@Ondrej dobrze, pozostałe odpowiedzi są mniej zależne, a pierwotne pytanie dotyczyło wbudowanych struktur danych. Chociaż anytreejest to prawdopodobnie świetna biblioteka, jest to pytanie python, a nie pytanie Node.js.
Rob Rose
Natrafiłem na tę odpowiedź przez Google. Ta biblioteka jest naprawdę fajna. Szczególnie podoba mi się możliwość użycia klasy mixin do stworzenia drzewa dowolnego obiektu!
Rÿck Nöthing
104

Python nie ma tak szerokiego zakresu „wbudowanych” struktur danych, jak Java. Ponieważ jednak Python jest dynamiczny, łatwe jest utworzenie ogólnego drzewa. Na przykład drzewem binarnym może być:

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

Możesz użyć tego w następujący sposób:

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"
Greg Hewgill
źródło
109
To tak naprawdę nie tłumaczy wiele na temat tworzenia użytecznej implementacji drzewa.
Mike Graham
14
Pytanie jest otagowane Python3, nie ma więc potrzeby czerpania class Treez obiektu
cfi
3
@ cfi Wyprowadzanie z objectjest czasem tylko wskazówką: jeśli klasa dziedziczy po żadnej innej klasie bazowej, jawnie dziedziczy po obiekcie. Dotyczy to również klas zagnieżdżonych. Zobacz Przewodnik po stylu Python Google
Konrad Reiche,
16
@platzhirsch: Proszę przeczytać i zacytować całą wytyczną: Google wyraźnie podkreśla, że ​​jest to wymagane do działania kodu Python 2 zgodnie z oczekiwaniami i zalecane w celu poprawy zgodności z Py3. Tutaj mówimy o kodzie Py3. Nie ma potrzeby dodatkowego, starszego pisania.
cfi
13
To drzewo binarne, a nie ogólne, o które prosiliśmy.
Michael Dorner
49

Ogólne drzewo to węzeł z zerowym lub większą liczbą potomków, z których każdy jest właściwym (drzewnym) węzłem. To nie to samo co drzewo binarne, są to różne struktury danych, chociaż obie mają pewną terminologię.

W Pythonie nie ma wbudowanej struktury danych dla ogólnych drzew, ale łatwo ją zaimplementować za pomocą klas.

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
źródło
Niesamowite, można go również łatwo wykorzystać jako wykres! Jedyny problem, który widziałem to: Jak mogę odróżnić lewy węzeł od prawego?
Ângelo Polotto
3
Według indeksu dzieci. W takim przypadku zawsze będą dzieci [0].
Freund Allein
38

Możesz spróbować:

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

Jak sugerowano tutaj: https://gist.github.com/2012250

Ib33X
źródło
jeśli chcesz przedłużyć do dowolnej ilości poziomów sprawdzić: stackoverflow.com/a/43237270/511809
natbusa
cienie wbudowanej funkcji skrótu.
Tritium21
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
źródło
3
Czy możesz dodać tylko kilka uwag, aby przedstawić swój kod i swoją implementację?
Michele d'Amico,
Dziękujemy za pełną implementację drzewa binarnego z funkcjami narzędziowymi. Ponieważ jest to Python 2, stworzyłem streszczenie implementacji drzewa binarnego (Py3) dla osób potrzebujących wersji Python 3.
CᴴᴀZ
16

Nie ma wbudowanych drzew, ale można je łatwo zbudować, podklasując typ węzła z listy i pisząc metody przejścia. Jeśli to zrobisz, bisect przyda mi się.

Istnieje również wiele implementacji PyPi , które można przeglądać.

O ile dobrze pamiętam, standardowa biblioteka języka Python nie zawiera struktur danych drzewa z tego samego powodu, którego nie zawiera biblioteka klas podstawowych .NET: lokalizacja pamięci jest zmniejszona, co powoduje więcej braków pamięci podręcznej. W nowoczesnych procesorach zwykle szybsze jest po prostu wprowadzenie dużej ilości pamięci do pamięci podręcznej, a struktury danych „bogate we wskaźnik” negują korzyści.

Justin R.
źródło
2
FYI: Pajęczyny pokryte są nienawiścią do wzmocnienia. Najwyraźniej powinien to być OGROMNY ból, z którym trzeba sobie poradzić, zwłaszcza że wsparcie dla niego zostało przerwane. Polecam więc trzymać się od tego z daleka
inspectorG4dget
Dzięki. Nie miałem żadnych problemów osobiście, ale nie chcę wprowadzać w błąd, więc usunąłem to odniesienie.
Justin R.
11

Zaimplementowałem zrootowane drzewo jako słownik {child:parent}. Na przykład z węzłem głównym 0drzewo może wyglądać tak:

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

Ta struktura bardzo ułatwiła przejście w górę ścieżką od dowolnego węzła do katalogu głównego, co było istotne dla problemu, nad którym pracowałem.

łapa
źródło
1
Właśnie w ten sposób rozważałem zrobienie tego, dopóki nie zobaczyłem odpowiedzi. Chociaż ponieważ drzewo jest rodzicem z dwójką dzieci, a jeśli chcesz zejść, możesz to zrobić {parent:[leftchild,rightchild]}.
JFA
1
Innym sposobem jest użycie list list, w których pierwszym (lub więcej) elementem na liście jest wartość węzła, a kolejne zagnieżdżone dwie listy reprezentują jego lewe i prawe poddrzewa (lub więcej dla drzewa n-ary).
pepr
9

Odpowiedź Grega Hewgilla jest świetna, ale jeśli potrzebujesz więcej węzłów na poziom, możesz użyć listy | słownika, aby je utworzyć: A następnie użyj metody, aby uzyskać do nich dostęp według nazwy lub kolejności (np. 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

Teraz po prostu utwórz root i zbuduj: 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

To powinno wystarczyć, abyś zaczął zastanawiać się, jak to zrobić

Bruno
źródło
W tej odpowiedzi brakuje czegoś, próbowałem tego rozwiązania przez ostatnie 2 dni i myślę, że masz pewien logiczny przepływ w metodzie dodawania obiektów. Prześlę odpowiedź na to pytanie, sprawdź to i daj mi znać, czy mogę pomóc.
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

działa jako słownik, ale zapewnia tyle zagnieżdżonych nagrań, ile chcesz. Spróbuj wykonać następujące czynności:

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']            = '*'

dostarczy zagnieżdżony dykt ... który rzeczywiście działa jak drzewo.

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

... Jeśli masz już dyktandę, każdy poziom zostanie rzucony na drzewo:

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

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

W ten sposób możesz edytować / dodawać / usuwać każdy poziom nagrania według własnego uznania. Nadal obowiązują wszystkie metody dyktowania dla przechodzenia itp.

natbusa
źródło
2
Czy istnieje powód, dla którego zdecydowałeś się na przedłużenie dictzamiast defaultdict? Z moich testów rozszerzenie defaultdictzamiast dict, a następnie dodanie self.default_factory = type(self)do początku init powinno działać w ten sam sposób.
Rob Rose
prawdopodobnie coś tu brakuje, jak poruszać się po tej strukturze? przejście od dzieci do rodziców lub rodzeństwa wydaje się bardzo trudne
Stormsson,
6

Zaimplementowałem drzewa za pomocą zagnieżdżonych nagrań. Jest to dość łatwe i działa dla mnie z dość dużymi zestawami danych. Poniżej zamieściłem próbkę, a więcej można zobaczyć w kodzie 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
źródło
5

Na mojej stronie opublikowałem implementację drzewa Python [3]: http://www.quesucede.com/page/show/id/python_3_tree_implementation .

Mam nadzieję, że to się przyda

Ok, oto kod:

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
źródło
4

Jeśli ktoś potrzebuje prostszego sposobu, aby to zrobić, drzewo jest tylko rekurencyjnie zagnieżdżoną listą (ponieważ zestaw nie jest mieszalny):

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

Gdzie każda gałąź jest parą: [ object, [children] ]
a każdy liść jest parą:[ object, [] ]

Ale jeśli potrzebujesz zajęć z metodami, możesz użyć dowolnego.

Hugo Trentesaux
źródło
1

Jakie operacje potrzebujesz? Często istnieje dobre rozwiązanie w Pythonie za pomocą dykta lub listy z modułem bisect.

Istnieje wiele, wiele implementacji drzew w PyPI , a wiele typów drzew jest prawie trywialnych do implementacji w czystym Pythonie. Jest to jednak rzadko konieczne.

Mike Graham
źródło
0

Kolejna implementacja drzewa luźno oparta na odpowiedzi 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

I przykład, jak go używać:

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)

Które powinny generować:

                        Węzeł główny                        
     / / \              
Węzeł potomny 0 Węzeł potomny 1 Węzeł potomny 2        
                   | / \       
             Wnuk 1.0 Wnuk 2.0 Wnuk 2.1
Solomon Ucko
źródło
0

Sugeruję bibliotekę Networkx .

NetworkX to pakiet Pythona do tworzenia, manipulacji i badania struktury, dynamiki i funkcji złożonych sieci.

Przykład budowy drzewa:

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')

Nie jestem pewien, co rozumiesz przez „ drzewo ogólne ”,
ale biblioteka pozwala, aby każdy węzeł był dowolnym obiektem , który można mieszać , i nie ma ograniczeń co do liczby dzieci, które ma każdy węzeł.

Biblioteka zawiera również algorytmy graficzne związane z drzewami i wizualizacją możliwościami .

Gal Avineri
źródło
-2

Jeśli chcesz utworzyć strukturę danych drzewa, najpierw musisz utworzyć obiekt treeElement. Jeśli utworzysz obiekt treeElement, możesz zdecydować, jak zachowa się twoje drzewo.

Aby to zrobić, należy wykonać klasę 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

Teraz musimy użyć tego elementu do stworzenia drzewa, używam drzewa A * w tym przykładzie.

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)

Możesz dodawać / usuwać dowolne elementy z obiektu, ale sprawić, że struktura będzie nienaruszona.

MAULIK MODI
źródło
-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
źródło
Wydaje się, że wcale nie odpowiada to na pytanie w czytelny sposób.
AlBlue