首页 > 编程学习 > 树数据结构:它们是什么以及如何使用它们?

树数据结构:它们是什么以及如何使用它们?

为新的 Web 开发人员简单介绍树数据结构及其应用程序。

tree

illustration of a metal decoration tree.

数据收集已成为 21 世纪最受关注的科技现象。我们知道它存在于我们的计算机文件、电子邮件、社交媒体中,但这些数据究竟是如何存储的?树结构对于访问和存储该信息至关重要。作为 Web 开发人员,了解这些数据结构如何工作以及如何使用它们至关重要。

到底什么是树结构?

tree data structure with root node shown

illustration of tree data structure and its root node. source: https://adarshjaiswal.com/what-is-tree-data-structure/

在深入研究如何使用树结构之前,我们首先需要了解它们是什么以及它们是如何工作的。就像一棵真正的树一样,这种类型的计算机科学结构有一个根和不同的分支,称为节点。

现在,这些节点中的每一个都可以有许多子节点,但必须仅连接到一个父节点。根节点没有父节点,每棵树中的根节点不超过一个。在树的底部,有叶子节点,它们没有任何子节点,位于数据结构的最后一层。

从本质上讲,树数据结构与真正的树完全一样,只是上下颠倒了,可以使用多种类型的树来组织数据。

树数据结构的相关应用

file systems are tree data structures. source: https://docstore.mik.ua/orelly/unix/lrnunix/ch03_01.htm

树数据结构最常见的应用是计算机的文件系统。目录以分层树结构组织和显示。这样可以更轻松地存储信息并了解文件的位置。

二叉树也是一种常见的树结构。它们被称为二进制是因为每个父节点只能有一个或两个子节点。

在计算机科学中,二叉搜索树用于存储和搜索算法。它们有助于在大型数据集中更快地查找数据,从而更容易从树中添加或删除项目。以下是使用 BST 插入数据的示例:

binary search tree. source: https://www.geeksforgeeks.org/floor-in-binary-search-tree-bst/

假设我们想将 x 插入到这棵树中。我们会首先查看根并问自己:58(x) 是大于还是小于 50?更多了,所以我们会顺着右分支到第一个节点,也就是 70。58 比 70 多还是少?它更少,所以我们将下降到 60 并在该节点下方插入 x 作为叶子。

但是这在代码中是怎样的呢?这是我们上面使用 Javascript 的示例:

 <script>  
 // javascript程序来演示  
 // 二进制插入操作  
 // 搜索树  
 /*  
 * 包含当前节点左右子节点和键值的类  
 */  
 类节点{  
   
 构造函数(项目){  
 this.key = 项目;  
 this.left = this.right = null;  
 }  
 } // BST的根  
 var根=空; // 该方法主要调用insertRec()  
 功能插入(键){  
 root = insertRec(root, key);  
 } /*  
 * 在 BST 中插入新密钥的递归函数  
 */  
 功能 insertRec(根,键){ /*  
 * 如果树为空,则返回一个新节点  
 */  
 如果(根==空){  
 根 = 新节点(键);  
 返回根;  
 } /* 否则,沿树递归 */  
 如果(键 < root.key)  
 root.left = insertRec(root.left, key);  
 else if (key > root.key)  
 root.right = insertRec(root.right, key); /* 返回(未更改的)节点指针 */  
 返回根;  
 } // 该方法主要调用InorderRec()  
 函数顺序(){  
 inorderRec(根);  
 } // 一个实用函数  
 // 做BST的中序遍历  
 函数 inorderRec(根)  
 {  
 如果(根!= null){  
 inorderRec(root.left);  
 document.write(root.key+”<br/> ”);  
 inorderRec(root.right);  
 }  
 } // 驱动程序代码 /* 让我们创建以下 BST  
 50  
 / \  
 30 70  
 / \ / \  
 20 40 60 80 */  
 插入(58);  
 // 打印 BST 的中序遍历  
 为了(); // 此代码由 Rajput-Ji 贡献  
 </script>

使用这种方法,我们能够快速地将 x 插入到树中。这在计算机存储了数千甚至数百万信息的大型数据系统中很有用。在组织数据时,二叉搜索树可以为我们节省大量时间。

结论

了解什么是树结构及其最常见的应用程序对于新的 Web 开发人员来说是很有价值的信息。计算机科学已经取得了长足的进步,数据存储现在比以往任何时候都更加重要。还有更多类型的数据结构,这篇介绍性文章几乎没有触及表面!

参考

[

二叉搜索树 |第 1 组(搜索和插入)-GeeksforGeeks

二叉搜索树是一种基于节点的二叉树数据结构,具有以下属性:...

www.geeksforgeeks.org

](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)

[

树结构 - 维基百科

树形结构、树形图或树形模型是一种在...中表示结构层次性质的方法。

en.wikipedia.org

](https://en.wikipedia.org/wiki/Tree_structure)

[

在 JavaScript 中实现二叉搜索树

树是由一些边连接的节点的集合。传统上,树的每个节点都保存一些数据,并且……

www.tutorialspoint.com

](https://www.tutorialspoint.com/implementing-a-binary-search-tree-in-javascript)

[

文件系统的树结构(Unix Power Tools,第 3 版)

多用户系统需要一种方法来让不同的用户拥有同名的不同文件。它还需要一种方法来……

docstore.mik.ua

](https://docstore.mik.ua/orelly/unix3/upt/ch01_14.htm)

[

目录结构 - 维基百科

在计算中,目录结构是操作系统排列用户可访问的文件的方式......

en.wikipedia.org

](https://en.wikipedia.org/wiki/Directory_structure)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明

本文链接:https://www.qanswer.top/29398/14281201

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号