第七节--树形结构及其算法

第七节–树形结构及其算法

树形结构是一种应用相当广泛的非线性结构。树状算法在程序中的建立与应用大多使用链表来处理，当然也可以使用数组这样的连续内存来表示二叉树

由于二叉树的应用相当广泛，因此衍生了许多特殊的二叉树结构
1.满二叉树(fully binary tree)
如果二叉树的高度为h，树的节点数为2-1，h>=0,就称此树为"满二叉树"

2.完全二叉树(complete binary tree)
如果二叉树的高速为h，所含的节点数小于2-1，但其节点的编号方式如同高度为h的满二叉树一样，从左到右，从上到下的顺序一一对应

对于完全二叉树而言，假设有N个节点，那么此二叉树的层数h为log(N+1)

3.斜二叉树(skewed binary tree)
当一个二叉树完全没有左节点或右节点时，就称为左斜二叉树或右斜二叉树

4.严格二叉树(strictly binary tree)
二叉树中的每一个非终端节点均有非空的左右子树

一.数组实现二叉树

使用有序的一位数组来表示二叉树，首先可将此二叉树假想成一棵满二叉树，而且第K层具有2个节点，按序存放在一维数组中

首先来看看使用一维数组建立二叉树的表示方法以及数组索引值的设置

索引值	1	2	3	4	5	6	7
内容值	A	B			C		D

一维数组中的索引值有以下关系：

1. 左子树索引值是父节点索引值乘2
2. 右子树索引值是父节点索引值乘2加1

二叉查找树具有以下特点：

1. 可以是空集合，若不是空集合，则节点上一定要有一个键值
2. 每一个树根的值需大于左子树的值
3. 每一个树根的值需小于右子树的值
4. 左右子树也是二叉查找树
5. 树的每个节点值都不相同

1.例子说明

现在示范用一组数据(32,25,16,35,27)来建立一棵二叉查找树，具体过程如下

2.程序说明

按序输入一棵二叉树节点的数据，分别是0,6,3,5,4,7,8,2，并建立一棵二叉查找树，最后输出存储此二叉树的一维数组
2.1源程序

def Btree_create(btree,data,length):
    for i in range(1,length):
        level=1
        while btree[level]!=0:
            if data[i]>btree[level]: #如果数组内的值大于树根，则往右子树比较
                level=level*2+1
            else:               #如果数组内的值小于或等于树根，则往左子树比较
                level=level*2
        btree[level]=data[i]    #把数组值放入二叉树
        
length=9
data=[0,6,3,5,4,7,8,9,2]  #原始数组
btree=[0]*16  #存放二叉树数组
print('原始数组内容：')
for i in range(length):
    print('[%2d] ' %data[i],end='')
print('')
Btree_create(btree,data,9)
print('二叉树内容：')
for i in range(1,16):
    print('[%2d] ' %btree[i],end='')
print()

2.2运行结果

原始数组内容：
[ 0] [ 6] [ 3] [ 5] [ 4] [ 7] [ 8] [ 9] [ 2] 
二叉树内容：
[ 6] [ 3] [ 7] [ 2] [ 5] [ 0] [ 8] [ 0] [ 0] [ 4] [ 0] [ 0] [ 0] [ 0] [ 9] 

二.链表实现二叉树

链表实现二叉树，就是使用功能链表来存储二叉树。使用链表来表示二叉树的好处是对于节点的增加与删除相当容易，缺点是很难找到父节点，除非在每一节点多增加一个父字段

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None

链表实现二叉树的示意图：

以链表方式建立二叉树的python算法：

def create_tree(root,val):    #建立二叉树的函数
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

1.程序说明

1.1功能要求
按序输入一棵二叉树10个节点的数据，分别是5,6,24,8,12,3,17,1,9，并使用链表来建立二叉树。最后输出左，右子树

1.2源程序

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None

def create_tree(root,val):    #建立二叉树的函数
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

data=[5,6,24,8,12,3,17,1,9]
ptr=None
root=None
for i in range(9):
    ptr=create_tree(ptr,data[i]) #建立二叉树
print('左子树:')
root=ptr.left
while root!=None:
    print('%d' %root.data)
    root=root.left
print('--------------------------------')
print('右子树:')
root=ptr.right
while root!=None:
    print('%d' %root.data)
    root=root.right
print()

1.2运行结果

左子树:
3
1
--------------------------------
右子树:
6
24

三.二叉树遍历

所谓二叉树的遍历(Binary Tree Traversal)，最简单的说法就是"访问树中所有的节点各一次"，并且在遍历后，将树中的数据转化为线性关系

简单二叉树节点而言，每个节点都可分为左右两个分支

可以有ABC，ACB，BAC，BCA，CAB，CBA一共6种遍历方法。如果按照二叉树特性，一律从左到右，那么就只剩下三种遍历方式，分别是BAC，ABC，BCA三种。这三种方式的命名与规则如下：

1. 中序遍历(BAC，Inorder)：左子树—>树根—>右子树
2. 前序遍历(ABC，Preorder)：树根—>左子树—>右子树
3. 后序遍历(BCA，Postorder)：左子树—>右子树—>树根

1.中序遍历

中序遍历(Inorder Traversal)是"左中右"的遍历顺序，也就是从树的左侧逐步向下方移动，直到无法移动，再访问此节点，并向右移动一节点。如果无法再向右移动时，可以返回上层的父节点，并重复左，中，右的步骤：

• 遍历左子树
• 遍历(或访问)树根
• 遍历右子树

中序遍历结果：FDHGIBEAC

中序遍历的递归算法如下：

def inorder(ptr):      #中序遍历子程序
    if ptr!=None:
        inorder(ptr.left)
        print('[%2d] ' %ptr.data, end='')
        inorder(ptr.right)

2.后序遍历

后序遍历(Postorder Traversal)是"左右中"的遍历顺序，就是先遍历左子树，在遍历右子树，最后遍历(或访问)根节点。反复执行此步骤：

• 遍历左子树
• 遍历右子树
• 遍历树根

后序遍历结果：FHIGDEBCA

后序遍历的递归算法如下：

def postorder(ptr):      #后序遍历子程序
    if ptr!=None:
        inorder(ptr.left)
        inorder(ptr.right)
        print('[%2d] ' %ptr.data, end='')

3.前序遍历

前序遍历(Preorder Traversal)是"中左右"的遍历顺序，也就是先从根节点遍历，再往左方移动，当无法继续时，继续向右方移动，接着再重复执行此步骤：

• 遍历树根
• 遍历左子树
• 遍历右子树

前序遍历结果：ABDFGHIEC

前序遍历的递归算法：

def preorder(ptr):      #前序遍历子程序
    if ptr!=None:
      	print('[%2d] ' %ptr.data, end='')
        inorder(ptr.left)
        inorder(ptr.right)

4.程序说明

4.1功能要求
按序输入一棵二叉树节点的数据，分别是5,6,24,8,12,3,17,1,9，利用链表来建立二叉树，最后进行中序遍历，轻松完成从小到大的排序

4.2源程序

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None
        
def inorder(ptr):      #中序遍历子程序
    if ptr!=None:
        inorder(ptr.left)
        print('[%2d] ' %ptr.data, end='')
        inorder(ptr.right)

def create_tree(root,val):    #建立二叉树的函数
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

#主程序
data=[5,6,24,8,12,3,17,1,9]
ptr=None
root=None
for i in range(9):
    ptr=create_tree(ptr,data[i])       #建立二叉树
print('====================')
print('排序完成的结果：')
inorder(ptr)   #中序遍历
print('')

4.3运行结果

====================
排序完成的结果：
[ 1] [ 3] [ 5] [ 6] [ 8] [ 9] [12] [17] [24] 

四.二叉树节点的查找

二叉树在建立的过程中，是根据左子树<树根<右子树的原则建立的，因此只需从树根出发比较键值，如果比数根大就往右，否则往左而下，直到相等就找到了要查找的值，如果比到None，无法在前进就代表查找不到此值

二叉树查找的算法：

def search(ptr,val):     #查找二叉树中某个值的子程序
    while True:
        if ptr==None:    #没找到就返回None
            return None
        if ptr.data==val:       #节点值等于查找值
            print('共查找 %3d 次' %i)
            return ptr
        elif ptr.data > val:  #节点值大于查找值
            ptr=ptr.left
        else:
            ptr=ptr.right

1.程序说明

1.1功能要求
建立一个二叉树找树，并输入要查找的值。二叉树节点的数据按序依次为7,1,4,2,8,13,12,11,15,9,5

1.2源程序

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None

def create_tree(root,val):  #建立二叉树的函数
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

def search(ptr,val):     #查找二叉树中某个值的子程序
    i=1
    while True:
        if ptr==None:    #没找到就返回None
            return None
        if ptr.data==val:       #节点值等于查找值
            print('共查找 %3d 次' %i)
            return ptr
        elif ptr.data > val:  #节点值大于查找值
            ptr=ptr.left
        else:
            ptr=ptr.right
        i+=1

#主程序
arr=[7,1,4,2,8,13,12,11,15,9,5]
ptr=None
print('[原始数组内容]')
for i in range(11):
    ptr=create_tree(ptr,arr[i])  #建立二叉树
    print('[%2d] ' %arr[i],end='')
print()
data=int(input('请输入查找值：'))
if search(ptr,data) !=None :    #在二叉树中查找
    print('您要找的值 [%3d] 找到了!!' %data)
else:
    print('您要找的值没找到!!')

1.3运行结果

[原始数组内容]
[ 7] [ 1] [ 4] [ 2] [ 8] [13] [12] [11] [15] [ 9] [ 5] 
请输入查找值：11
共查找   5 次
您要找的值 [ 11] 找到了!!

五.二叉树节点的插入

if search(ptr,data)!=None:      #在二叉树中查找
    print('二叉树中有此节点了!')
else:
    ptr=create_tree(ptr,data)
    inorder(ptr)

一.程序说明

1.功能要求
二叉树的节点数据按序为7,1,4,2,8,13,12,11,15,9，然后输入一个键值，如果不在此二叉树中，就将其加入到二叉树

2.源程序

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None

def create_tree(root,val):  #建立二叉树的函数
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:
            backup.left=newnode
        else:
            backup.right=newnode
    return root

def search(ptr,val):     #在二叉树中查找某个值的子程序
    while True:
        if ptr==None:    #没找到就返回None
            return None
        if ptr.data==val:       #节点值等于查找值
            return ptr
        elif ptr.data > val:    #节点值大于查找值
            ptr=ptr.left
        else:
            ptr=ptr.right

def inorder(ptr):      #中序遍历子程序
    if ptr!=None:
        inorder(ptr.left)
        print('[%2d] ' %ptr.data, end='')
        inorder(ptr.right)

#主程序
arr=[7,1,4,2,8,13,12,11,15,9,5]
ptr=None
print('[原始数组内容]')

for i in range(11):
    ptr=create_tree(ptr,arr[i])  #建立二叉树
    print('[%2d] ' %arr[i],end='')
print()
data=int(input('请输入要查找的键值：'))
if search(ptr,data)!=None:      #在二叉树中查找
    print('二叉树中有此节点了!')
else:
    ptr=create_tree(ptr,data)
    inorder(ptr)

3.运行结果

[原始数组内容]
[ 7] [ 1] [ 4] [ 2] [ 8] [13] [12] [11] [15] [ 9] [ 5] 
请输入要查找的键值：3
[ 1] [ 2] [ 3] [ 4] [ 5] [ 7] [ 8] [ 9] [11] [12] [13] [15] 

六.二叉树节点的删除

二叉树节点的删除操作则稍为复杂，可分为以下三种情况：
1.删除的节点为树叶，只要将其相连的父节点指向None即可
2.删除的节点只有一棵子树。如下图：删除节点1，就将其右指针字段放在父节点的左指针字段

3.删除的节点有两棵子树。如下图：要删除节点4，方式有两种，虽然结果不同，但都可符合二叉树特性

• 找出中序立即先行者(inorder immediate predecessor)，就是将欲删除节点的左子树中最大者向上提，在此即为上图中的节点2。简单来说，就是在该节点的左子树，往右寻找，直到右指针为None，这节点就是中序立即先行者
• 找出中序立即后续者(inorder immediate successor)，就是把要删除节点的右子树中最小者向上提，在此即为上图中的节点5。简单来说，就是在该节点的右子树，往左寻找，直到左指针为None，这个节点就是中序立即后续者

七.堆积树排序法

堆积排序法算是选择排序法的改进版，它可以减少在选择排序法中的比较次数，进而减少排序时间。堆积树是一种特殊的二叉树，可分为最大堆积树和最小堆积树两种。

最大堆积树满足以下3个条件：

• 它是一个完全二叉树
• 所有节点的值都大于或等于它左右子节点的值
• 树根是堆积树中最大的

最小堆积树满足以下3个条件：

• 它是一个完全二叉树
• 所有节点的值都小于或等于它左右子节点的值
• 树根是堆积树中最小的

假设有9项数据32,17,16,24,35,87,65,4,12，以二叉树表示：

如果要将该二叉树转换堆积树(heap tree)，我们可以用数组来存储二叉树所有节点的值，即：

A[0]=32，A[1]=17，A[2]=16，A[3]=24，A[4]=35，A[5]=87

A[6]=65，A[7]=4，A[8]=12

步骤01：A[0]=32为树根，若A[1]大于父节点，则必须互换。此处A[1]=17<A[0]=32故不交换
步骤02：A[2]=16<A[0]，故不交换
步骤03：A[3]=24>A[1]=17，故交换，如下图

步骤04：A[4]=35>A[1]=24，故交换，再与A[0]=32比较，A[1]=35>A[0]=32，故交换，如下图

步骤05：A[5]=87>A[2]=16，故交换，再与A[0]=35比较，A[2]=87>A[0]=35，故交换，如下图

步骤06：A[6]=65>A[2]=35，故交换，且A[2]=65<A[0]=87，故不交换，如下图

步骤07：A[7]=4<A[3]=17，故不交换，A[8]=12<A[3]=17，故不交换

下面将利用堆积排序法对34,19,40,14,57,17,4,43进行排序

• 
  

1.程序说明

1.1功能要求
使用堆积排序法来排序

1.2源程序

def heap(data,size):
    for i in range(int(size/2),0,-1):#建立堆积树节点
        ad_heap(data,i,size-1)
    print()
    print('堆积的内容：',end='')
    for i in range(1,size): #原始堆积树的内容
        print('[%2d] ' %data[i],end='')
    print('\n')
    for i in range(size-2,0,-1): #堆积排序
        data[i+1],data[1]=data[1],data[i+1]#头尾节点交换
        ad_heap(data,1,i)#处理剩余节点
        print('处理过程为：',end='')
        for j in range(1,size):
            print('[%2d] ' %data[j],end='')
        print()

def ad_heap(data,i,size):
    j=2*i
    tmp=data[i]
    post=0
    while j<=size and post==0:
        if j<size:
            if data[j]<data[j+1]: #找出最大节点
                j+=1
        if tmp>=data[j]: #若树根较大，结束比较过程
            post=1
        else:
            data[int(j/2)]=data[j]#若树根较小，则继续比较
            j=2*j
    data[int(j/2)]=tmp #指定树根为父节点

def main():
    data=[0,5,6,4,8,3,2,7,1]	#原始数组的内容
    size=9
    print('原始数组为：',end='')
    for i in range(1,size):
        print('[%2d] ' %data[i],end='')
    heap(data,size) #建立堆积树
    print('排序结果为：',end='')
    for i in range(1,size):
        print('[%2d] ' %data[i],end='')
        
main()

1.3运行结果

原始数组为：[ 5] [ 6] [ 4] [ 8] [ 3] [ 2] [ 7] [ 1] 
堆积的内容：[ 8] [ 6] [ 7] [ 5] [ 3] [ 2] [ 4] [ 1] 

处理过程为：[ 7] [ 6] [ 4] [ 5] [ 3] [ 2] [ 1] [ 8] 
处理过程为：[ 6] [ 5] [ 4] [ 1] [ 3] [ 2] [ 7] [ 8] 
处理过程为：[ 5] [ 3] [ 4] [ 1] [ 2] [ 6] [ 7] [ 8] 
处理过程为：[ 4] [ 3] [ 2] [ 1] [ 5] [ 6] [ 7] [ 8] 
处理过程为：[ 3] [ 1] [ 2] [ 4] [ 5] [ 6] [ 7] [ 8] 
处理过程为：[ 2] [ 1] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] 
处理过程为：[ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] 
排序结果为：[ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8]