一文看懂数据结构中的树 值得收藏
|
副标题[/!--empirenews.page--]
通常在开始学编程的时候，你会接触一些常用数据结构。
到最后一般会学到哈希表。对于修读计算机科学学位的朋友，你通常要上专门的数据结构课，从了解有关链表、队列和栈的各种知识。这些统称为线性数据结构，因为依逻辑次序从头排到尾。 当你开始进入下一阶段，学习树和图结构时，事情就会显得比处理线性数据结构复杂很多。这促使我们专门写一篇文章来探讨“树”这种特定的数据结构帮大家答疑解惑。 本文内容包括:
现在就开始学习吧 :) 树的定义 通常对编程新手来说，线性数据结构比树和图要更好理解。我们此处所说的树，即是以层次化方式组织和存放数据的特定数据结构。 实例解析 为了理解“层次化”的意思，我们以家谱为例：里面有祖父母、父母、孩子、兄弟姐妹。这就是用层次化的模式来构建家谱。  上图就是我的家谱。Tossico，Akikazu，Hitomi和Takemi作为我的祖父母和外祖父母处于最顶层。Toshiaki 和 Juliana是我父母。TK，Yuji，Bruno 和 Kaio 则是我和我的的兄弟姐妹们。  公司组织也是类似的层次化结构  HTML的文档模型对象 (DOM) 就是一棵树最顶层 HTML 标签连接到 head 标签和 body 标签。二者又有对应的子标签，比如 head 含有 meta 和 title 标签，body 含有与可视化内容相关的 h1, a, li等标签。名词定义 树(tree)：是以边(edge)相连的结点(node)的集合，每个结点存储对应的值(value/data)，当存在子结点时与之相连。  根结点(root)：是树的首个结点，在相连两结点中更接近根结点的成为父结点(parent node)，相应的另一个结点称为子结点(parent node)。  边(edge)：所有结点都由边相连，用于标识结点间的关系。边是树中很重要的一个概念，因为我们用它来确定节点之间的关系。  叶子结点(Leaves)：是树的末端结点，他们没有子结点，就像真实的树那样 ，由根开始，伸展枝干，到叶为止。  树高(height)与结点深度(depth)也是很重要的概念。树高：是由根结点出发，到子结点的最长路径长度。结点深度：是指对应结点到根结点路径长度。 二叉树 现在来探讨一种特殊的树结构-二叉树(binary tree)，它每个节点最多有两个子结点，亦称左孩子和右孩子。 在计算机科学中，二叉树是一种“树”数据结构，树上的每个节点最多有两个孩子，分别为左孩和右孩。——维基百科 来看一个二叉树的实例。  动手写二叉树 首先明确我们要实现的对象是一个结点集合，每个结点有三个属性：值(value), 左孩子(left_child)和右孩子(right_child)。 写出来会是这个样子：  我们写了一个BinaryTree类，在初始化实际对象的时候传入对应值，并在此时还没有子结点的情况下将左右孩子设为空。 为什么要这么做呢? 因为当我们创建节点的时候，它还没有孩子，我们只有节点数据。 让我们测试一下：  下面到了插入结点的操作：在树还没有对应子结点时新建结点，并赋值给现有结点对应变量。否则，新建结点连接并替换掉现有位置子结点。 画出来是这个样子： 相应代码(左右相同)：  为了进一步测试，让我们构建一个更复杂一些的树：  这棵树共有六个结点，其中结点b没有左孩子。对应初始化并插入结点的代码如下：  下一步让我们看看如何对树进行遍历。 一般来讲我们有两种遍历方式：深度优先遍历(DFS)和 广度优先遍历(BFS)，前者沿着特定路径遍历到根结点再转换临近路径继续遍历，后者逐层遍历整个树结构。来看具体的例子： 深度优先遍历 (DFS) （编辑：鹰潭站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
