python - 树转二叉树

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


class BT:
    def __init__(self):
        self.root = None

    def _pre_order_(self, n):
        if n:
            print(n.x, end=‘ ‘)
            self._pre_order_(n.left)
            self._pre_order_(n.right)

    def _in_order_(self, n):
        if n:
            self._in_order_(n.left)
            print(n.x, end=‘ ‘)
            self._in_order_(n.right)

    def _post_order_(self, n):
        if n:
            self._post_order_(n.left)
            self._post_order_(n.right)
            print(n.x, end=‘ ‘)

    def build_tree(self, tree: dict):
        for k in tree:
            if not self.root:
                self.root = Node(k)
            n = self.root
            q = [n.left, n.right]
            while q:
                if n and n.x == k:
                    break
                n = q.pop(0)
                if n:
                    q.append(n.left)
                    q.append(n.right)
            for i, v in enumerate(tree[k]):
                if i == 0:
                    n.left = Node(v)
                    n = n.left
                else:
                    n.right = Node(v)
                    n = n.right

    def pre_order(self):
        self._pre_order_(self.root)

    def in_order(self):
        self._in_order_(self.root)

    def post_order(self):
        self._post_order_(self.root)


a = [(‘a‘, ‘b‘), (‘a‘, ‘c‘), (‘a‘, ‘d‘), (‘b‘, ‘e‘), (‘c‘, ‘f‘), (‘c‘, ‘g‘), (‘f‘, ‘h‘)]
k = {}
for _ in a:
    if _[0] not in k:
        k[_[0]] = []
    k[_[0]].append(_[1])

t = BT()
t.build_tree(k)
print(‘先序遍历结果：‘)
t.pre_order()
print()
print(‘中序遍历结果：‘)
t.in_order()
print()
print(‘后序遍历结果：‘)
t.post_order()

先序遍历结果：
a b e c f h g d
中序遍历结果：
e b h f g c d a
后序遍历结果：
e h g f d c b a