数据结构——树(上)-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

数据结构——树(上)

简介: 树的结构 、二叉树

1、树的定义

什么是树?

长这样?

数据结构——树(上)图1.png

(图片来自网络)

不不不,树是一种数据结构,树是包含 n(n>=0) 个节点,当 n=0 时,称为空树,非空树中(n-1)条边的有穷集,在非空树中:

  • 每个元素称为节点
  • 有一个特定的节点被称为根节点或树根
  • 除根节点之外的其余数据元素被分为m(m>=0)个=个互不相交的集合,其中每一个集合身也是一棵树,被称作原树的子树

树也可以这样定义:

​ 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点,所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位,这个节点称为该树的根节点,或称为树根。

树的结构如下图所示:

数据结构——树(上)图2.png

2、树的基本概念

数据结构——树(上)图3.png

数据结构——树(上)图4.png

3、树的表示

儿子—兄弟表示法——二叉树的引入

数据结构——树(上)图5.png

这里的Element是储存的数据,FirstChild指向它的第一个儿子节点,NextSibling指向它的下一个兄弟

其表现方式为:

数据结构——树(上)图6.png

其中的N是指NULL

这种树的表示方法可以有效防止空间的浪费,在结构复杂,数据不统一时,可以节省大量空间,并且结构统一,方便管理

将其旋转45°,就得到了二叉树

数据结构——树(上)图7.png

接下来给出二叉树的代码:

typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
    ElementType Data; /* 结点数据 */
    BinTree Left;     /* 指向左子树 */
    BinTree Right;    /* 指向右子树 */
};

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: