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) 遍历有三种不同的类型
这三种深度优先搜索 (DFS) 遍历将在接下来的页面中详细介绍。
