玩蛇(Python) - 算法：二叉树(Binary tree)

一、二叉树介绍

1.1 什么是二叉树

二叉树(Binary tree)是树形结构的一个重要类型，是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。

二叉树是平衡二叉树，红黑树，二叉堆，大顶堆，小顶堆，多叉树的基础。所以应用场景很广泛，例如：Java中的TreeSet和TreeMap，C++ STL中的set、map，Linux虚拟内存的管理，都是通过红黑树去实现的，以及哈夫曼树编码之类。

1.2术语

• 树（Tree）

由n(n>=0)个结点组成的有限集。n=0时称为空树。在任意一棵非空树中：

有且仅有一个特定的称为根（Root）的结点；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

当n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。

当m>0时，子树的个数没有限制，但它们一定是互不相交的。

• 节点

结点是数据结构中的基础，是构成复杂数据结构的基本组成单位。

在二叉树中的第i层，最多由2^(i-1)的节点。

如果深度由K，那么整个树最多有2^k - 1个节点。

• 结点的度

结点拥有的子树数目称为结点的度。

• 结点关系

结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。 同一个双亲结点的孩子结点之间互称兄弟结点。

• 结点层次

从根开始定义起，根为第一层，根的孩子为第二层，以此类推。

• 树的深度

树中结点的最大层次数称为树的深度或高度。 如图树的深度为4。

二、二叉树实例 - 导航装置数量计算

2.1需求：导航装置数量计算

1) 在秋日市集景区共有N个景点，景点编号为1~N。景点内设有N−1 条双向道路，使所有景点形成了一个 二叉树结构 ，根结点记为 root，景点编号即为节点值。

2) 由于秋日市集景区的结构特殊，游客很容易迷路，主办方决定在景区的若干个景点设置导航装置，按照所在景点编号升序排列后定义装置编号为 1 ~ M。

导航装置向游客发送数据，数据内容为列表 [游客与装置 1 的相对距离,游客与装置 2 的相对距离,...,游客与装置 M 的相对距离]。

3) 由于游客根据导航装置发送的信息来确认位置，因此主办方需保证游客在每个景点接收的数据信息皆不相同。请返回主办方最少需要设置多少个导航装置。

4) 示例：

输入：root = [1,2,null,3,4]，二叉树层次节点从左到右顺序

输出：2

解释：在景点 1、3 或景点 1、4 或景点 3、4 设置导航装置。

2.2 需求分析设计

树没有环所,以对于每个节点来说最多连接三个节点(父节点、左叶子、右叶子)。

1) 如果只有一个根节点，直接返回1

只有一个点铁定不会迷路，1个导航装置即可。

2) 如果是一条线，也直接返回1

只有一条路，铁定不会迷路，1个导航装置即可

3) 如果有父节点、双子节点，那么就是三叉节点，则需要至少放2个导航装置

因为只有一个节点放置导航装置， 到了岔路口 ， 无法判定方向 是朝第一个路口，还是第2个路口，所以至少需要放2个导航装置。

4) 当有多个三叉节点的时候，保证每个三叉节点仅有2个导航装置

如下图，两个叶子节点新增放置1个导航装置，父节点新增放置一个导航装置，保障3个三叉节点均有2个导航装置。

2.3 根据上面设计，完成代码实现

1) 源码(附详细注释，不再单独解释实现逻辑)

from collections import deque
#节点
class TreeNode(object):
  def __init__(self, value):
    self.val = value
    self.left = None
    self.right = None
 
#二叉树，用于使用List生成二叉树
class GenerateBinaryTreeByList(object):  
  def __init__(self, tree_list:list[int]):
    #定义树根
    self.tree_root = None|TreeNode
    self.generateTreeByList(tree_list)
 
  #输入的list参数，是按照层级从左到右存储
  #这种情况下使用先进先出的队列来保证节点互联顺序即可
  def generateTreeByList(self, tree_list:list[int]):
    #根节点先放入queue
    self.tree_root = TreeNode(tree_list[0])
    father_queue = deque([self.tree_root])
    #算出节点数量，用于后续计算
    tree_list_length = len(tree_list)
    #处理节点从第2个元素开始
    i = 1
    while i < tree_list_length:
      #父节点取出
      node = father_queue.popleft()
      #先处理左子节点
      node.left = TreeNode(tree_list[i]) if tree_list[i] else None
      #如果节点不为空，则放入队列，用于其子节点的计算
      if node.left:
        father_queue.append(node.left)
       
      #右节点处理
      i = i + 1
      if i >= tree_list_length:
        break
      node.right = TreeNode(tree_list[i]) if tree_list[i] else None
      if node.right:
        father_queue.append(node.left)
       
      #下一个节点处理
      i = i + 1
#标志常数
HAVE_LOCATOR = 1
NO_LOCATOR = 0
class NavigationCounter(object):
  def __init__(self, tree_root:TreeNode):
    #用于存储最少防止的导航装置数量
    self.num_of_locator = 0
    #如果是空树，则无需导航装置
    if len(tree_list) == 0:
      return
   
    #通过遍历查询导航装置的数量
    left_locator_flag = self.calculateLocators(tree_root.left)
    right_locator_flag = self.calculateLocators(tree_root.right)
   
    #针对root特殊处理
    #只有根节点，没有子树或节点是一条线，整体则仅需放置1个导航装置
    if left_locator_flag == NO_LOCATOR and right_locator_flag == NO_LOCATOR:
      self.num_of_locator = 1
   
    #针对具备双叶子节点的情况，如果单边有三叉节点，单边是一条线或None，则需增加一个导航装置
    if tree_root.right or tree_root.left:      
      #如果单边有三叉节点，单边是一条线，则需增加一个导航装置
      if (left_locator_flag == NO_LOCATOR and right_locator_flag == HAVE_LOCATOR) \
        or (left_locator_flag == HAVE_LOCATOR and right_locator_flag == NO_LOCATOR):
        self.num_of_locator += 1
   
   
  def calculateLocators(self, sub_tree:TreeNode):
    #如果子树不存在，则无需考虑导航装置，直接返回0
    if not sub_tree:
      return NO_LOCATOR
   
    left_locator_flag = self.calculateLocators(sub_tree.left)
    right_locato_flag = self.calculateLocators(sub_tree.right)
   
    #如果有左右子树（子树非Root节点处理情况），则肯定是三叉节点
    if sub_tree.left and sub_tree.right:
      #左右均没有放导航装置,则增加一个导航装置
      if left_locator_flag == NO_LOCATOR and right_locato_flag == NO_LOCATOR:
        #增加一个导航装置
        self.num_of_locator += 1
        #返回处理结果，已有*位器定**，用于父节点判断是否放置导航装置
        return HAVE_LOCATOR
      #至少有一个节点已经防止了*位器定**
      else:
        return HAVE_LOCATOR
    #仅有左侧节点，反馈子节点的情况(节点是一条线的情况)
    if sub_tree.left:
      return left_locator_flag
    #仅有右节点，反馈子节点的情况(节点是一条线的情况)
    if sub_tree.right:
      return right_locato_flag
    #没有叶子节点，说明当前节点就是叶子节点，则无需考虑导航装置
    else:
      return NO_LOCATOR
if __name__ == '__main__':
  #实例1
  #输入：
  tree_list = [1,2,None,3,4]
  #输出：2
  bTree = GenerateBinaryTreeByList(tree_list)
  print(NavigationCounter(bTree.tree_root).num_of_locator)
 
 
  #实例2
  #输入：
  tree_list = [1,2,3,4]
  #输出：1
  bTree = GenerateBinaryTreeByList(tree_list)
  print(NavigationCounter(bTree.tree_root).num_of_locator)

2) 验证(生成树，定位装置计算节点)

PS D:\Shangouxuehui_Git\PythonAlgorithm-main> & D:/Python312/python*ex.e** d:/Shangouxuehui_Git/PythonAlgorithm-main/sgxh_binary_tree.py
2
1

##山狗学会 License Start##

转载请注明出处，"*今条头日**"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元

主页链接：山狗学会主页

##山狗学会 License End##