第六章树

1,什么是树?
2,什么是树的度?
3,结点的层次
4 线性结构和树结构的比较
5 树的三种存储结构(双亲表示法,孩子表示法,孩子兄弟表示法)
6,二叉树的定义
7,满二叉树 和 完全二叉树
8 ,二叉树的性质
9, 二叉树的存储结构


1,什么是树?
树是n个结点的有序集合,n = 0 时为空树,
1,在非空树中,有且仅有一个可以称为根的结点。
2,n>1时,其余结点可分为m个互不相交的有限集,其中每一个集合本身是一颗树,并且称为根的子树。
注意子树一定是不可以相交的

2,什么是树的度?
1,树内各结点的度的最大值
2,结点拥有的子树数称为结点的度

3,结点的层次
从根开始定义,根为第一层。根的孩子为第二层,依次类推。
树中结点的最大层次称为树的深度或高度。

4 线性结构和树结构的比较

  • 线性结构
    第一个数据元素无前驱
    最后一个数据元素无后继
    中间元素,一个前驱一个后继
  • 树结构
    根结点,无双亲,唯一
    叶结点,无孩子,可以有多个
    中间结点,一个双亲,多个孩子。

5 树的三种存储结构(双亲表示法,孩子表示法,孩子兄弟表示法)

  • 双亲表示法
    1,连续的空间地址作储存结点
    2,data 数据域 指针域指向双亲
    缺点是找不到孩子结点
    改进方式是再增加一个指针域指向孩子结点
  • 孩子表示法
    设计思想:每个结点有多个指针域,每个指针指向一棵子树的根结点。这种方法叫多重链表表示法
    方案一:每个结点指针域的个数等于树的度
    当所有的结点度数大致相等时才会高效
    方案二:每个结点有三部分构成data 数据域,degree度域,指针域
    但是需要维护每个结点的度的数值,运算上带来时间上的损耗。
    孩子表示法:有2部分构成
    1,顺序存储结构存储一个一维数组,数据域放data,指针域指向该结点的孩子链表
    2,线性表中的元素,数据域放的是指向该元素在数组中的下标。指针域指向下一个孩子结点的指针
    缺点:找不到双亲 ,在表头结点里再加一个指针域,指向父母结点。
  • 孩子兄弟表示法
    听名字就知道它的指针域要指向孩子和兄弟
    孩子指针域:指向第一个孩子结点
    兄弟指针域:指向此结点右边的兄弟结点

6,二叉树的定义
二叉树是n个结点的有限集合,该集合或者为空集(空二叉树)或者由一个根结点和两颗互不相交的,分别称为根结点的左子树和右子树的二叉树组成。
左子树和右子树是有顺序的,次序不能颠倒。
7,满二叉树 和 完全二叉树
所有的分支结点都存在左子树和右子树。
对于一个n个结点的二叉树,如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全一致。
给每个结点按照满二叉树的结构逐层顺序编号,如果编号出现空档,说明不是完全二叉树。否则就是。
8 二叉树的性质
1在二叉树的第i层上最多有2^(i-1) 个结点
2深度为k的二叉树,至多有(2^k) - 1个结点
3n0 = n2 + 1
假设终端结点个数为n0,度为2的结点个数为n2,度为1的结点个数为n1
2个等式
n = n1 + n2 + n0
总线数 = n-1 = n1 + 2n2
4二叉树的深度为|log 2 n| + 1
|x|代表不大于x的最大整数
5对一颗有n个结点的完全二叉树,对任一结点i
5.1i = 1 ,结点i 是二叉树的根,无双亲。若i > 1则其双亲是结点|i / 2|
5.2如果2i > n 则结点i 无左孩子(结点i 为叶子结点)。否则其左孩子为结点2i
5.3如果2i + 1 > n 则结点i无右孩子
(5,1先推导完全二叉树的左侧左孩子的特点,2,再推导中间结点和左孩子的特点关系)
否则其右孩子是结点2i+ 1
9 二叉树的存储结构

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

推荐阅读更多精彩内容

  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,745评论 0 13
  • 1.树和二叉树的定义 (1) 树的定义 树是n (n≥0) 个结点的有限集。 n=0 时称为空树。在任意一棵非空树...
    yinxmm阅读 2,449评论 0 3
  • 目录 1、什么是树 2、相关术语 3、二叉树 3.1、二叉树的类型 3.2、二叉树的性质 3.3、二叉树的结构 3...
    我哈啊哈啊哈阅读 2,543评论 0 10
  • 树形结构是一种十分重要的数据结构。二叉树、树与树林都属于树形结构。 树形结构每个结点最多只有一个前驱结点,但可以有...
    cain_huang阅读 1,969评论 0 11
  • 四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,528评论 0 7