数据结构之二叉树

一、树
1.1树形结构


image.png

1.2 基础知识
以多叉树为例:
节点:树上每一个元素都称为节点。例如:1,2,3,4,5,6,21,22,31......
根节点:一棵树只有一个根节点,例如:1
父节点:例如:1可以称之为2,3,4,5,6的父节点
子节点:例如:2,3,4,5,6可以称之为1的子节点
兄弟节点:同一个父节点下面的节点。例如:21,22/51,52

一棵树可以没有任何节点,称为空树。
子树:将下面的节点联合起来看成一颗全新的树。子树可分为左子树和右子树。
节点的度:子树的个数。例如:1--->5;2--->2;3--->1;
树的度:所有节点度中最大值
叶子节点:度为0的节点:例如:21,221,222,223,51......
非叶子节点:度为非0的节点。

层数:根节点在第1层,根节点的子节点在第2层,以此类推......
节点的深度:从根节点到当前节点的唯一路径上的节点总数。例如:2经历了1-2所以深度为2,31经历了1-3-31所以深度为3

节点的高度:从当前节点到最远叶子节点的路径上的节点总数。例如:2--22-221,所以高
度为3

树的深度:所有节点深度的最大值
树的高度:所有节点高度中的最大值
注意:一般来说,树的深度等于树的高度

有序树:树中任意节点的子节点之间有顺序关系
无序树:树中任意节点的子节点之间没有顺序关系
二、二叉树
2.1 二叉树(有序树)
特点:1.每个节点的度最大为2(最多拥有2棵子树)
2.左子树和右子树是有顺序的
3.即使某节点只有一棵子树,也要区分左右子树

2.2 二叉树的性质
1.非空二叉树的第i层,最多有2^(i-1)个节点(i>=1)
2.在高度为h的二叉树上最多有2^h-1个节点(h>=1)
3.对于任何一颗非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2,则:n0=n2+1
假设度为1的节点个数为n1,那么二叉树的节点总数n=n0+n1+n2
二叉树的边数T=n1+2*n2=n-1=n0+n1+n2-1
化简得:n0=n2+1

2.3 真二叉树和满二叉树
真二叉树:所有节点的度都要么为0,要么为2


image.png

满二叉树:所有节点的度都要么为0,要么为2,且所有的叶子节点都在最后一层。


image.png

在同样高度的二叉树中,满二叉树的叶子节点数量最多,总节点数量最多
满二叉树一定是真二叉树,真二叉树不一定是满二叉树

假设满二叉树的高度为h(h>=1)
第i层的节点数量:2^(i-1)
叶子节点数量:2^(h-1)
总结点数量n=2^h-1
h=log2(n+1)

2.4 完全二叉树
2.4.1 概念
完全二叉树:叶子节点只会出现在最后2层,且最后1层的叶子节点都靠左对齐。


image.png

完全二叉树从根节点到倒数第二层是一颗满二叉树
满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

2.4.2 性质
1.度为1的节点只有左子树
2.度为1的节点要么是1个,要么是0个
3.同样节点数量的二叉树,完全二叉树的高度最小
4.假设完全二叉树的高度为h(h>=1),那么
至少有2(h-1)个节点(20+21+22+......+2^(h-2)+1)
最多有2h-1个节点(20+21+22+......+2^(h-1),满二叉树)
h-1<=log2(n)<h(求h,log2(n)向下取整+1)

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

推荐阅读更多精彩内容

  • 前言 二叉树是数据结构中一种重要的数据结构,也是树表家族最为基础的结构,包括完全二叉树、满二叉树、二叉查找树、AV...
    复旦猿阅读 412评论 0 1
  • 一、什么是二叉树? 二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两...
    沉淀者阅读 459评论 0 1
  • 一、基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。 性质: 1、非空二叉树的第n层上至多有2^...
    沐心沐翡阅读 664评论 3 0
  • 前言 大家都知道,链表适合需要频繁插入、删除数据的场景。但虽然说链表的插入、删除操作比数组性能好很多,但是在插入、...
    复旦猿阅读 1,288评论 2 2
  • 推荐指数: 6.0 书籍主旨关键词:特权、焦点、注意力、语言联想、情景联想 观点: 1.统计学现在叫数据分析,社会...
    Jenaral阅读 5,705评论 0 5