Ich weiß, dass Sie einen binären Baum rekonstruieren können, wenn Sie seine Inorder- und Preorder-Traversals als Strings angeben, aber ist es möglich, die Postorder- und/oder Preoder-Traversierungen nur zu finden angesichts der inorder traversal?Finden der anderen zwei Durchläufe eines binären Baums, wenn nur eine Durchquerung gegeben wird
Nein, das Abrufen von Postorder/Preorder von nur Inorder Traversal ist nicht möglich. Wenn dies der Fall wäre, wäre es möglich, einen binären Baum mit nur dem Inorder-Traversal zu rekonstruieren, was nicht möglich ist, weil ein Inorder-Traversal Ihnen mehrere mögliche rekonstruierte Binärbäume geben kann.
Wie sieht Ihre Eingabe aus und wozu dient der Baum?
Wenn Sie einen vollständig in Klammern stehenden Ausdruck haben, dann haben Sie einen unique Baum, und Sie erhalten Pre- und Post-order, indem Sie den Baum konstruieren und dann die Terme vor und nach der Bestellung aus dem Baum konstruieren.
Wenn Ihr Ausdruck nicht vollständig in Klammern gesetzt ist, ist dies ein Hinweis darauf, dass zwischen den verschiedenen Bäumen, die Ihrer Reihenfolge entsprechen, kein Unterschied besteht. Wenn z. B. ein Baum arithmetische Ausdrücke darstellt, ist das gleiche wie (x+y)+z und x+(y+z). Dies bedeutet jedoch, es spielt keine Rolle, welche Vor- oder Nachbestellung Sie verwenden, auch ++xyz und +x+yz sind gleich.
Nun, wenn das egal ist, müssen Sie sich nicht um mehrere mögliche Darstellungen Ihrer In-Reihenfolge kümmern. Wählen Sie einfach eine der Darstellungen aus und berechnen Sie dann die von diesem Baum induzierte Vor- und Nachordnung.
Wenn Sie nur die Inorder-Traversierung erhalten, können Sie viele verschiedene Binärbäume konstruieren. Das heißt, Sie können einen "einzigartigen" Baum nicht nur mit "inorder" beschreiben. – Aziz