使用列表遍历二叉树

Question

code.py

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

def inOrder(root):
    if root:
        inOrder(root.left)
        print (root.data)
        inOrder(root.right)

def preOrder(root):
    if root:
        print (root.data)
        preOrder(root.left)
        preOrder(root.right)

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print (root.data)

我通过使用类创建Node来实现二叉树遍历。我现在想仅使用一个列表而不使用类来实现二叉树遍历。

树= [1，[2，[4，[]，[]]，[5，[]，[]]]，[3，[]，[]]]

我想知道如何使用此列表来实现它。对我来说太难了。

Answer 1

作为列表的二叉树似乎相当简单。

数据是node/sub_arr[0]，左节点是另一个子数组sub_arr[1]，右节点是sub_arr[2]。

在代码中。我只是将node.left替换为tree[1]，将node.right替换为tree[2]，将data替换为tree[0]。

Tree = [1, [2, [4, [], []], [5, [], []]], [3, [], []]]


def inOrder(tree):
    if tree:
        inOrder(tree[1])  # Left
        print(tree[0])
        inOrder(tree[2])  # Right


def preOrder(tree):
    if tree:
        print(tree[0])
        preOrder(tree[1])  # Left
        preOrder(tree[2])  # Right


def postOrder(tree):
    if tree:
        postOrder(tree[1])  # Left
        postOrder(tree[2])  # Right
        print(tree[0])


print('In order')
inOrder(tree=Tree)
print('Pre Order')
preOrder(tree=Tree)
print('Post Order')
postOrder(tree=Tree)

#Output
In order
4
2
5
1
3
Pre Order
1
2
4
5
3
Post Order
4
5
2
3
1