[python]1991巡視ツリー

👉 1991巡回旅行

[正解コード]

class Node:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

class Tree:
    def __init__(self, root):
        self.root = root
        
    def find_node(self, node, data):
        if node != None:
            if node.data == data: return node
            left_node = self.find_node(node.left, data)
            if left_node: return left_node
            right_node = self.find_node(node.right, data)
            if right_node: return right_node
        return None

    def add_edge(self, data, left, right):
        node = self.find_node(self.root, data)
        if left != '.': node.left = Node(left, None, None)
        if right != '.': node.right = Node(right, None, None)
    
    def preorder(self, node):
        if node != None:
            print(node.data, end='')
            self.preorder(node.left)
            self.preorder(node.right)
    
    def inorder(self, node):
        if node != None:
            self.inorder(node.left)
            print(node.data, end='')
            self.inorder(node.right)
            
    def postorder(self, node):
        if node != None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data, end='')
            
n = int(input())
t = Tree(Node(None, None, None))
for i in range(n):
    node, left, right = input().split()
    if i == 0:
        t.root.data = node
    t.add_edge(node, left, right)
t.preorder(t.root)
print()
t.inorder(t.root)
print()
t.postorder(t.root)

[回答]
データ構造ツリーをクラスとして実装します.
[アプリケーション構造とアルゴリズム]

Tree

✔ Python Dictionary

Python言語ではかなり簡単にツリーを実現できます.

def preorder(N):
    global graph

    if N in graph:
        print(N, end="")
        preorder(graph[N][0])
        preorder(graph[N][1])


def inorder(N):
    global graph

    if N in graph:
        inorder(graph[N][0])
        print(N, end="")
        inorder(graph[N][1])


def postorder(N):
    global graph

    if N in graph:
        postorder(graph[N][0])
        postorder(graph[N][1])
        print(N, end="")


N = int(input())

graph = {}

for _ in range(N):
    p, c1, c2 = input().split()

    graph[p] = [c1, c2]

preorder('A')
print()
inorder('A')
print()
postorder('A')

mandaringitのコードを参照してください.