登录 主页

go数据结构(二叉树的概念)

2023-04-11 11:41AM

树的相关概念:

节点

二叉树中的节点包含三个基本信息,即节点值、左子节点和右子节点。其中节点值可以是任意类型的数据,左子节点和右子节点是指向左子树和右子树的指针(若为空则指向空值null)。

根节点

根节点是二叉树中的顶点,它是唯一一个没有父节点的节点。

叶子节点

没有子节点的节点称为叶子节点。

子节点

一个节点的左右被分别称作它的左子节点和右子节点。

父节点

一个节点的父节点是它的直接上级节点。

其中的每个元素叫做节点。树的顶点(没有父元素的节点)叫根节点,如 E;

每个分支的末端节点(没有子元素的节点)叫叶子节点,如 G、H、I、J、K、L;

用来连接相邻节点之间的关系叫父子关系,比如 E 是 A、F 的父节点,A、F 是 E 的子节点;

具有同一个父节点的多个子节点叫做兄弟节点,比如 A、F 是兄弟节点。

节点拥有的子节点数目叫做节点的度,显然,叶子节点的度为 0,树的度是树内各节点度的最大值。

树还有高度、深度和层的概念:

深度和高度:

  • 深度:二叉树的深度是指根节点到该节点的路径长度,根节点的深度为0。
  • 高度:二叉树的高度是指从该节点到最远的叶子节点的路径长度,叶子节点的高度为0。

注:其实线性表也可以看作一种特殊的树,只不过所有节点都在一个分支上,第一个元素是根节点,最后一个元素是子节点,没有兄弟节点。层数就是线性表的长度

参考:Go 数据结构和算法篇(十五):二叉树的定义和存储 - 极客书房

返回>>

登录

请登录后再发表评论。

评论列表:

目前还没有人发表评论