测试开发基础之算法（11）：⼆叉树的三种遍历算法及典型题解
树是⼀种⾮线性表数据结构，相⽐数组、链表、队列、栈、散列表等线性数据结构要复杂⼀些。树根据存储的数据特点，形成了很多有特点的树，⽐如典型的⼆叉树，在很多场景具有应⽤。⼆叉树在⾯试中也是经常会被考到的点。本篇⽂章就来全⾯认识⼆叉树，并学会在⼆叉树的各种操作。
1.树和⼆叉树的核⼼概念
⽤图来展⽰树的概念，最为直观，下⾯5幅图中第⼀个不是树，其余四个是树。
树这种数据结构很像现实⽣活中的树。图中的每个点，叫做“节点”，节点之间的连线叫做“⽗⼦关系”。以上⾯的第②个图为例，A叫根节点，A是B的⽗节点，B是A的⼦节点，B、C、D之间互称兄弟节点。G H I叫作叶⼦节点。
“树”还有三个⽐较相似的概念：⾼度（Height）、深度（Depth）、层（Level），上⾯第三幅图展⽰了三者之间的区别。
二叉树公式
树的结构很多，但是常⽤的还是⼆叉树。⼆叉树顾名思义是只有两个叉，也就是有左右两个节点，如上⾯的③④⑤都是⼆叉树，⽽②是三叉树。上图第④幅图，除了叶⼦节点，其他节点都有两个⼦节点，这样的数叫做满⼆叉树。上图的第⑤幅图，叶⼦节点都落在最下⾯两层，最后⼀层的叶⼦节点都靠左排列，其它层节点的个数都达到了最⼤个数，这样的数叫做完全⼆叉树。
2.⼆叉树的存储⽅式
满⼆叉树的特点⽐较明显，但是完全⼆叉树的特点并不明显，为啥会特别提出完全⼆叉树的概念呢。这主要与⼆叉树的存储⽅式相关，完全⼆叉树的数组储存⽅式最省空间。下⾯我们详细看下⼆叉树的存储⽅式。⼆叉树有两种常⽤的存储⽅式：⼆叉链式存储法和数组顺序存储法。
⼆叉链式存储
⼆叉链式存储是⽐较直观、常⽤和简单的存储法。如下图
树中的每⼀个字段都有三个字段，分别是数据，左⼦节点指针和右⼦节点指针。从根节点开始，使⽤左
右⼦节点指针，就可以遍历整个树了。
数组的顺序存储法
基于数组的顺序存储法，是将树中的所有结点存放到数组中。根节点存放到数组下标i=1的位置，左⼦节点存放到下标为2i的位置，右⼦节点存放下标为2i+1的位置。以下图完全⼆叉树为例：
可以见完全⼆叉树在数组中的存储⽅式⽐较紧凑，仅浪费了⼀个下标为0的空间。⽽⾮完全⼆叉树，采⽤数字的顺序存储法则会浪费⽐较多的空间。
3.前中后序遍历⼆叉树
遍历是⼆叉树的重要操作，⽐较经典的遍历⽅法有：前序遍历、中序遍历和后续遍历。前中后代表是遍历时，当前节点与左右⼦节点的先后顺序。
前序遍历，指的是先打印当前节点，再打印左⼦树，最后打印右⼦树。
中序遍历，指的是先打印左⼦树，再打印当前节点，最后打印右⼦树。
后续遍历，指的是先打印左⼦树，再打印右⼦树，最后打印当前节点。
上⾯三种遍历⽅式，⽤图来表⽰就是：
实际上，⼆叉树的遍历就是⼀个递归过程。⽐如前序遍历，就是先打印当前节点，接着递归打印左⼦树，最后递归打印右⼦树，遍历的时间复杂度是 O(n)。
前序遍历的递推公式：
preOrder (node) = print node->preOrder(node->left)->preOrder(node->right)
中序遍历的递推公式：
inOrder(node) = inOrder(node->left)->print node->inOrder(node->right)
后序遍历的递推公式：
postOrder(node) = postOrder(node->left)->postOrder(node->right)->print node
有了递归公式，我们看看代码的实现。
from typing import TypeVar, Generic, Optional, Generator
T = TypeVar("T")
class TreeNode(Generic[T]):
def__init__(self, value):
self.value = value
self.left =None
self.right =None
def pre_order(root: Optional[TreeNode[T]])-> Generator[T,None,None]:
"""
:param root：根节点
:return:⽣成器
"""
if root:
yield root.value  # 先打印当前节点
yield from pre_order(root.left)# 再打印左⼦树
yield from pre_order(root.right)# 再打印右⼦树
def in_order(root: Optional[TreeNode[T]])-> Generator[T,None,None]:
if root:
yield from in_order(root.left)
yield root.value
yield root.value
yield from in_order(root.right)
def post_order(root: Optional[TreeNode[T]])-> Generator[T,None,None]: if root:
yield from post_order(root.left)
yield from post_order(root.right)
yield root.value
if __name__ =='__main__':
b_tree = TreeNode("root_node")
second_layer_left = TreeNode("second_layer_left")
second_layer_right = TreeNode("second_layer_right")
first = TreeNode("first")
second = TreeNode("second")
third = TreeNode("third")
fourth = TreeNode("fourth")
fifth = TreeNode("fifth")
sixth = TreeNode("sixth")
# 拼接成树
b_tree.left = second_layer_left
b_tree.right = second_layer_right
second_layer_left.left = first
second_layer_left.right = second
second_layer_right.left = third
second_layer_right.right = fourth
first.left = fifth
second.left = sixth
# 前序遍历
print(list(pre_order(b_tree)))
# 中序遍历
print(list(in_order(b_tree)))
# 后续遍历
print(list(post_order(b_tree)))
4.按层遍历⼆叉树
按层次遍历⼆叉树，就是即逐层地从左到右访问所有节点。
例如：
给定⼆叉树: [3,9,20,null,null,15,7],
3
/ \
9  20
/
  \
15  7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。