Python数据结构之树的全面解读

什么是树？

树是一种重要的数据结构，它以分层的方式存储数据，根据结点之间的层次关系，被称作父结点、子结点以及兄弟结点。

树的组成部分

一棵树由一个根结点、若干个子树以及它们构成的森林组成。树具有以下属性：
- 每个结点都有唯一的一个父结点（除了根结点）
- 每个结点可以有多个子结点
- 没有环路（即，一个结点不能成为它自己的祖先）
- 每个非根结点有重复的子节点

树的基本术语

• Root：根结点，树形结构的顶端，树只有一个根结点
• Node：结点，树的基本单位
• Edge：边，链接两个结点的箭头
• Parent：父结点，某个结点的直接上一级结点
• Child：子结点，某个结点的直接下一级结点
• Sibling：兄弟结点，有同一个父结点的结点互为兄弟结点

树的类型

• 无序树：子节点没有规定顺序的树称为无序树。
• 有序树：子节点有顺序的树称为有序树。
• 二叉树：每个结点最多有两个子节点的树称为二叉树。
• 完全二叉树：对于一棵二叉树，除最后一层外，每一层上的结点数都达到最大值，最后一层上的结点都集中在左边，这样的树称为完全二叉树。
• 满二叉树：对于一棵二叉树，除了最后一层每个结点都有左右子两个子节点外，最后一层的每个结点都没有子节点，这样的树称为满二叉树。
• 平衡二叉树：它是一棵满足任意结点的左右子树高度差都不大于 1 的二叉树。
• B树：B-树就是一种对读写操作进行优化的自平衡树。

树的存储方式

1. 顺序存储法

将树存储再一维矩阵中，可以简单的找到一个节点的儿子。

     规律：第 n 个节点的左儿子下标为 2n，右儿子下标为 2n+1。

该种存储方式缺点很明显，如果树的高度很高，那么数组的空间会浪费很多，因为很多节点是空的。

1. 链式存储法

将每个节点的子树用链表储存起来。节点有两个指针分别指向它的左子树和右子树。

种储存方式比较灵活，节点的数量或者高度没有太高的限制，方便插入、扩展以及删除操作。

树的遍历方式

树的遍历有两种方式：深度优先和广度优先。

深度优先遍历

深度优先遍历有三种方式：先序遍历、中序遍历和后序遍历。

• 先序遍历（preorder）：根结点、左子树、右子树
• 中序遍历（inorder）：左子树、根结点、右子树
• 后序遍历（postorder）：左子树、右子树、根结点

广度优先遍历

广度优先遍历，也被称作层序遍历，按照层级一层层遍历，从每层的左部开始到右边。

BFS基于队列实现。遍历当前节点，将它的不为 None 的孩子按照从左到右、从上到下的顺序加入队列，循环直至队列为空，遍历完整棵树。

例子：

         10
        /  \
       8   12
      / \
     5   9

• 先序遍历：10 8 5 9 12
• 中序遍历：5 8 9 10 12
• 后序遍历：5 9 8 12 10
• 广度优先遍历：10 8 12 5 9

树的应用

• 文件系统：文件系统中的目录结构就是一棵树。

• HTML/CSS：网页的布局是一棵树，我们可以用HTML来表示。

• 数据库：数据库设计中的ER图就是树形结构。

• 机器学习：树的学习一直是机器学习中经典的算法。

总结

树作为一种数据结构，广泛地应用于各种领域。可以看出，掌握树这一知识点对于程序员来说至关重要。