0x01 二叉树的实现

使用嵌套列表实现一个二叉树

# 使用嵌套列表实现二叉树
Tree = ['a',   # root
        ['b',  # left subtree
            ['d', [], []],
            ['e', [], []]
         ],
        ['c',  # right subtree
            ['f', [], []],
            []
         ]
        ]
print('root=',Tree[0])
print('left subtree=',Tree[1])

def BinaryTree(r):
    return [r, [], []]

def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:  # 左子结点的列表不为空
        root.insert(1, [newBranch, t, []])
    else:           # 左子结点的列表为空
        root.insert(1, [newBranch, [], []])
    return root

def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:  # 左子结点的列表不为空
        root.insert(2, [newBranch, [], t])
    else:           # 左子结点的列表为空
        root.insert(2, [newBranch, [], []])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root, newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

tree = BinaryTree('a')
insertLeft(tree, 'b')
insertRight(tree, 'c')
insertLeft(getLeftChild(tree),'d')
insertRight(getLeftChild(tree),'e')
insertLeft(getRightChild(tree),'f')
print(tree)

# ['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]

0x02 二叉树的遍历

0x03 二叉排序树