PythonMOOC算法二叉樹

二叉樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合、每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。它或者是空集，或者是由一個(gè)根和稱為左、右子樹的兩個(gè)不相交的二叉樹組成。

使用嵌套列表實(shí)現(xiàn)一個(gè)二叉樹

image.png

# -*- coding: utf-8-*-
def BinaryTree(r):
    return [r, [], []]


def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:  # 左子結(jié)點(diǎn)的列表不為空
        root.insert(1, [newBranch, t, []])
    else:  # 左子結(jié)點(diǎn)的列表為空
        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='')

#定義一個(gè)二叉樹
tree=['a',#根節(jié)點(diǎn)
      ['b',#左子樹
        ['d',[],[]],
        ['e',[],[]],],
      ['c',#右子樹
        ['f',[],[]],
        []]
      ]
preorder(tree)
print()
inorder(tree)
print()
postorder(tree)

計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)

image.png

算法思路：

1. 當(dāng)樹為空時(shí)，結(jié)點(diǎn)個(gè)數(shù)為0
2. 否則，結(jié)點(diǎn)總數(shù)=根節(jié)點(diǎn)個(gè)數(shù)+左子樹結(jié)
   點(diǎn)個(gè)數(shù)+右子樹結(jié)點(diǎn)

# -*- coding: utf-8-*-
#計(jì)算結(jié)點(diǎn)個(gè)數(shù)
def count(root):
    if root==[]:
        return 0
    else:
        n1=count(root[1])
        n2 = count(root[2])
        return 1+n1+n2

#定義一個(gè)二叉樹
tree=['a',#根節(jié)點(diǎn)
      ['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)


# 定義一個(gè)二叉樹
mytree = [30,
          [15,
           [12, [], []],
           [23, [], []],
           ],
          [52,
           [],
           [74, [], [], ]
           ]
          ]
num=int(input('請(qǐng)輸入想查找的數(shù)：'))
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('輸入想插入的數(shù)：'))
insert1(mytree,num)
print(mytree)

二叉樹的刪除

考慮情況復(fù)雜一些，因?yàn)闀?huì)破壞原有結(jié)構(gòu)

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('請(qǐng)輸入想刪除的數(shù)：'))
result=delete(mytree,num)
if result==False:
    print('不存在要?jiǎng)h除的數(shù)！')
else:
    print('刪除后：',mytree)

二叉樹很靈活，運(yùn)用廣泛。