python 用字典构造二叉树

7uzetpgm 于 2023-02-15 发布在 Python

关注(0)|答案(1)|浏览(161)

我有一个节点和它们的子节点的字典，但是我在插入子节点来构造二叉树时遇到了麻烦，我用二叉树来进行前序遍历和中序遍历。
输入：每个密钥对表示：根：（左子级、右子级），并且可以按任意顺序排列{6：（无、无）、10：（2，6）、2：（无、无）、3：（14、无）、8：（10，3）}
输出树
Binary Tree
我希望树是类格式的（例如，root.left将返回10，root.left.right将返回6。但是我的代码没有查找应该是8：（10，3）的根节点并收集所有子节点。我如何增强代码？）

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

   # Compare the new key with the left and right node
   def insert(self, key, vals):
        
        if self.key == None:
           self.key = key
           self.left = vals[0]
           self.right = vals[1]
       
        # else if left is equal to key
        elif self.left == key:
           self.key = key
           self.left = vals[0]
           self.right = vals[1]
        
        # else if right is equal to key 
        elif: 
           self.key = key
           self.left = vals[0]
           self.right = vals[1]

python

来源：https://stackoverflow.com/questions/75442899/construct-binary-tree-using-dictionary

1条答案

按热度按时间

nlejzf6q1#

他们给你的数据结构是一个很好的存储二叉树的方法，没有必要把它转换成对象，你可以有一个Tree对象，然后把这些都作为这个类的方法，但是我不确定这样是否更好。

from collections import defaultdict

tree = {6:(None,None), 10:(2,6), 2:(None,None), 3:(14,None),8:(10,3)}

def find_root(tree):
    nodes = defaultdict(int)
    for k,(l,r) in tree.items():
        if l:
            nodes[l] += 1
        if r:
            nodes[r] += 1
    for k in tree:
        if k not in nodes:
            return k

def pre_traverse(tree,node):
    if not node:
        return
    print(node)
    if not node in tree:
        return
    pre_traverse(tree,tree[node][0])
    pre_traverse(tree,tree[node][1])

def in_traverse(tree,node):
    if not node:
        return
    if not node in tree:
        print(node)
        return
    in_traverse(tree,tree[node][0])
    print(node)
    in_traverse(tree,tree[node][1])

root = find_root(tree)
print("in-order traversal:")
in_traverse(tree,root)
print("pre-order traversal:")
pre_traverse(tree,root)

输出：

in-order traversal:
2
10
6
8
14
3
pre-order traversal:
8
10
2
6
3
14

赞(0）回复(0）举报 2023-02-15

我来回答

python 用字典构造二叉树

1条答案

相关问题

热门标签

最新问答