devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树；二叉树的前序、中序、后序遍历及查找；顺序存储二叉树；线索化二叉树_先序查找二叉树

作者：花生_TL007 | 2024-03-20 16:30:19

赞

踩

先序查找二叉树

数组、链表和树存储方式分析

对于树结构，不论是查找修改还是增加删除，效率都比较高，结合了链表和数组的优点，如以下的二叉树：

1、数组的第一个元素作为第一个节点

2、数组的第二个元素3比7小，放在7的左边

3、数组的第三个元素10比7大，放在7的右边

4、数组的第四个元素1比7小，也比3小，放在3的左边

5、数组的第五个元素5比7小，但比3大，放在3的右边

6、数组的第六个元素9比7大，但比10小，放在10的左边

7、数组的第七个元素12比7大，比10大，放在10的右边

二叉树的前中后序遍历

思路分析

代码实现

  1. # 创建 HeroNode 节点
  2. class HeroNode:
  3.     def __init__(self, no: int, name: str):
  4.         self.no = no
  5.         self.name = name
  6.         self.left = None
  7.         self.right = None
  8.  
  9.     def __str__(self):
  10.         return f"no={self.no}, name={self.name}"
  11.  
  12.     # 前序遍历
  13.     def pre_order(self):
  14.         # 先输出父节点
  15.         print(self, end=' => ')
  16.         # 左子树不为空则递归左子树
  17.         if self.left is not None:
  18.             self.left.pre_order()
  19.         # 右子树不为空则递归右子树
  20.         if self.right is not None:
  21.             self.right.pre_order()
  22.  
  23.     # 中序遍历
  24.     def infix_order(self):
  25.         # 左子树不为空则递归左子树
  26.         if self.left is not None:
  27.             self.left.infix_order()
  28.         # 输出父节点
  29.         print(self, end=' => ')
  30.         # 右子树不为空则递归右子树
  31.         if self.right is not None:
  32.             self.right.infix_order()
  33.  
  34.     # 后序遍历
  35.     def post_order(self):
  36.         # 左子树不为空则递归左子树
  37.         if self.left is not None:
  38.             self.left.post_order()
  39.         # 右子树不为空则递归右子树
  40.         if self.right is not None:
  41.             self.right.post_order()
  42.         # 输出父节点
  43.         print(self, end=' => ')
  44.  
  45.  
  46. # 建立 HeroNode 二叉树
  47. class BinaryTree:
  48.     root: HeroNode = None
  49.  
  50.     # 前序遍历
  51.     def pre_order(self):
  52.         if self.root is not None:
  53.             self.root.pre_order()
  54.         else:
  55.             print("二叉树为空...")
  56.  
  57.     # 前序遍历
  58.     def infix_order(self):
  59.         if self.root is not None:
  60.             self.root.infix_order()
  61.         else:
  62.             print("二叉树为空...")
  63.  
  64.     # 前序遍历
  65.     def post_order(self):
  66.         if self.root is not None:
  67.             self.root.post_order()
  68.         else:
  69.             print("二叉树为空...")
  70.  
  71.  
  72. def test_binary_tree():
  73.     # 手动创建二叉树
  74.     binary_tree = BinaryTree()
  75.     root = HeroNode(1, '宋江')
  76.     node2 = HeroNode(2, '吴用')
  77.     node3 = HeroNode(3, '卢俊义')
  78.     node4 = HeroNode(4, '林冲')
  79.  
  80.     root.left = node2
  81.     root.right = node3
  82.     node3.right = node4
  83.     binary_tree.root = root
  84.  
  85.     # 前序
  86.     print("前序遍历：", end=" ")
  87.     binary_tree.pre_order()
  88.     print()
  89.  
  90.     # 中序
  91.     print("中序遍历：", end=" ")
  92.     binary_tree.infix_order()
  93.     print()
  94.  
  95.     # 后序
  96.     print("后序遍历：", end=" ")
  97.     binary_tree.post_order()
  98.     print()
  99.  
  100.  
  101. test_binary_tree()

二叉树的前中后序查找

思路分析

代码实现

  1. """ 前中后序遍历查找 """
  2. # 创建 HeroNode 节点
  3. class HeroNode:
  4.     def __init__(self, no: int, name: str):
  5.         self.no = no
  6.         self.name = name
  7.         self.left = None
  8.         self.right = None
  9.  
  10.     def __str__(self):
  11.         return f"no={self.no}, name={self.name}"
  12.  
  13.     # 前序遍历查找
  14.     def pre_order_search(self, no: int):
  15.         """
  16.         前序遍历查找某个节点
  17.         :param no: 要查找节点的 id
  18.         :return: 找到的 HeroNode 节点或 None
  19.         """
  20.         print("进入前序遍历...")
  21.         if self.no == no:  # 如果当前节点是，直接返回
  22.             return self
  23.  
  24.         find_node = None
  25.         # 如果左子节点不为空，则向左子节点继续递归查找
  26.         # 找到则返回，找不到则看右子节点
  27.         if self.left is not None:
  28.             find_node = self.left.pre_order_search(no)
  29.  
  30.         if find_node:  # 说明在左子树上找到，直接返回
  31.             return find_node
  32.  
  33.         # 否则判断右子节点，若不为空，向右子树递归查找
  34.         if self.right is not None:
  35.             find_node = self.right.pre_order_search(no)
  36.  
  37.         # 如果右子树找到，则find_node有值，否则find_node为空
  38.         return find_node
  39.  
  40.     # 中序遍历查找
  41.     def infix_order_search(self, no: int):
  42.         """
  43.         中序遍历查找某个节点
  44.         :param no: 要查找节点的 id
  45.         :return: 找到的 HeroNode 节点或 None
  46.         """
  47.         find_node = None
  48.         # 如果左子节点不为空，则向左子节点继续递归查找
  49.         # 找到则返回，找不到则看右子节点
  50.         if self.left is not None:
  51.             find_node = self.left.infix_order_search(no)
  52.  
  53.         if find_node:  # 说明在左子树上找到，直接返回
  54.             return find_node
  55.         print("进入中序遍历...")
  56.         if self.no == no:  # 如果当前节点是，直接返回
  57.             return self
  58.  
  59.         # 否则判断右子节点，若不为空，向右子树递归查找
  60.         if self.right is not None:
  61.             find_node = self.right.infix_order_search(no)
  62.  
  63.         # 如果右子树找到，则find_node有值，否则find_node为空
  64.         return find_node
  65.  
  66.     # 后序遍历查找
  67.     def post_order_search(self, no: int):
  68.         """
  69.         后序遍历查找某个节点
  70.         :param no: 要查找节点的 id
  71.         :return: 找到的 HeroNode 节点或 None
  72.         """
  73.         find_node = None
  74.         # 如果左子节点不为空，则向左子节点继续递归查找
  75.         # 找到则返回，找不到则看右子节点
  76.         if self.left is not None:
  77.             find_node = self.left.post_order_search(no)
  78.  
  79.         if find_node:  # 说明在左子树上找到，直接返回
  80.             return find_node
  81.  
  82.         # 否则判断右子节点，若不为空，向右子树递归查找
  83.         if self.right is not None:
  84.             find_node = self.right.post_order_search(no)
  85.  
  86.         # 如果右子树找到，则find_node有值，否则find_node为空
  87.         if find_node:
  88.             return find_node
  89.         print("进入后序遍历...")
  90.         if self.no == no:  # 如果当前节点是，直接返回
  91.             return self
  92.         return None
  93.  
  94.  
  95. # 建立 HeroNode 二叉树
  96. class BinaryTree:
  97.     root: HeroNode = None
  98.  
  99.     # 前序查找
  100.     def pre_order_search(self, no):
  101.         if self.root is not None:
  102.             return self.root.pre_order_search(no)
  103.         else:
  104.             return None
  105.  
  106.     # 中序查找
  107.     def infix_order_search(self, no):
  108.         if self.root is not None:
  109.             return self.root.infix_order_search(no)
  110.         else:
  111.             return None
  112.  
  113.     # 后序查找
  114.     def post_order_search(self, no):
  115.         if self.root is not None:
  116.             return self.root.post_order_search(no)
  117.         else:
  118.             return None
  119.  
  120.  
  121. def test_binary_tree():
  122.     # 手动创建二叉树
  123.     binary_tree = BinaryTree()
  124.     root = HeroNode(1, '宋江')
  125.     node2 = HeroNode(2, '吴用')
  126.     node3 = HeroNode(3, '卢俊义')
  127.     node4 = HeroNode(4, '林冲')
  128.     node5 = HeroNode(5, "关胜")
  129.  
  130.     root.left = node2
  131.     root.right = node3
  132.     node3.right = node4
  133.     node3.left = node5
  134.     binary_tree.root = root
  135.  
  136.     print("前序遍历查找：")  # 比较了4次（看输出得到的结果）
  137.     res = binary_tree.pre_order_search(5)
  138.     if res:
  139.         print("找到了，节点信息为：", res)
  140.     else:
  141.         print("找不到编号为5的节点")
  142.     print()
  143.  
  144.     print("中序遍历查找：")  # 比较了3次（看输出得到的结果）
  145.     res = binary_tree.infix_order_search(5)
  146.     if res:
  147.         print("找到了，节点信息为：", res)
  148.     else:
  149.         print("找不到编号为5的节点")
  150.     print()
  151.  
  152.     print("后序遍历查找：")  # 比较了2次（看输出得到的结果）
  153.     res = binary_tree.post_order_search(5)
  154.     if res:
  155.         print("找到了，节点信息为：", res)
  156.     else:
  157.         print("找不到编号为5的节点")
  158.  
  159.  
  160. test_binary_tree()

二叉树删除节点

思路分析

代码实现

  1. """ 递归删除二叉树节点 """
  2. # HeroNode 节点
  3. class HeroNode:
  4.     def __init__(self, no: int, name: str):
  5.         self.no = no
  6.         self.name = name
  7.         self.left = None
  8.         self.right = None
  9.  
  10.     def __str__(self):
  11.         return f"no={self.no}, name={self.name}"
  12.  
  13.     # 前序遍历
  14.     def pre_order(self):
  15.         # 先输出父节点
  16.         print(self, end=' => ')
  17.         # 左子树不为空则递归左子树
  18.         if self.left is not None:
  19.             self.left.pre_order()
  20.         # 右子树不为空则递归右子树
  21.         if self.right is not None:
  22.             self.right.pre_order()
  23.  
  24.     def delete_node(self, no: int):
  25.         """
  26.         递归删除节点规则：
  27.             如果删除的节点是叶子节点，则直接删除
  28.             如果删除的节点不是叶子节点，则删除该节点及其左右子树
  29.         :param no: 要删除的节点编号
  30.         :return:
  31.         """
  32.         # 如果左子节点不为空，且左子节点是要删除的节点，则删除左子节点及其子树，并返回
  33.         if self.left and self.left.no == no:
  34.             self.left = None  # 相当于删除左子节点及其子树
  35.             return
  36.         # 如果右子节点不为空，且右子节点是要删除的节点，则删除右子节点及其子树，并返回
  37.         if self.right and self.right.no == no:
  38.             self.right = None  # 相当于删除右子节点及其子树
  39.             return
  40.         # 如果左右子节点都不是要删除的节点，则首先向左子节点递归删除
  41.         if self.left:
  42.             self.left.delete_node(no)
  43.         # 如果递归完左子节点还没找到要删除的节点，则继续向右子节点递归删除
  44.         if self.right:
  45.             self.right.delete_node(no)
  46.  
  47.  
  48.  
  49. # 建立 HeroNode 二叉树
  50. class BinaryTree:
  51.     root: HeroNode = None
  52.  
  53.     # 前序遍历
  54.     def pre_order(self):
  55.         if self.root is not None:
  56.             self.root.pre_order()
  57.         else:
  58.             print("二叉树为空...")
  59.  
  60.     # 删除树节点
  61.     def delete_node(self, no: int):
  62.         if self.root:
  63.             if self.root.no == no:  # 如果根节点是要删除的节点
  64.                 self.root = None  # 则把根节点置空
  65.             else:
  66.                 self.root.delete_node(no)
  67.         else:
  68.             print("树空，不能删除节点...")
  69.  
  70.  
  71. def test_binary_tree():
  72.     # 手动创建二叉树
  73.     binary_tree = BinaryTree()
  74.     root = HeroNode(1, '宋江')
  75.     node2 = HeroNode(2, '吴用')
  76.     node3 = HeroNode(3, '卢俊义')
  77.     node4 = HeroNode(4, '林冲')
  78.     node5 = HeroNode(5, "关胜")
  79.  
  80.     root.left = node2
  81.     root.right = node3
  82.     node3.right = node4
  83.     node3.left = node5
  84.     binary_tree.root = root
  85.  
  86.     print("删除前：", end='')
  87.     binary_tree.pre_order()
  88.     print()
  89.  
  90.     binary_tree.delete_node(5)
  91.     print("删除后：", end='')
  92.     binary_tree.pre_order()
  93.     print()
  94.  
  95.  
  96.  
  97. test_binary_tree()

顺序存储二叉树

思路分析

代码实现

需求如下：

  1. """顺序存储二叉树"""
  2. # 顺序存储二叉树就是用数组结构存储二叉树节点数据，
  3. # 要求用数组存储后，可以对该数组进行前序遍历、中序遍历、后序遍历
  4. # 其实就是将二叉树从左到右，从上到下的节点依次存入数组中，如下：
  5. """
  6. 假设有如下一棵二叉树，它对应的顺序存储就是：arr = [1, 2, 3, 4, 5, 6, 7]
  7.                 1
  8.              2      3
  9.           4    5  6    7
  10. """
  11. class ArrayBinaryTree:
  12.     def __init__(self, arr):
  13.         self.arr = arr
  14.  
  15.     def pre_order(self, index: int):
  16.         """
  17.         以前序遍历方式访问数组元素
  18.         :param index: 数组下标
  19.         :return:
  20.         """
  21.         n = len(self.arr)  # n为数组长度
  22.         if self.arr and n > 0:
  23.             # 输出当前元素
  24.             print(f"arr[{index}]={self.arr[index]}", end=" ")
  25.             # 向左子树递归
  26.             if 2 * index + 1 < n:
  27.                 self.pre_order(2 * index + 1)
  28.             # 向右子树递归
  29.             if 2 * index + 2 < n:
  30.                 self.pre_order(2 * index + 2)
  31.         else:
  32.             print("数组为空！")
  33.  
  34.     def infix_order(self, index: int):
  35.         """
  36.         以中序遍历方式访问数组元素
  37.         :param index: 数组下标
  38.         :return:
  39.         """
  40.         n = len(self.arr)
  41.         if self.arr and n > 0:
  42.             if 2 * index + 1 < n:  # 向左子树递归
  43.                 self.infix_order(2 * index + 1)
  44.             print(f"arr[{index}]={self.arr[index]}", end=" ")
  45.             if 2 * index + 2 < n:  # 向右子树递归
  46.                 self.infix_order(2 * index + 2)
  47.         else:
  48.             print("数组为空")
  49.  
  50.     def post_order(self, index: int):
  51.         """
  52.         以后序遍历方式访问数组元素
  53.         :param index: 数组下标
  54.         :return:
  55.         """
  56.         n = len(self.arr)
  57.         if self.arr and n > 0:
  58.             if 2 * index + 1 < n:  # 向左子树递归
  59.                 self.post_order(2 * index + 1)
  60.             if 2 * index + 2 < n:  # 向右子树递归
  61.                 self.post_order(2 * index + 2)
  62.             print(f"arr[{index}]={self.arr[index]}", end=" ")
  63.  
  64.  
  65. arr_binary_tree = ArrayBinaryTree([1, 2, 3, 4, 5, 6, 7])
  66. print("前序遍历：")
  67. arr_binary_tree.pre_order(0)
  68. print()
  69. print("中序遍历：")
  70. arr_binary_tree.infix_order(0)
  71. print()
  72. print("后序遍历：")
  73. arr_binary_tree.post_order(0)
  74. print()

线索化二叉树

简单介绍

思路分析

遍历线索化二叉树

线索化二叉树和遍历线索化二叉树的代码实现

  1. """ 线索化二叉树 """
  2. # 创建 Node 节点
  3. class Node:
  4.     no: int = None
  5.     left = None
  6.     right = None
  7.     # left_type/right_type 表示指针类型
  8.     # 值为0时表示指向的是左子树/右子树，为1时表示指向的是前驱节点/后继节点
  9.     left_type: int = 0
  10.     right_type: int = 0
  11.  
  12.     def __init__(self, no: int):
  13.         self.no = no
  14.         self.left = None
  15.         self.right = None
  16.  
  17.     def __str__(self):
  18.         return f"no={self.no}"
  19.  
  20.  
  21. # 建立线索化 Node 二叉树
  22. class ThreadedBinaryTree:
  23.     root: Node = None
  24.     # 为了实现线索化，需要一个指针（变量）指向当前节点的前驱节点
  25.     # 如中序线索化中，需要一个指针（变量）指向当前节点在中序遍历结果中的前驱节点
  26.     # 在递归进行线索化时， pre 总指向当前节点按某种遍历方式结果的前驱节点
  27.     pre: Node = None
  28.  
  29.     # 建立中序线索化二叉树
  30.     def threaded_infix_tree(self, node: Node):
  31.         """
  32.         建立中序线索化二叉树
  33.         :param node: 要线索化的节点
  34.         :return:
  35.         """
  36.         if node is None:  # 节点为空，不需要线索化
  37.             return
  38.         # 先线索化左子树
  39.         self.threaded_infix_tree(node.left)
  40.         # 线索化当前节点
  41.         # 结合图形理解代码，第一个要线索化的节点是8
  42.         # 先处理当前节点的左子节点
  43.         if node.left is None:  # 如果当前节点的左指针为空，则让左指针指向当前节点的前驱节点pre
  44.             node.left = self.pre
  45.             node.left_type = 1  # 设置指针类型为1，表示该指针指向的是前驱节点
  46.         # 处理后继节点
  47.         if self.pre and  self.pre.right is None:
  48.             self.pre.right = node
  49.             self.pre.right_type = 1  # 设置指针类型为1，表示该指针指向的是后继节点
  50.         # 每处理一个节点后，让当前节点成为下一个节点的前驱节点
  51.         self.pre = node
  52.         # 后线索化右子树
  53.         self.threaded_infix_tree(node.right)
  54.  
  55.     # 遍历中序线索化二叉树
  56.     def for_in_tree(self):
  57.         node = self.root
  58.         while node:
  59.             # 循环找到 left_type = 1 的节点，该节点就是中序遍历的第一个节点，即图中的节点8
  60.             while node.left_type == 0:
  61.                 node = node.left
  62.             # 输出当前节点
  63.             print(node, end=" ")
  64.             # 如果当前节点的右指针指向的是后继节点，则一直输出
  65.             while node.right_type == 1:
  66.                 node = node.right
  67.                 print(node, end=" ")
  68.             # 替换要遍历的节点，具体过程通过debug和结合图来看会更容易理解
  69.             node = node.right
  70.  
  71.  
  72. def test_binary_tree():
  73.     # 手动创建二叉树
  74.     binary_tree = BinaryTree()
  75.     root = Node(1)
  76.     node2 = Node(3)
  77.     node3 = Node(6)
  78.     node4 = Node(8)
  79.     node5 = Node(10)
  80.     node6 = Node(14)
  81.  
  82.     root.left = node2
  83.     root.right = node3
  84.     node2.left = node4
  85.     node2.right = node5
  86.     node3.left = node6
  87.  
  88.     threaded_binary_tree = ThreadedBinaryTree()
  89.     threaded_binary_tree.root = root
  90.     # 测试线索化
  91.     print(f"线索化前：10的left={node5.left}，right={node5.right}")
  92.     threaded_binary_tree.threaded_infix_tree(root)
  93.     # 以10号节点，即node5测试
  94.     print(f"线索化后：10的前驱节点={node5.left}，后继节点={node5.right}")
  95.  
  96.     # 测试遍历线索化二叉树
  97.     threaded_binary_tree.for_in_tree()
  98.  
  99.  
  100. test_binary_tree()

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/275023
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号