数据结构与算法(七)-树

前言:回顾一下前面学习的内容,大概说了下数据结构中的线性结构,从物理存储方面来说又分为顺序存储和链式存储结构,各自有自己的优缺点,顺序存储结构读快写慢,链式存储结构写快读慢。但是这些数据元素之间的关系都为一对一的关系,而我们生活中关系不止是一对一,有可能是一对多,多对多,本篇先介绍一下一对多的存储结构,那么它是怎样存储才能保持它们之间的关系呢?

一、树定义

  生活中有很多这样的例子,一个强盛家族的族谱,必然是呈金字塔形状的,从一到多。就和树一样,一颗树通常由根部长出一个树干,然后从树干长出一些树枝,然后从树枝上又长出更小的树枝,而叶子则长在最细的树枝上。树这种数据结构正式像一颗倒过来的树木。

  所以对树的定义,即树是一种管理有像树干、树枝、树叶一样关系的数据的数据结构。

  树由节点(顶点)和边(枝)构成,并且有一个节点作为起始点。这个起始点称为树的根节点。从根节点上可以连出几条边,每条边都和一个节点相连。延伸出来的这些节点又可以继续通过边延伸出新的结点。这个过程中,旧的节点称作父结点,而延伸出来的新节点称作子结点。一个子节点都没有的节点就叫做叶子结点。另外,由根节点出发,到达某一个节点所要经过的边的个数叫做这个节点的深度,节点拥有的子树数称为该节点的度,树的度为各节点度的最大值。

  下图中,标着7、9和0三个数字的节点里,7就是父节点,9和0就是子节点。另一个图里,标记6的这个节点就是“根节点”,标记3、5、11、8、10、9、2、17、14的这些节点就是“叶子节点”,而图中12这个的深度是2。  

树(Tree)是n(n>=0)个节点的有限集。当n=0时称为空树,在任意一颗非空树中:

  • 有且仅有一个特定的称为根(Root)的节点;
  • 当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1、T2、、、Tm,其中每一个集合本身由是一棵树,并且称为根的子树(SubTree)。

  节点的子树的根称为节点的孩子(Child),相应的该节点称为孩子的双亲(Parent),同一双亲的孩子之间互称为兄弟(Sibling);节点的祖先是从根到该节点所经分支上的所有结点。

  总结一下树的相关概念:

节点的度:一个节点含有的子树的个数称为该节点的度;  
叶节点或终端节点:度为0的节点称为叶节点;  
非终端节点或分支节点:度不为0的节点;  
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;  
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;  
兄弟节点:具有相同父节点的节点互称为兄弟节点;  
树的度:一棵树中,最大的节点的度称为树的度;  
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;  
树的高度或深度:树中节点的最大层次;  
堂兄弟节点:双亲在同一层的节点互为堂兄弟;  
节点的祖先:从根到该节点所经分支上的所有节点;  
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。  
森林:由m(m>=0)棵互不相交的树的集合称为森林; 

二、树的存储结构

  上面已经对树的定义和概念做了个基本的认识,那么我们最关心的还是怎么在程序中实现该结构。

  在计算机中数据的存储有两种结构顺序存储和链式存储,顺序存储结构显然是不行的,而链式存储结构也是有缺点的,我们来看一下:

第一种:

  由于链式存储结构中的节点需含有子结点的引用或指针,但在树中子节点的不确定性导致无法无法固定具体节点中有几个引用或指针;

  Node节点结构示意图:

  我们可以根据树的度来确定Node节点的结构,比如树的度为3,那么Node结构中就由3个对自己引用。

  这样的话就会浪费很多空间,所以这样的结构不是最理想的存储结构;

第一种(改):

  对于上面的存储结构会过多的浪费存储空间,那么我们在结点中声明一个动态链表Nodes来存放可能的子节点Node;

  修改完后的结构如图:

第二种:

  使用数组+链表结合的方式来表示树:

  在第一版(改)中可以看到Node使用了集合,那么为什么不直接使用数组+链表的方式来构建呢,所以构建出来后就是上面图的样子(0的位置为ROOT根节点,从根节点出发,查看每个分支,构成树)。

  根据上面的存储方式,就可以完成对树的实现了;

三、树的分类

  树的种类分很多,根据是子节点之间否有序可分为有序树无序树

  根据子节点数量分为二叉树多路查找树

  而其中二叉树又分为斜二叉树满二叉树完全二叉树线索二叉树二叉排序树平衡二叉树红黑树哈夫曼树等。多路查找树分为2-3树2-3-4树B树B树变种树B+树等。

  有句话是这样说的,一木成,两木成林,三木成,所以有树就有森林,即n棵互不相交的树称为森

本系列参考书籍:

  《写给大家看的算法书》

  《图灵程序设计丛书 算法 第4版》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

3413
来自专栏彭湖湾的编程世界

【算法】赫夫曼树(Huffman)的构建和应用(编码、译码)

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

6135
来自专栏Jack的Android之旅

疯狂java笔记之树和二叉树

树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构

1732
来自专栏JavaEdge

二分查找复杂度分析实战演练

3538
来自专栏韦弦的偶尔分享

Swift 二叉树的最大深度- LeetCode

1102
来自专栏向治洪

基本数据结构概念

一、线性结构 顺序存储线性表:将元素依次存储在地址连续的存储单元中,物理上相邻; 链式存储线性表:将元素按照逻辑顺序链接在依次,不要求地址连续; ...

1996
来自专栏mathor

Morris遍历

 Morris算法遍历一棵二叉树,时间复杂度O(n),但是空间复杂度却只用神奇的O(1),下面说一下Morris遍历的流程,首先规定来到的当前结点即为cur

761
来自专栏mathor

树形DP

 假设现在有一棵树,我只要求出每个结点作为头节点对应子树的最大值和最小值,那么最终答案一定在其中,因此每个结点都有两个信息,最大值和最小值,我把这个信息封装为一...

1234
来自专栏我是攻城师

数据结构之树

树(Tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关...

982
来自专栏IT可乐

Java数据结构和算法(十一)——红黑树

  上一篇博客我们介绍了二叉搜索树,二叉搜索树对于某个节点而言,其左子树的节点关键值都小于该节点关键值,右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为...

4068

扫码关注云+社区

领取腾讯云代金券