PythonMOOC算法二叉树

二叉树是由n（n≥0）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。

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

image.png

# -*- coding: utf-8-*-
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]

# -*- coding: utf-8-*-
#二叉树的遍历
可能的三种遍历次序：
先序遍历：vLR
中序遍历：LvR
后序遍历：LRv
#先序遍历
def preorder(tree):
    if tree!=[]:
        print(tree[0],end='')
        preorder(tree[1])
        preorder(tree[2])

#中序遍历
def inorder(tree):
    if tree!=[]:
       inorder(tree[1])
       print(tree[0],end='')
       inorder(tree[2])

#后序遍历
def postorder(tree):
    if tree!=[]:
        postorder(tree[1])
        postorder(tree[2])
        print(tree[0],end='')

#定义一个二叉树
tree=['a',#根节点
      ['b',#左子树
        ['d',[],[]],
        ['e',[],[]],],
      ['c',#右子树
        ['f',[],[]],
        []]
      ]
preorder(tree)
print()
inorder(tree)
print()
postorder(tree)

计算二叉树结点个数

image.png

算法思路：

1. 当树为空时，结点个数为0
2. 否则，结点总数=根节点个数+左子树结
   点个数+右子树结点

# -*- coding: utf-8-*-
#计算结点个数
def count(root):
    if root==[]:
        return 0
    else:
        n1=count(root[1])
        n2 = count(root[2])
        return 1+n1+n2

#定义一个二叉树
tree=['a',#根节点
      ['b',#左子树
        ['d',[],[]],
        ['e',[],[]],],
      ['c',#右子树
        ['f',[],[]],
        []]
      ]
print(count(tree))

递归查找二叉树中的值是否存在

image.png

# -*- coding: utf-8-*-
def searchBintree(tree, num):
    if tree == []:
        return False
    if num == tree[0]:
        return True
    if num < tree[0]:
        return searchBintree(tree[1], num)
    if num > tree[0]:
        return searchBintree(tree[2], num)


# 定义一个二叉树
mytree = [30,
          [15,
           [12, [], []],
           [23, [], []],
           ],
          [52,
           [],
           [74, [], [], ]
           ]
          ]
num=int(input('请输入想查找的数：'))
print(searchBintree(mytree, num))

向二叉排序树中插入元素

image.png

# -*- coding: utf-8-*-
def insert1(tree, num):
    if tree == []:
        tree.extend([num, [], []])
    elif num <= tree[0]:
        insert1(tree[1], num)
    elif num > tree[0]:
        insert1(tree[2], num)


mytree = [30,
          [15,
           [12, [], []],
           [23, [], []],
           ],
          [52,
           [],
           [74, [], [], ]
          ]
          ]
num=int(input('输入想插入的数：'))
insert1(mytree,num)
print(mytree)

二叉树的删除

考虑情况复杂一些，因为会破坏原有结构

image.png
image.png
image.png

# -*- coding: utf-8-*-
def getmax(tree):
    if tree[2]==[]:
        x=tree[0]
        if tree[1]!=[]:
            tree[:]=tree[1]
        else:
            tree.clear()
        return x
    else:
        return getmax(tree[2])

def delete(tree,num):
    if tree==[]:
        return False
    if num<tree[0]:
        return delete(tree[1],num)
    elif num>tree[0]:
        return delete(tree[2],num)
    else:
        if tree[1]==[] or tree[2]==[]:
            tree.clear()
        elif tree[1]==[]:
            tree[:]=tree[1]
        elif tree[2]==[]:
            tree[:]=tree[2]
        else:
            max=getmax(tree[1])
            tree[0]=max
    return True


mytree=[30,
        [15,
         [12,[],[]],
         [23,[],[]],],
        [52,
         [],
         [74,[],[]]]]

num=int(input('请输入想删除的数：'))
result=delete(mytree,num)
if result==False:
    print('不存在要删除的数！')
else:
    print('删除后：',mytree)

二叉树很灵活，运用广泛。