草庐IT

小白科普丨何为树、二叉树和森林？

华为云开发者社区 2023-03-28 原文
摘要：本文为大家带来树、二叉树和森林的表示及如何进行相互转换。

本文分享自华为云社区《树、二叉树和森林的表示及相互转换》，作者：1+1=王。

树的基本概念

树的定义：树是n（n >= 0）个节点的==有限==集。当n=0是，称为空树。

树的特点：

（1）树的根没有前驱，除根外的其他节点有且仅有一个前驱；
（2）每个节点都可以有零个或多个后继。

术语：

（1）节点的度：树中一个节点的孩子个数。
（2）树的度：树中节点的最大度。
（3）分支节点：度大于0的节点。
（4）叶子结点：度为0的节点。
（5）节点的深度：从根节点开始自顶向下逐层累加。
（6）节点的高度：从叶子节点开始自底向上逐层累加。
（7）树的高度：树中节点的最大层数。
（8）路径：两个节点之间所经过的节点序列。
（9）路径长度：路径上所经过的边的个数。
（10）森林：m（m >= 0）棵互不相交的树的集合。

二叉树的基本概念

二叉树的定义：一种特殊的树形结构，它的特点是每个节点至多有两颗子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，不能随意颠倒。

几种特殊的二叉树：

（1）满二叉树：一棵高度为h，且含有2^h - 1个节点的二叉树。

（2）完全二叉树：对应相同高度的满二叉树缺失最下层最右边的一些连续叶子结点。
（3）二叉排序树：左子树上所有节点的关键字都小于根节点的关键字；右子树上所有节点的关键字都大于根节点的关键字；左子树和右子树又各是一棵二叉排序树。（左 < 根 < 右）
（4）平衡二叉树：任一节点的左子树和右子树的深度之差不超过1的二叉排序树。

  • 二叉树的性质：

（1）二叉树的第i层上至多有2^i-1^个节点；
（2）深度为h的二叉树至多有2^k^ - 1个节点；
（3）对任何一个二叉树，若其终端节点树为n0，度为2的节点树为n2，则n0 = n2 + 1;
（4）具有n个节点的完全二叉树的深度为log~2~(n + 1)向上取整。
（5）对完全二叉树按从上到下、从左到右的顺序依次编号1,2,3，…，则有以下关系：
a. 当i>1时，节点i的双亲的编号为i / 2；
b. 当2i<=n时，节点i的左孩子编号为2i，否则无左孩子；
c. 当2i+1<=n时，节点i的右孩子编号为2i+1，否则无右孩子；
d.节点i所在层次为log~2~i + 1（向下取整）。

存储结构

二叉树的存储结构

顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为i-1的分量中。（适合完全二叉树和满二叉树）

链式存储结构：使用链表节点来存储二叉树中的每个节点。二叉链表包括数据域data、左指针域lchild和右指针域rchild三个域。

typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

树的存储结构

双亲表示法：用一组连续空间来存储树的每个结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

#define MAX_TREE_SIZE 100//节点最大个数
typedef struct PTNode{//节点结构
TElemType data;
int parent;//双亲位置域
}PTNode;
typedef struct{//树结构
PTNode nodes[MAX_TREE_SIZE ];
int root,n;//根的位置和节点数
}PTree;

孩子表示法：将没得节点的孩子节点都用单链表链接起来形成一个线性结构，此时n个节点就有n个孩子链表。

#define MAX_TREE_SIZE 100//节点最大个数
typedef struct CTNode{//孩子节点
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct{
TElemType data;
ChildPtr firstChild;//孩子链表头指针
}CTBox;
typedef struct{//树结构
CTBox nodes[MAX_TREE_SIZE ];
int root,n;//根的位置和节点数
}CTree;

孩子兄弟表示法（二叉树表示法）：以二叉链表作为树的存储结构。每个节点包括三部分内容：节点值、指向第一个孩子结点的指针和指向下一个兄弟节点的指针。

typedef struct CSNode{//节点结构
TElemType data;
struct CSNode *firstChild,*nextSibling;
}CSNode,*CSTree;

树、二叉树和森林的相互转换

树转换为二叉树

  • 规则：每个节点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。由于根节点没有兄弟，所以对应的二叉树没有右子树。
  • 画法：（1）在兄弟节点之间加一条线；（2）在每棵树根之间加一条线；（3）以第一棵根为轴心，顺时针旋转45度。

森林转换为二叉树

  • 规则：先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树为空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当做第一棵二叉树根的右子树，将第三棵树对应的二叉树当做第二棵二叉树根的右子树…以此类推，即可将森林转换为二叉树。
  • 画法：（1）将森林中的每棵树转换为二叉树；（2）对每个节点，只保留它与第一个孩子的连线；（3）以根为轴心，顺时针旋转45度。

二叉树转换为森林

  • 若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，将根与右子树断开
  • 将右子树视为一棵新的二叉树，重复第一步。

 

点击关注，第一时间了解华为云新鲜技术~

何为小白dataspancolor代码与软件发布

有关小白科普丨何为树、二叉树和森林？的更多相关文章

  1. ruby - 如何为 emacs 安装 ruby​​-mode - 2

    我刚刚为fedora安装了emacs。我想用emacs编写ruby。为ruby​​提供代码提示、代码完成类型功能所需的工具、扩展是什么？ 最佳答案 ruby-mode已经包含在Emacs23之后的版本中。不过，它也可以通过ELPA获得。您可能感兴趣的其他一些事情是集成RVM、feature-mode(Cucumber)、rspec-mode、ruby-electric、inf-ruby、rinari(用于Rails)等。这是我当前用于Ruby开发的Emacs配置:https://github.com/citizen428/emacs

  2. ruby-on-rails - 如何为空白字段编写 rspec？ [Rails3.1] - 2

    我使用rails3.1+rspec和factorygirl。我对必填字段(validates_presence_of)的验证工作正常。我如何让测试将该事实用作“成功”而不是“失败”规范是:describe"Addanindustrywithnoname"docontext"Unabletocreatearecordwhenthenameisblank"dosubjectdoind=Factory.create(:industry_name_blank)endit{shouldbe_invalid}endend但是我失败了:Failures:1)Addanindustrywithnona

  3. ruby - 如何为 pbcopy 生成富文本链接 - 2

    我一直在玩一个脚本，它在Chrome中获取选定的文本并在Google中查找它，提供四个最佳选择，然后粘贴相关链接。它以不同的格式粘贴，具体取决于当前在Chrome中打开的页面-DokuWiki打开的DokuWiki格式，普通网站的HTML，我想要我的WordPress所见即所得编辑器的富文本。我尝试使用pbpaste-Preferrtf来查看没有其他样式的富文本链接在粘贴板上的样子，但它仍然输出纯文本。在文本编辑中保存文件并进行试验后，我想出了以下内容text=%q|{\rtf1{\field{\*\fldinst{HYPERLINK"URL"}}{\fldrsltTEXT}}}|te

  4. 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:

  5. ruby - 如何为字母、元音和辅音等德语字符类编写正则表达式？ - 2

    例如，我设置了这些:L=/[a-z,A-Z,ßäüöÄÖÜ]/V=/[äöüÄÖÜaeiouAEIOU]/K=/[ßb-zBZ&&[^#{V}]]/因此/(#{K}#{V}{2})/匹配"azAZßäÜ"中的"ßäÜ"。有没有更好的方法来处理它们？我能否将这些常量放在我的Ruby安装文件夹中某个文件中的模块中，这样我就可以在我在计算机上编写的任何新脚本中包含/要求它们？(我是新手，我知道我混淆了这个术语；请纠正我。)此外，我能否只获取元字符\L、\V和\K(或任何尚未在Ruby中设置)以在正则表达式中代表它们，所以我不必一直做字符串插值？ 最佳答案

  6. ruby-on-rails - Rails 如何为 Google Charts 构建数据结构 - 2

    我想使用googlecharts创建一个如下所示的图表:GoogleChart.pie_400x200('TacoBell'=>0,'Mediterranean'=>2,'Shivas'=>5)给定一个对象Results(name,count)。如何为GoogleCharts的结构创建一个对象，如上所示？谢谢 最佳答案 从您在评论中列为@results的结果对象开始，以下应该有效:GoogleChart.pie_400x200(@results.map{|r|{r[:title]=>r[:percentage]}})

  7. ruby - 如何为类方法动态定义别名方法？ - 2

    我有一个名为“计算器”的模块，我想将其包含在“产品”类中。Calculator将扩展“Product”，它将类方法复制到Product上。这些类方法之一是“memoize”。我的想法是我可以做这样的事情:moduleCalculatordefself.extended(base)base.memoize:foo_barendend以内存方法(特别是类方法)为目的:foo_bar。在memoize内部，我调用方法“alias_method”，它试图将类方法别名为不同的名称(此处为:foo_bar)。这失败了。Memoize看起来像这样:moduleCalculator(theextend

  8. ruby - 如何为命名空间类定义 Fabricator - 2

    我想为类定义Fabricator，其命名空间类似于“Foo::Bar”。告诉我它的工作方式。这是我的代码。模型/foo.rbclassFooincludeMongoid::Documentembedded_in:foo_container,polymorphic:truefield:xxx....end模型/foo/bar.rbclassFoo::Bar数据/制造商/foo_bar_fabricator.rbFabricator(:foo_bar,class_name:'Foo::Bar')doyyy'MyString'zzz'MyString'end当我尝试在parino控制台上创建

  9. 关于如何为 PostgreSQL 编写存储过程的 Ruby 教程？ - 2

    听说PostgreSQL的可以用Ruby写存储过程但我一直没能找到更多关于它的信息，教人们如何实际去做。有人可以为此推荐好的资源。谢谢 最佳答案 显然，您需要安装PL/Ruby。之后，你可以写:CREATEFUNCTIONruby_max(int4,int4)RETURNSint4AS'ifargs[0].to_i>args[1].to_ireturnargs[0]elsereturnargs[1]end'LANGUAGE'plruby';查看其GitHubrepository安装说明。

  10. ruby-on-rails - 如何为法语设置 Rails？ - 2

    我必须为我的公司开发一个RubyonRails应用程序，但不知道如何为法语站点配置它。我不需要多语言支持，我只想要法语的错误消息、复数和日期格式。我试着设置:config.i18n.default_locale=:fr在我的application.rb文件中，但它似乎没有任何效果。RoR3中是否已经实现了这些功能？还是我必须自己翻译这些东西？ 最佳答案 要将应用程序设置为法语，您需要在config/application.rb中设置config.i18n.default_locale=:fr，创建fr.yml文件在您的应用程序con

随机推荐