学习笔记之树的学习

学习主题:数据结构之树及树的遍历(一)

基本概念

的定义:树是n个结点的集合,集合中有一个成为根的特殊结点,在根结点下分布着一些互不相交的集合,每个集合又是一个树,这些树成为根结点的子树。如图1-1所示。


图1-1

从树的定义中不难看出其中采用了递归的描述,换一个说法就是子树和根结点构成一个新的树,树的子树也还是树。

父结点,子结点,兄弟结点:

每个结点的子树成为该结点的子结点(儿子),相应的该结点成为子结点的父结点(父亲),具有同一父结点的结点成为兄弟结点,如图1-2所示,B是A的子结点,A是B的父结点,B与C是兄弟结点。

叶结点:一个结点若没有子结点,则称该结点为叶结点,图1-2中的叶结点有D,E,F,G,I,K。(自己写的)

结点的度:一个结点的子树的数量称为结点的度,如图1-2,结点A有B,C,D三个子结点,则A的度为3。

树的度:树中任意结点的度的最大值,如图1-2,结点A和结点C的度最大,为3,则该树的度为3。

树的深度:指的是树的最大层数,如图1-2,该树的深度为4?5??有待考证?

层:根结点在第一层,以此类推,如图1-2,结点H在第三层。

高度:叶结点的高度为1,以此类推,根结点的高度最高。

森林:多个树组成的为森林,即将图1-1和图1-2放在同一张图中,但并不相连。


图1-2

在树中,有且仅有一个结点没有父结点,即该树的根结点;除了根结点之外的其余结点,每个结点有且仅有一个父结点,但该结点可以有无数的子结点。如图1-3和图1-4,这两张图都不是树。


图1-3
图1-4

特殊的树

1、空树:若一棵树没有结点,则该树为空树。

2、若一个树有且仅有一个结点,则该结点为根结点。

3、斜树:所有节点只有左节点或右节点,如图1-5所示。


图1-5

4、二叉树:二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。如图1-6所示。


图1-6

5、B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。

6、Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。

重点学习二叉树、B树和Trie树及其遍历。

树的表示法

1、双亲表示法:每个结点存储该结点的数据及其父结点在数组中的下标。

2、孩子表示法:全部结点组成一个数组,每个数组指向一个单链表,存放其子结点。如图1-7所示。


图1-7

3、双亲孩子表示法:如图1-8所示。


图1-8

4、孩子兄弟表示法:如图1-9所示。


图1-9

此方法的好处在于能够将一个多叉树(即拥有子结点个数大于2的结点)转换成一个二叉树,是将复杂的树转换成二叉树的很好的一个办法。

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

推荐阅读更多精彩内容

  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,183评论 0 25
  • 树和二叉树 1、树的定义 树(Tree)是由一个 或 多个结点 组成的有限集合T,且满足: ①有且仅有一个称为根的...
    利伊奥克儿阅读 1,349评论 0 1
  • 原文链接 B树 1.前言: 动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(...
    非典型程序员阅读 1,148评论 0 3
  • 一. 算法之变,结构为宗 计算机在很多情况下被应用于检索数据,比如航空和铁路运输业的航班信息和列车时刻表的查询,都...
    Leesper阅读 6,834评论 13 42
  • 数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比,二叉树有如下特点: 每个结点最多只有两棵子...
    sunhaiyu阅读 6,426评论 0 14