树
树是由边连接的节点组成的非线性分层数据结构。
数组、链表、栈、队列等其他数据结构都是按顺序存储数据的线性数据结构。为了在线性数据结构中执行任何操作，时间复杂度随着数据大小的增加而增加。但是，在当今的计算世界中，这是不可接受的。
不同的树数据结构允许更快、更轻松地访问数据，因为它是一种非线性数据结构。
在时间上，树访问更快。
相关术语
节点
节点是包含键或值以及指向其子节点的指针的实体。
每条路径的最后一个节点称为叶节点或不包含指向子节点的链接/指针的外部节点。
具有至少一个子节点的节点称为内部节点。
深度和高度
应用
- 二叉搜索树（BST）用于快速检查一个元素是否存在于集合中。
- 堆是一种用于堆排序的树。
- 现代路由器使用树的修改版本 Tries 来存储路由信息。
- 大多数流行的数据库使用 B-Trees 和 T-Trees，它们是我们上面学习的树结构的变体来存储它们的数据
- 编译器使用语法树来验证您编写的每个程序的语法。
树遍历
遍历树意味着访问树中的每个节点。例如，您可能想要添加树中的所有值或找到最大的值。对于所有这些操作，您将需要访问树的每个节点。
像数组、堆栈、队列和链表这样的线性数据结构只有一种读取数据的方法。但是像树这样的分层数据结构可以以不同的方式遍历。
例如：
left 和 right 指向的 struct 节点可能还有其他的 left 和 right 子节点，因此我们应该将它们视为子树而不是子节点。
根据这种结构，每棵树都是
- 承载数据的节点
- 两个子树
请记住，我们的目标是访问每个节点，因此我们需要访问子树中的所有节点，访问根节点并访问右子树中的所有节点。
根据我们执行此操作的顺序，可以有三种类型的遍历。
中序遍历
left -> root -> right
from left down to root top to right dowm前序遍历
root-> left->right
from top to down后序遍历
left->right->root
from down to top
中序遍历 例子
我们先遍历左子树。当这棵树完成时，我们还需要记住访问根节点和右子树。
让我们把所有这些都放在一个堆栈中以便我们记住。
现在我们遍历指向栈顶的子树。
同样，我们遵循相同的中序规则
左子树 -> 根 -> 右子树
遍历左子树后，剩下
- Python实现三种遍历
# Tree traversal in Python
class Node:
def __init__(self, item):
self.left = None
self.right = None
self.val = item
def inorder(root):
if root:
# Traverse left
inorder(root.left)
# Traverse root
print(str(root.val) + "->", end='')
# Traverse right
inorder(root.right)
def postorder(root):
if root:
# Traverse left
postorder(root.left)
# Traverse right
postorder(root.right)
# Traverse root
print(str(root.val) + "->", end='')
def preorder(root):
if root:
# Traverse root
print(str(root.val) + "->", end='')
# Traverse left
preorder(root.left)
# Traverse right
preorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Inorder traversal ")
inorder(root)
print("\nPreorder traversal ")
preorder(root)
print("\nPostorder traversal ")
postorder(root)
