如何创建将二叉树转换为元组的函数？

Question

我遇到了这个问题，我的任务是将元组转换为二叉树，然后将二叉树转换回元组，return 树和元组。我能够将元组转换为树，但我未能创建一个函数来执行相反的操作。我只是一个尝试学习数据结构的初学者。

此处的 parse_tuple 函数用于解析元组以创建工作正常的二叉树。

请帮我修复我的 tree_to_tuple 功能。任何修复逻辑的见解或技巧都会很棒。

谢谢

#used for creating binary tree
class TreeNode:
    
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#used to parse over the tuple to create a bianry tree
def parse_tuple(data):
    
    if isinstance(data, tuple) and len(data) == 3:
        
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
        
    elif data is None:
        node = None
    
    else:
        node = TreeNode(data)
    
    return node

#doesnt work
def tree_to_tuple(node):
    if isinstance(node, TreeNode) and node.left is not None and node.right is not None:
        node_mid = node.key
        node_left = tree_to_tuple(node.left)
        node_right = tree_to_tuple(node.right)
    
    elif node.left is None:
        node_left = None
        
    else:
        node_right = None
        
    return (node_left, node_mid, node_right)

tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

tree2 = parse_tuple(tree_tuple)

tree_tuple2 = (1, 2, 3)
tree = parse_tuple(tree_tuple2)
print(tree_to_tuple(tree2))

这是我尝试使用 tree_to_tuple

时遇到的错误

文件“main.py”，第 45 行，在 tree_to_tuple return (node_left, node_mid, node_right) UnboundLocalError：赋值前引用的局部变量 'node_left'。

Answer 1

你很接近，但你的测试有点乱。

这是一个补丁：

def tree_to_tuple(node):
    if isinstance(node, TreeNode):

        #  special case if the tree has no left and no right sub-tree
        if node.left is None and node.right is None:
            return node.key

        return (
            tree_to_tuple(node.left),
            node.key,
            tree_to_tuple(node.right)
        )
    raise ValueError('this is not a tree')

tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

tree2 = parse_tuple(tree_tuple)

tree_tuple2 = (1, 2, 3)
tree = parse_tuple(tree_tuple2)
print(tree_to_tuple(tree2))

输出：

((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

Answer 2

Here's a piece of code I have written that works for me.

def tree_to_tuple(node):
    if isinstance(node, TreeNode):

        if node.left is not None and node.right is not None:
            node_mid = node.key
            node_left = tree_to_tuple(node.left)
            node_right = tree_to_tuple(node.right)

            return (node_left, node_mid, node_right)

        elif node.left is None and node.right is None:
            return node.key

        elif node.left is None and node.right is not None:
            node_mid = node.key
            node_right = tree_to_tuple(node.right)
            node_left = None

            return (node_left, node_mid, node_right)

        elif node.left is not None and node.right is None:
            node_mid = node.key
            node_right = None
            node_left = tree_to_tuple(node.left)

            return (node_left, node_mid, node_right)

    else:
        print("It's not a tree")

Answer 3

我会这样做：

def tree_to_tuple(node):
    if isinstance(node, TreeNode):
       return(tree_to_tuple(node.left), node.key, tree_to_tuple(node.right))
    else:return node

Answer 4

# class for creating binary tree (that has key(node), left(node), right(node)) 
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


# instead of linking nodes one by one, we can represent nodes in the form of tuple
# and we can use recursion technique to automate linking process.  
  
def parse_tuple(data):

    # check if the parameter passed is of type tuple and it's length is 3 (left node, key, right node)
    if isinstance(data, tuple) and len(data) == 3:
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    
    # if it is the leaf node(last node) and it is also == None, then assign node = None
    elif data is None:
        node = None
    
    # if it is a leaf node(last node) and not != to None, then assign node = current value
    else:
        node = TreeNode(data)
    
    return node


def tree_to_tuple(node):
    if isinstance(node, TreeNode):
        # check if left and right node are equal to None if so, then it means it has no child nodes
        # and simply just return key node
        if node.left is None and node.right is None:
            return node.key
        
        # use recursion to iterate through each sub tree and get the left , key and right nodes
        return (
            tree_to_tuple(node.left),
            node.key,
            tree_to_tuple(node.right)
        )
    # else simply return node
    else:
        return node

    
tree_tuple = ((1,3,None), 2, ((None, 3, 4), 5, (6, 7, 8)))
tree2 = parse_tuple(tree_tuple)
print(tree_to_tuple(tree2))


Output
 ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

如何创建将二叉树转换为元组的函数？

How do i create a function to convert a binary tree to a tuple?

python

recursion

binary-tree

data-structures