原来你是这样的数据结构之树结构

什么是树结构

树结构是一种描述非线性层次关系的数据结构,其中主要的是树的概念,树是n个数据结点的集合,在该集合中包含一个根结点,根结点之下分布这一些互不交叉的子集合,这些子集合是根结点的子树,它的结构特征如下:

  • 在树结构中,有且仅有一个结点没有直接前驱,这个前驱就是树的根结点.
  • 除根结点外,其余每个结点有且仅有一个直接前驱.
  • 每个结点可以有任意多个直接后继.

上图就是一个典型的树结构,就像现实中树的根系,其中A结点是树的根结点,根结点A有三个直接后继结点B,C,D,而结点B,C,D他们都只有一个前驱结点A.

一个树结构也可以是空的,此时空树中没有数据结点,也就是一个空集合,如果树结构中仅包含一个结点,那么这也是一个树,树根便是该结点自身。

树的基本概念

父结点和子结点:每个结点子树的根称为该结点的子结点,响应的,该结点称为其子结点的父结点。
兄弟结点:具有同一父结点的结点称为兄弟结点。
结点的度:一个结点所包含子树的数量。
树的度:是指该树所有结点中最大的度。
叶结点:树中度为零的结点称为叶结点或终端结点。
分之结点:树中度不为零的结点称为分之结点或非终端结点。
结点的层数:结点的层数从数根开始计算,根结点为第一层,依次向下为第2,3,....层(树一种层次结点,每个结点都出在一定的层次上)。
树的深度:树中结点的最大层数称为树的深度。
有序数:若树中各结点的子树(兄弟结点)是按一定次序从左向右排列的,称为有序树。
无序树:若树中各结点的子树(兄弟结点)未按依定次序排列,称为无序树。
森林:n棵互不相交的树的集合。

二叉树

在树结构中,二叉树是最简单的一种形式。在研究树结构时,二叉树是树结构中的重点。二叉树的描述相对简单,处理也相对简单,而且更重要的是任意的树都可以转换成相对应的二叉树。因此,二叉树是所有树结构的基础。

1.什么是二叉树

二叉树是树结构的一种特殊形式,它是n个结点的集合,每个结点最多只能有两个子结点,二叉树的子树仍然是二叉树。二叉树的一个结点对应的两个子树分别称为左子树和右子树。由于子树有左右之分,因此二叉树是有序树。

普遍的树结构中,结点的最大度数是没有限制的,而二叉树结点的最大度数为2,另外,树结构中没有左子树和右子树的区别。

一个二叉树的结构可以是空的,此时空二叉树中没有数据结点,是一个空集合。如果二叉树结构中仅包含一个结点,这么这也是一个二叉树,树根便是该结点本身。

二叉树还可以进一步细分为两种特殊的类型:
满二叉树和完全二叉树。

满二叉树:

满二叉树即在二叉树中除最下一层的叶结点外,每层的结点都有两个子结点。

完全二叉树

完全二叉树记载二叉树中除二叉树最后一层歪,其他各层的结点数据都达到最大个数,且最后一层结点按照从左向右的顺序连续存在,只缺最后一层右侧若干结点。

2.完全二叉树的性质

对于完全二叉树,若树中包含n个结点,假设这些结点按照顺序方式存储,那么,对于任意一个结点m来说,具有如下性质。

  • 如果m!=1,则结点m的父结点的编号为m/2;
  • 如果2m<=n ,则结点m的左子树根结点编号为2m;若r*m>n,则没有左子树,也没有右子树;
  • 如果2m+1<=n,则结点m的右子树根结点编号为2m+1;若2*m+1>n,则无右子树。
  • 对于完全二叉树,其深度为[log2n]+1.

这些基本性质展示了完全二叉树结构的特点,在完全二叉树的存储方式及运算处理上都有重要意义。
按照数据的存储方式,树结构可以分为顺序存储结构和链式存储结构。

3.二叉树的顺序存储

顺序存储方式是最基本的数据存储方式。和线性表类似,树结构的顺序存储一般采用一维数组来表示,这里的关键是定义合适的次序来存放树中各个层次的数据。

image

先来分析完全二叉树的顺序存储,上面的这个图每个结点的数据都是字符类型,如果采用顺序存储方式,可以将其按层来存储,即先存储根结点,然后从左往右一次存储下一层结点的数据,直到所有的结点数据完全存储。
[A,B,C,D,F,G,H]
上述二叉树顺序存储结构的数据定义,可以采用如下形式:

static final int MAXLEN = 100;              //最大结点数
char [] SeqBinTree = new Char9[MAXLEN];     //定义保存二叉树数组

二叉树的链式存储

与线性结构的链式存储类型,二叉树的链式存储结构包含结点元素及分布指向左子树和右子树的引用。典型的二叉树的链式存储结构如下:

class ChainTreeType
{
    char NodeData;                          //元素数据
    ChainTreeType LSonNode;                 //左子树
    ChainTreeType RSonNode;                 //右子树
}

ChainTreeType root = null;                  //根结点

有时候,为了后续计算的方便,也可以保存一个该结点的父结点的引用,此时二叉树的链式存储结构包含了结点元素,指向父结点的引用及分别指向左子树和右子树的引用,这种带父引用的链式存储结构代码如下:

class ChainTreeType
{
    char NodeData;                          //元素数据
    ChainTreeType LSonNode;                 //左子树
    ChainTreeType RSonNode;                 //右子树
    CharinTreeType ParentNode;              //父结点引用
}

ChainTreeType root = null;                  //根结点

上述就是树结构及二叉树的基本内容,下一篇我们用链式存储结构来实现一个二叉树。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容