草庐IT

学二叉树之前，先来认识下树吧

Claffic 2023-04-21 原文

欢迎来到 Claffic 的博客 💞💞💞 

前言：

往期给大家讲了链表，栈，队列等数据结构， 它们都是线性结构，而今天要讲的是一种非线性结构：树，让我们开始吧！ 

目录

🌳1.什么是树？

🪲2.有关树的概念

🎄3.树的表示 

⛏️4.树的实际应用

1.什么是树？

树，木本植物之总名... ...欸，走错频道了？

其实数据结构中的树就是由大自然中的树定义来的，因为它们有很多相似之处：

                        自然中的树(倒置)                                                  数据结构的树

怎么样？是不是还蛮像的🤩

自然地，最顶端的那个结点就叫做 根节点 (图中A结点)

此时引出树的概念：

树是一种非线性的数据结构，它是由 n (n>=0)个有限结点组成的一个具有层次关系的集合。

我们仔细来看看这颗树： 

从顶端开始，可以发现 根结点 以上是没有结点的，这里暂称为没有前驱结点

注意看，这棵树由根节点分出了三个方向，这三个箭头下又分别有一颗小树，我们称它们为子树。

把子树2拿出来再进行分割：

                                      

子树2下又有子树2.1...

子树下有子树，子树下又有子树... ...

怎么有点像，

递归？

是的，可以理解为 树是递归定义的 。

接下来跟我看看下面的结构是不是树： 

记住：这不是树，三条红边不能存在任意一条！！！

这部分的总结： 

• 树顶端的结点称为根节点，根节点没有前驱结点；

• 子树之间不能相交🍌；

• 除了根节点之外，每个结点有且仅有一个前驱节点；

• 一棵N个结点的树有N-1条边；

• 树是递归定义的。

2.有关树的概念

为了更好介绍树的有关概念，这里画一个更复杂的树：
 

• 结点的度：一个结点含有的子树个数（结点下的分支） 如结点A的度为5；

• 树的度：一棵树中最大的结点的度  如上树的度为5；

• 结点的层次：根是第1层，根的子节点所在层是第2层，如此递增；

• 树的高(深)度：最大的结点的层次  如上树的高(深)度是4；

• 叶子结点：度为0的结点（没有子树）  如结点 N，O；

• 双亲结点：如A是B，C，D，E，F的双亲结点；

• (孩)子结点：如B，C，D，E，F是A的(孩)子结点；

• 兄弟结点：具有相同双亲结点的子节点  如G，H；

• 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点  如H，I；

• 非终端结点/分支结点：度不为0的结点  如C，D，E...；

• 结点的祖先：从根节点所经分支上的所有结点  如A是所有结点的祖先；

3.树的表示 

毕竟是代码人，知道了树的结构，就要考虑怎么表示树比较好，

先来想想具体需要表示什么： 

一个是要存储的数据，

另一个是结点与结点之间的关系；

重点看后者：

要表示关系，最好是既能在一条线上深入，又能关系到临近的一条线。

我们想到了孩子与兄弟：

typedef int DataType;
struct Node
{
    struct Node* Child1; // 第一个孩子结点
    struct Node* brother; // 指向兄弟结点
    DataType data; // 结点中的数据域
};

除了孩子兄弟表示法这种最常见的表示法，此外还有双亲表示法，孩子表示法，孩子双亲表示法。

由于树的结构本身是具有不确定性的，所以这里不做深一步的实现，大家知道有这些表示方法就好。

4.树的实际应用

这里说个最典型的吧： 

文件资源管理器中的文件管理就是一个树结构：

总结： 

这篇博客介绍了树，其实主要作用是为了后期二叉树做铺垫，大家了解它的结构，知道相关概念即可。 

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗

先来学xffstrongxff0c数据结构c语言

有关学二叉树之前，先来认识下树吧的更多相关文章

  1. ruby - 如何在 Rails 4 中使用表单对象之前的验证回调？ - 2

    我有一个服务模型/表及其注册表。在表单中，我几乎拥有服务的所有字段，但我想在验证服务对象之前自动设置其中一些值。示例:--服务Controller#创建Action:defcreate@service=Service.new@service_form=ServiceFormObject.new(@service)@service_form.validate(params[:service_form_object])and@service_form.saverespond_with(@service_form,location:admin_services_path)end在验证@ser

  2. ruby-on-rails - 如何处理 Grape 中特定操作的过滤器之前？ - 2

    我正在我的Rails项目中安装Grape以构建RESTfulAPI。现在一些端点的操作需要身份验证，而另一些则不需要身份验证。例如，我有users端点，看起来像这样:moduleBackendmoduleV1classUsers现在如您所见，除了password/forget之外的所有操作都需要用户登录/验证。创建一个新的端点也没有意义，比如passwords并且只是删除password/forget从逻辑上讲，这个端点应该与用户资源。问题是Grapebefore过滤器没有像except,only这样的选项，我可以在其中说对某些操作应用过滤器。您通常如何干净利落地处理这种情况？

  3. ruby-on-rails - 在 Ruby on Rails 中发送响应之前如何等待多个异步操作完成？ - 2

    在我做的一些网络开发中，我有多个操作开始，比如对外部API的GET请求，我希望它们同时开始，因为一个不依赖另一个的结果。我希望事情能够在后台运行。我找到了concurrent-rubylibrary这似乎运作良好。通过将其混合到您创建的类中，该类的方法具有在后台线程上运行的异步版本。这导致我编写如下代码，其中FirstAsyncWorker和SecondAsyncWorker是我编写的类，我在其中混合了Concurrent::Async模块，并编写了一个名为“work”的方法来发送HTTP请求:defindexop1_result=FirstAsyncWorker.new.async.

  4. ruby-on-rails - 在所有延迟的作业之前 Hook - 2

    是否可以在所有delayed_job任务之前运行一个方法？基本上，我们试图确保每个运行delayed_job的服务器都有我们代码的最新实例，所以我们想运行一个方法来在每个作业运行之前检查它。(我们已经有了“check”方法并在别处使用它。问题只是关于如何从delayed_job中调用它。) 最佳答案 现在有一种官方方法可以通过插件来做到这一点。这篇博文通过示例清楚地描述了如何执行此操作http://www.salsify.com/blog/delayed-jobs-callbacks-and-hooks-in-rails(本文中描述

  5. ruby-on-rails - define_method 在调用方法之前不使用变量？ - 2

    我无法从for循环中获取变量。似乎i(var)是稍后计算的，而不是我完全需要的类定义。ree-1.8.7-2010.02>classPatree-1.8.7-2010.02?>foriin39..47ree-1.8.7-2010.02?>define_method("a#{i}".to_sym)doree-1.8.7-2010.02>putsiree-1.8.7-2010.02?>endree-1.8.7-2010.02?>endree-1.8.7-2010.02?>end#=>39..47ree-1.8.7-2010.02>p=Pat.new#=>#ree-1.8.7-2010.02

  6. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  7. ruby-on-rails - ActiveRecord:除非另有说明，否则在保存之前使所有文本字段都调用 strip - 2

    多年来，我在各种网站上遇到过各种问题，用户在字符串和文本字段的开头/结尾放置空格。有时这些会导致格式/布局问题，有时会导致搜索问题(即搜索顺序看起来不对，但实际上并非如此)，有时它们实际上会使应用程序崩溃。我认为这会很有用，而不是像我过去所做的那样放入一堆before_save回调，向ActiveRecord添加一些功能以在保存之前自动调用任何字符串/文本字段上的.strip，除非我告诉它不是，例如do_not_strip:field_x,:field_y或类定义顶部的类似内容。在我去弄清楚如何做到这一点之前，有没有人看到更好的解决方案？明确一点，我已经知道我可以做到这一点:befor

  8. ruby-on-rails - 如何在 Rails 3 中保存到数据库之前格式化值 - 2

    我有一个带有利润字段的用户模型。利润字段是DECIMAL(11,0)类型。我在表单上有一个屏蔽输入，允许用户输入1,000美元之类的内容。我想格式化该值并从中删除除数字以外的所有内容，这样我将保存1000。这是我到目前为止所拥有的:classUser但它一直在数据库中保存0。看起来它在我的格式化函数之前将其转换为十进制。 最佳答案 试试这个:defprofit=(new_profit)self[:profit]=new_profit.gsub(/[^0-9]/,'')end 关于ruby

  9. ruby-on-rails - Ruby on Rails - 我可以在调用之前修改属性的值吗？ - 2

    假设我有一个名为Product的模型，其中有一个名为brand的字段。假设brand的值以this_is_a_brand格式存储。我可以在模型(或其他任何地方)中定义一个方法，允许我在调用brand之前修改它的值吗？例如，如果我调用@product.brand，我想得到ThisisaBrand，而不是this_is_a_brand。 最佳答案 我建议使用方括号语法([]和[]=)而不是read_attribute和write_attribute。方括号语法更短并且designedtowraptheprotectedread/writ

  10. ruby-on-rails - 在 Rails 中，如何在特定的 Rspec 测试之前加载所有代码？ - 2

    我有一些Rspec测试有时会因错误而失败:自动加载常量时检测到循环依赖。这些测试是多线程的(rufus-scheduler测试)，这显然是自动加载代码的已知问题(http://route.github.io/2013/11/13/rails-autoloading.html)。如果我在config/environments/test.rb中设置config.eager_load=true，我可以使测试始终如一地工作。但是，我担心当它变大时，这会真正减慢我的测试套件的其余部分。有什么方法可以仅为我的多线程测试设置这个预加载选项吗？rails4.1.4 最佳答案

随机推荐