BFS in python van een preorder en inorder

(Python 2.7) Ik moet de bfs van een binaire boom afdrukken met een bepaalde preorder en inorder en een maximumlengte van de volgorde- en volgorde van de reeksen. Ik weet hoe het werkt, bijvoorbeeld: preorder: ABCDE inorder: CBDAE maximale lengte: 5

                A
            /    \
           B        E
         /\         
         C   D

BFS: ABECD

Tot nu toe heb ik dit uitgezocht

class BinaryTree:
    def __init__ (self, value, parent=None):
            self.parent = parent
            self.left_child = None
            self.right_child = None
            self.value=value

    def setLeftChild(self, child=None):
            self.left_child = child
            if child:
                child.parent = self

    def setRightChild(self, child=None):
            self.right_child = child
            if child:
                child.parent = self


preorder={}
inorder={}

print "max string length?"
i=int(raw_input())
count=0
while i>count:
    print"insert the preorder"
    preorder[raw_input()]=count
    count=count+1
print "preorder is",sorted(preorder, key=preorder.get)

count2=0
while i>count2:
    print"insert the inorder"
    inorder[raw_input()]=count2
    count2=count2+1
print "inorder is",sorted(inorder, key=inorder.get)
root=

Ik heb ontdekt hoe ik een binaire boom in python kan maken, maar het punt is dat ik niet weet hoe ik de waarden van de volgende childs moet toevoegen. Zoals je kunt zien heb ik al de root en ben ik erachter gekomen hoe ik de eerste childs (links en rechts) kan invoegen, maar ik weet niet hoe ik de volgende moet toevoegen.

3

3 antwoord

Ik denk dat in wezen de vraag is hoe alle parent-leftChild-paren en parent-rightChild-paren van de boom uit de opgegeven preorder en volgorde

Om de parent-leftChild-paren te krijgen, moet je het volgende controleren: 1) als node1 gelijk is na node2 in preorder; 2) als node2 vóór in node1 staat

Voor uw voorbeeldvoorbestelling: ABCDE in bestelling: CBDAE

  • B staat na A in de preorder en B staat voor A in volgorde, dus B is het linker kind van A.

  • D heeft gelijk na C in preorder, maar D staat ook na C in volgorde, dus D is niet het linker kind van C

U kunt de vergelijkbare truc gebruiken om alle parent-rightChild-paren te krijgen

2
toegevoegd
@ TomásMedina Ja, en je moet alle paren zoals A-B, B-C, C-D ... in de preorderlijst krijgen en ze valideren in de inorderlijst. Het maakt dus niet uit hoe lang de preorderlijsten zijn, je moet er toch doorheen gaan
toegevoegd de auteur xvatar, de bron
@ TomásMedina Ik bedoel voor A en B op de preorderlijst, je checkt ze op de inorderlijst om te zien of B eerder verschijnt dan A, zo ja, dan betekent dit dat B het linker kind is van A. Je doet dezelfde cheque voor de andere paren op de preorderlijst, die B en C, C en D, D en E zijn. Sorry als het woord 'paar' je verwart, maar ik hoop dat je begrijpt wat ik bedoel.
toegevoegd de auteur xvatar, de bron
Dus ik zou een "als" moeten doen, bijvoorbeeld om te bepalen waar het knooppunt naartoe gaat op basis van de preorder en inorder invoer die ik heb gekregen? het ding is dat de preorder en inorderlengte groter dan 5 kan zijn en dat is waar ik een beetje in de war raak. Bedankt voor je hulp.
toegevoegd de auteur TomMe, de bron
Ok, het ziet ernaar uit dat ik op de goede weg ben, maar wat bedoel je met het krijgen van alle paren? Ik begreep dat deel niet. Ik zat te denken in het vergelijken van de positie van de elementen tussen de twee lijsten en daaruit te bepalen waar ze naartoe gaan. Is dit ok of denk je dat er een meer eenvoudige of efficiënte manier is om het te doen?
toegevoegd de auteur TomMe, de bron
Oh, dat was precies wat ik wilde doen, het leek erop dat we allebei hetzelfde praatten, maar op een andere manier. Maar hoe kan ik de posities tussen de twee lijsten vergelijken? Heel erg bedankt voor je hulp man.
toegevoegd de auteur TomMe, de bron
Ik heb net de code bewerkt, nu gebruik ik een woordenboek, omdat ik heb ontdekt dat het gemakkelijker te gebruiken is, omdat het me al waarden voor elke positie geeft
toegevoegd de auteur TomMe, de bron

Als u kinderen aan een knooppunt wilt toevoegen, haalt u het knooppunt waaraan u kinderen wilt toevoegen en roept u setLeftChild of setRightChild aan.

1
toegevoegd
zoals root.left_child.setLeftChild (BinaryTree (preorder [2]))?
toegevoegd de auteur TomMe, de bron

If you're using BFS - you ideally want to be using a graph - an excellent library is networkx

Een voorbeeld:

import networkx as nx

g = nx.DiGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('B', 'D')

print 'A' + ''.join(node[1] for node in (nx.bfs_edges(g, 'A')))

# ABECD
0
toegevoegd