Python二叉树的实现


什么是二叉树?

二叉树是由n(n>=0)个结点组成的有限集合,每个结点最多有两个子树的有序树。它或是空集,或者是由一根和称为左,右子树的两个不相交的二叉树组成。
在这里插入图片描述

嵌套列表实现一个二叉树

嵌套列表画出上图所示的二叉树

开局直接用列表,一顿操作猛如虎

myTree=['a',#根节点
    ['b',#左子树
       ['d',[],[]],
       ['e',[],[]]
    ],
    ['c',#右子树
        ['f',[],[]],
        []
    ]
       ]
print("root=",myTree[0])
print("left_subtree=",myTree[1])
print("right_subtree=",myTree[2])

在这里插入图片描述

将上述操作分解,进行封装函数

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', [], []], []]]

二叉树的遍历

二叉树的遍历分为三种:

先序遍历:
• 若二叉树为空,则空操作;
• 否则:
访问根结点 v; • 先序遍历左子树 L; • 先序遍历右子树 R。
上图先序遍历结果:abdecf

算法实现:
1.先序遍历的递归实现:

def pretree(tree):
    if tree != []:
        print(tree[0], end='') # 对根的访问
        preorder(tree[1]) # 对左子树的访问 
        preorder(tree[2]) # 对右子树的访问

2.中序遍历
• 若二叉树为空,则空操作;
• 否则:
• 中序遍历左子树L; • 访问根结点 v; • 中序遍历右子树 R。
上图中序遍历结果:dbeafc

算法实现:

def Inorder(tree):
    if tree != []:
        Inorder(tree[1]) # 访问左子树
        print(tree[0], end='') # 对根的访问
        Inorder(tree[2]) # 访问右子树

3.后序遍历:
• 若二叉树为空,则空操作;
• 否则:
• 后序遍历左子树 L; • 后序遍历右子树 R; • 访问根结点 v。
上图后序遍历结果:debfca

算法实现:

def postorder(tree):
    if tree != []:
        postorder(tree[1]) # 对左子树的访问
        postorder(tree[2]) # 对右子树的访问
        print(tree[0], end='') # 对根的访问