DSA 二叉树
二叉树
二叉树是一种树形数据结构，其中每个节点最多可以有两个子节点：左子节点和右子节点。
这种每个节点最多有两个子节点的限制，为我们带来了许多好处。
- 遍历、搜索、插入和删除等算法更容易理解、实现和运行更快。
- 在二叉搜索树 (BST) 中保持数据排序，可以使搜索非常高效。
- 使用有限数量的子节点更容易平衡树，例如使用 AVL 二叉树。
- 二叉树可以表示为数组，从而使树更节省内存。
请使用下面的动画来了解二叉树的样子，以及我们用来描述它的术语。
在二叉树中，父节点或内部节点是具有一个或两个子节点的节点。
左子节点是左侧的子节点。
右子节点是右侧的子节点。
树的高度是从根节点到叶子节点的最大边数。
二叉树与数组和链表比较
二叉树相对于数组和链表的优势
- 数组在直接访问元素时速度很快，例如访问包含 1000 个元素的数组中的第 700 个元素。但是，插入和删除元素需要移动其他元素以腾出新元素的位置，或者占用已删除元素的位置，这非常耗时。
- 链表在插入或删除节点时速度很快，无需移动内存，但要访问列表中的元素，必须遍历整个列表，这需要时间。
- 与数组和链表相比，二叉树（如二叉搜索树和 AVL 树）非常优秀，因为它们既能快速访问节点，又能快速进行删除或插入节点，且无需移动内存。
我们将在接下来的两页中详细介绍二叉搜索树 (BST) 和 AVL 树的工作原理，但首先我们将了解二叉树的实现方式以及如何进行遍历。
二叉树的类型
有几种不同的二叉树变体或类型值得讨论，以便更好地理解二叉树的结构。
现在提及不同类型的二叉树也很重要，因为这些术语和概念将在本教程的后续内容中使用。
下面是对不同类型二叉树结构的简要解释，解释下方附有这些结构的图示，以便尽可能清晰易懂。
一个平衡的二叉树，对于树中的每个节点，其左右子树的高度差最多为 1。
一个满的二叉树，除了最后一层外，所有层都已填满节点，最后一层也可以是满的，或者从左到右填满。满二叉树的特性意味着它也是平衡的。
一个满的二叉树，是指每个节点要么有 0 个子节点，要么有 2 个子节点的树。
一个完美的二叉树，所有叶子节点都在同一层，这意味着所有层都已填满节点，所有内部节点都有两个子节点。完美二叉树的特性意味着它也是满的、平衡的和完整的。
二叉树实现
让我们来实现这个二叉树。
上述二叉树的实现方式与实现单向链表类似，只不过不是将每个节点链接到一个下一个节点，而是创建一种结构，使每个节点都可以链接到其左子节点和右子节点。
这就是二叉树的实现方式
示例
Python
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# Test
print("root.right.left.data:", root.right.left.data)二叉树遍历
一次访问一个节点地遍历一棵树，称为遍历。
由于数组和链表是线性数据结构，它们只有一种明显的遍历方式：从第一个元素或节点开始，继续访问下一个，直到访问完所有节点。
由于树可以向不同方向分支（非线性），因此有不同的遍历树的方式。
树的遍历方法主要分为两大类：
广度优先搜索 (BFS) 是指在访问完同一层的节点后再访问下一层的节点。这意味着树的探索方向更偏向横向。
深度优先搜索 (DFS) 是指遍历一直向下到叶子节点，然后逐个分支地向下探索树。
DFS 遍历有三种不同的类型：
这三种深度优先搜索遍历将在下一页详细介绍。
