[小白系列]Python实现逻辑树、遍历树（深度优先以及广度优先），以非计算机专业的角度学习把数组放入二叉树

把数组放入二叉树

给定一个有序整数数组arr，要求：

• 给定数组为有序数组，需要构造出有序二叉树
• 使用中序遍历的方式打印该二叉树
• 使用层序遍历的方式打印该二叉树

1.给定数组为有序数组，需要构造出有序二叉树

1.1 树

• 树一种重要的数据结构
• 基本概念：节点、节点关系、节点层次、树的深度

• 结点：树结构的基础，是构成树的基本组成单位
• 结点关系：A是B、C的父母结点，B、C是A的子结点
• 结点层级：从根开始定义起，根为第一层，根的孩子为第二层，以此类推
• 树的深度：树中结点的最大层次数称为树的深度或高度

1.2 二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5zwHlxHx-1586513283395)(attachment:binary_tree.jpg)]

• 每个结点最多有两颗子树
• 左子树和右子树是有顺序的，次序不能任意颠倒
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

1.3把数组放入二叉树

• 取数组中间元素作为根结点，将数组分为左右两部分
• 对数组左右两部分用递归方法分别构建左右子树
• 递归算法

class BiNode:
    def __init__(self):
        self.data = None   #结点数据
        self.lchild = None #左子树结点
        self.rchild = None #右子树结点

#将有序数组转换为二叉树
def array_to_tree(arr, start, end):
    """将有序数组转换成二叉树
        arr：有序数组
        start：数组起点索引
        end：数组结尾索引
        """
    root = None  #初始化根结点数据
    if end >= start:
        root = BiNode() #创建树实例
        mid = (start + end + 1)//2  #取中点数据索引
        root.data = arr[mid] #树的根结点诶数组中间元素
        root.lchild = array_to_tree(arr, start, mid - 1)  #使用递归方式用左半部分数组构建root的左子树
        root.rchild = array_to_tree(arr, mid+1, end) #使用递归方式用右半部分数组构建root的右子树
    else:
        root = None
    return root

结果图示

1.4使用中序遍历的方式打印二叉树

• 中序遍历：按照左子树->根节点->右子树的顺序访问 （一种深度优先遍历）

#使用中序遍历的方式打印二叉树
def print_tree_midorder(root):
    """使用中序遍历的方式打印二叉树内容
        root：二叉树根结点
    """
    if root == None: #判断是否为空
        return
        
    #使用递归方式，遍历root节点的左子树
    if root.lchild != None:
        print_tree_midorder(root.lchild)
            
    #遍历root节点
    print(root.data, end = ' ')
        
    #使用递归方式，遍历root节点右子树
    if root.rchild != None:
        print_tree_midorder(root.rchild)

arr = list(range(1,11))
arr

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

root = array_to_tree(arr, 0, len(arr)-1)

print('树的中序遍历结果为：', end = '')
print_tree_midorder(root)

树的中序遍历结果为：1 2 3 4 5 6 7 8 9 10 

对照树结构产看遍历结果

1.5 使用层序遍历的方式打印二叉树

• 层序遍历：按照层从小到大，同一层从左到右依次遍历（广度优先遍历）
• 在遍历一个结点的同时记录其子节点信息，然后按照这个记录的顺序访问结点数据
• 可以采用队列存储当前遍历到的结点的子节点

#使用层序遍历的方式打印二叉树
from collections import deque  #载入队列结构,deque是双向队列
def print_tree_layer(root):
    """使用层序遍历的方式打印二叉树内容
        root：二叉树根结点
    """
    if root == None:
        return
        
    queue = deque() #创建队列实例
    #树根结点进队列
    queue.append(root)
        
    while len(queue)>0:
        p = queue.popleft() #出队
        #访问当前节点
        print(p.data, end = ' ')
            
        #如果该节点左孩子不为空，则入队列
        if p.lchild != None:
            queue.append(p.lchild)
                
        #如果该节点右孩子不为空，则入队列
        if p.rchild != None:
            queue.append(p.rchild)

arr = list(range(1,11))
arr

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

root = array_to_tree(arr, 0, len(arr)-1)

print('树的层序遍历结果为：', end = '')
print_tree_layer(root)

树的层序遍历结果为：6 3 9 2 5 8 10 1 4 7 

对照树结构产看遍历结果

更多内容请访问：
链接1:
链接2

最后

以上就是包容小熊猫最近收集整理的关于[小白系列]Python实现逻辑树、遍历树（深度优先以及广度优先），以非计算机专业的角度学习把数组放入二叉树的全部内容，更多相关[小白系列]Python实现逻辑树、遍历树（深度优先以及广度优先），以非计算机专业内容请搜索靠谱客的其他文章。