通常开始学习编程的时候，都会接触到一些常用的数据结构。哈希表一般是最后才学的。对于那些正在攻读计算机科学学位的人，您通常必须通过学习链表、队列和堆栈来学习专门的数据结构课程。这些统称为线性数据结构，因为它们是按逻辑顺序从头到尾排列的。当你开始进入下一个层次，学习树和图结构时，事情开始看起来比处理线性数据结构要复杂得多。这促使我们专门写了一篇文章来讨论“树”的具体数据结构，以帮助大家答疑解惑。本文涵盖：树的定义树的结构工作原理代码实现现在开始学习:)新程序员通常比树和图更容易理解树的定义。我们这里说的树是一种特定的数据结构，它以分层的方式组织和存储数据。实例分析为了理解“等级”的含义，我们以一个家谱为例：有祖父母、父母、子女、兄弟姐妹。这是使用分层模式来构建家谱。上图是我的家谱。Tossico、Akikazu、Hitomi和Takemi在我的祖父母和外祖父母中名列前茅。Toshiaki和Juliana是我的父母。TK、Yuji、Bruno和Kaio是我和我的兄弟姐妹。组织也是类似的层次结构，因为HTML的文档模型对象(DOM)是一棵树，最顶层的HTML标签连接到head和body标签。两者都有相应的子标签，例如head包含meta和title标签，body包含h1、a、li等与视觉内容相关的标签。名词定义树（tree）：是由边（edges）连接的节点（nodes）的集合，每个节点存储一个对应的值（value/data），当有子节点时与它相连。根节点（root）：它是树的第一个节点。在两个相连的节点中，靠近根节点的成为父节点，对应的另一个节点称为子节点。).边：所有节点都由边连接，边用于标识节点之间的关系。边是树中的一个重要概念，因为我们使用它们来确定节点之间的关系。叶节点（Leaves）：是树的末端节点。它们没有子节点，就像真正的树一样，从根开始，延伸到树枝，到叶子为止。树高（height）和节点深度（depth）也是很重要的概念。树高：从根节点开始，到子节点的最长路径的长度。节点深度：指从对应节点到根节点的路径长度。二叉树下面我们来讨论一种特殊的树结构——二叉树（binarytree），每个节点最多有两个子节点，也称为左孩子和右孩子。在计算机科学中，二叉树是一种“树”数据结构，其中树上的每个节点最多有两个孩子，一个左孩子和一个右孩子。——维基百科看一个二叉树的例子。手写一棵二叉树，首先要明确我们要实现的对象是节点的集合，每个节点都有三个属性：值（value）、左孩子（left_child）和右孩子（right_child).写出来会是这样的：我们写了一个BinaryTree类，在初始化实际对象的时候传入了相应的值，此时没有子节点的时候就把左右子节点设置为空。我们为什么要做这个？因为当我们创建一个节点时，它还没有孩子，我们只有节点数据。我们来测试一下：下面是插入节点的操作：当树没有对应的子节点时，新建一个节点，赋值给已有节点对应的变量。否则，新节点连接并替换现有位置子节点。如图所示：对应代码（左右相同）：为了进一步测试，让我们构建一棵更复杂的树：这棵树共有六个节点，节点b没有左孩子。初始化和插入节点的代码如下：接下来我们看看如何遍历树。一般来说，我们有两种遍历方法：深度优先遍历（DFS）和广度优先遍历（BFS）。前者沿着特定的路径遍历到根节点然后转换相邻路径继续遍历，后者逐层遍历整个树结构。下面看具体的例子：深度优先遍历（DFS）DFS会沿着特定的路径遍历到叶子节点，然后回溯（backtracking）到相邻的路径继续遍历。以下面的树结构为例：遍历顺序为1–2–3–4–5–6–7具体来说，我们会先访问根节点1，然后访问它的左孩子2，再访问左孩子3of2，回退一步到叶子节点，访问右孩子4of2，再往回走，继续依次访问5、6、7。在输出遍历结果时，根据父节点值相对于子节点输出顺序的不同，深度优先遍历可以细分为三种情况：前序、中序和后序遍历。前序遍历是按照我们访问节点的顺序直接输出遍历结果，父节点值先输出。代码：中序遍历中序遍历的输出为：3-2-4-1-6-5-7。先输出左孩子值，再输出父节点，最后输出右孩子。对应代码如下：后序遍历后序遍历输出结果为：3-4-2-6-7-5-1。左右子值依次输出，最后一个为父节点。对应代码如下：广度优先搜索（BFS）BFS：根据节点深度逐层遍历树结构。拿上图来实际解释一下这个方法：每一层从左到右逐层遍历，对应的遍历结果为：1-2-5-3-4-6-7。对应的代码如下：大家应该注意到了，我们需要使用先进先出（FIFO）的队列结构来完成操作。具体入队和出队顺序如下图所示：执行搜索等操作。——维基百科其最明显的特点是父节点的值大于左子树中任意一个节点的值，小于右子树任意一个节点的值。上图以三棵二叉树为例，哪一个是正确的？A的左右子树需要交换。B满足条件，是一棵二叉搜索树。C值为4的节点需要移动到3的右孩子，依次进行二分查找插入、节点检索、节点删除、平衡解释。插入假定节点按以下顺序插入：50、76、21、4、32、100、64、52。50将是我们的初始根节点。然后依次进行以下操作：76大于50，放在右边，21小于50，放在左边4，放在21的左边，最后我们会得到下面的树在一口气：你找到规律了吗？和驱动一样，从根节点开始驱动，当插入值大于当前节点值时，向右开；否则，向左打开，直到找到停车位。（哔哔，老司机）代码实现也很简单：这个算法最厉害的地方就是它的递归部分，你知道是哪几行吗？其实节点的检索是结合我们的插入操作的，检索的方法很明显，还是从根节点开始，小于对应节点的值就左转，大于对应的值就右转对应节点的值，等于报告找到了。比如我们想知道下图中是否有值52：代码如下：delete:removeandrefactor删除操作比较复杂，因为它要处理三种不同的情况：场景#1：叶子节点是最简单的情况，直接删除即可。场景#2：只有左孩子或右孩子这种场景相当于删除链表上的节点，删除当前节点并让其子节点替换其原来的位置。场景#3：一个有左右孩子的节点在该节点的右子树中找到具有最小值的节点，移除当前要删除的节点，并将最小值节点提升到空出的位置。其他一些操作被清除：只需将三个属性都设置为None即可。求最小值：从根节点开始向左转，直到找不到节点，就找到了最小值。恭喜你完成了本文的内容！数据结构中树的内容大致相同，赶快收藏起来
