二叉树的性质概念脑图思维导图

夕阳下的美眉

2023-12-09

浏览量: 51

数据存储

存储结构

存储方式

二叉树的概念，性质和存储结构等内容讲解

树图思维导图提供《二叉树的性质概念脑图》在线思维导图免费制作，点击“编辑”按钮，可对《二叉树的性质概念脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：a18648a6cf02e58e15a3f1ea53d5536c

思维导图大纲

树的性质和概念

树的概念

树是由n（n>=0)个元素组成的有限集合

当n=0时，树为空树

每个元素称为结点

非空树

有且仅有一个首结点，即根结点

除根结点之外，每个结点都有唯一的前驱结点

每个结点都有0个或多个后继结点

当n>1时，除根结点之外的其他结点可以被划分为m（m>0）个互不相交的有限集合，这些树称为根结点的子树

子树：根结点的分叉树

度：一个结点的字数个数称为结点的度，树中各结点的度的最大值称为这棵树的度

叶结点：度为0的结点，度不为0的结点称为分支结点

内部结点：根结点以外的分支结点（去除根结点和度为0的点）

父节点：一个结点的前驱结点为该结点的父结点

子结点：一个结点的后继结点为该结点的子结点

兄弟结点：同一个结点的多个子结点互称为兄弟结点

若规定一棵树中根结点的层次为1，其他结点的层次等于它的父结点的层次加1，则一棵树中所有结点的层次的最大值称为树的深度。

高度：由底向上

深度：自顶向下

二叉树的概念

二叉树：它的每个结点最多有两个孩子，称为左孩子和有孩子

空二叉树：n=0

二叉树中每个结点的度必须小于等于2

满二叉树：所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上

每层结点个数必须满足2^n-1个

满二叉树是完全二叉树，完全二叉树不是满二叉树

满二叉树的特点

叶子只能出现在最下一层

非叶子结点的度一定是2

在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完全二叉树：从左到右依次把格子占满，按顺序

完全二叉树的特点

叶子结点只能出现在最后一层或倒数第二层

最下层叶子结点一定集中在左部连续位置

倒数第二层如果有叶子结点，一定出现在右部连续位置

同样结点数的二叉树，完全二叉树的深度最小

二叉树的性质

一般二叉树的性质

在非空二叉树的i层上，至多有2^（i-1）个结点

在深度为K的二叉树上最多有2^k -1个结点

对于任何一颗非空的二叉树，如果叶结点个数为n0，度数为2的结点个数为n2，则有n0=n2+1

n0：度为0的结点个数

总结点个数：n=n0+n1+n2=2n2+n1+1

在一颗只有度为0和度为2的二叉树中高度（深度）与结点个数的关系：2h（k）-1=n

h:高度，k：深度

完全二叉树的性质

具有n个结点的完全二叉树的深度为log2n+1

在深度为k的满二叉树中的结点数量是2^k -1=n,完全二叉树结点数量肯定最多2^k -1,同时完全二叉树倒数第二层肯定是满的，所以完全二叉树的结点数至少大于少一层的满二叉树，为2^k -1

n个结点的完全二叉树，对任意一层的结点i有

如果i=1，则该结点是二叉树的根，无父结点，如果i>1，则父结点为i/2向下取整

如果2i>n，那么结点i没有左孩子，否则左孩子为2i

如果2i+1>n，那么结点没有右孩子，否则其右孩子为2i+1

二叉树的存储结构

存储

顺序存储结构

缺点：浪费空间

优点：找一个结点的双亲和孩子较容易

链式存储结构

优点：节省存储空间，结构灵活，操作方便

二叉树的顺序存储：是用一组连续的存储单元存放二叉树中的结点

链式存储：是用链表来表示一颗二叉树，即用链来指示元素的逻辑关系

二叉树的遍历

层次遍历：从左到右，从上到下

先序遍历：根左右（NLR）

中序遍历：左根右（LNR）

后序遍历：左右根（LRN）

先序遍历的非递归实现

根据先序遍历的顺序，先访问根结点，再访问左子树，后访问右子树

边访问边输出

二叉树的构造

定义

二叉树是一种特殊的树形结构，每个节点最多只有两个子节点，通常称为左子节点和右子节点。

构造方法

定义节点

节点包括数据域和指针域

构造方法步骤

1.创建根节点

2.递归构造左子树和右子树，并将它们连接到根节点上

遍历方式

前序遍历

1.根节点

2.左子树

3.右子树

中序遍历

1.左子树

2.根节点

3.右子树

后序遍历

左子树

右子树

根结点

二叉树遍历的应用

统计二叉树中叶子结点的个数：先统计二叉树左子树的叶子结点个数，然后再统计右子树的叶子结点个数，把左右子树中的叶子结点数加起来，就得到二叉树中所有叶子结点的个数

计算二叉树的高度：先统计二叉树左子树的高度，然后再统计右子树中的高度，通过比较左右子树的高度，将较大的值加上1（根结点的高度）。

霍夫曼树

路径：从一个结点往下可以到达的孩子或子孙结点之间的通路。

路径长度：通路中边的数目称为路径长度

权：将树中结点赋予一个有着某种含义的数值，则称这个数值为该结点的权

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度为：所有叶子结点的带权路径长度之和

并查集

存储结构：用一维数组或链式存储来实现

数据结构定义

struct Node

{

Datatype data；

int parent；

}

合并：将两个不相交的子集合并成一个大集合

合并代码

void union （interesting root，int root2）

{

s[root2].parent = root1;

}

查找操作

查找某个元素所在的集合，返回该集合的代表元素，即根结点

int find(int x)

{

if (s[x].parent < 0)

return x;

else

return find(s[x].parent);

}

路径压缩：并查集中的子树只用来表示各个元素是否在同一集合，没有元素排列次序的要求，所以完全可以把一个较高的树变为较低的树。

设计概论思维脑图思维导图

知足的达芬奇

1.74

树图思维导图提供《设计概论思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《设计概论思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：deb0532980b57f8781635ceaaa393fb9

0513早会整理思维脑图思维导图

U245265618

2.94

树图思维导图提供《0513早会整理思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《0513早会整理思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：70912fe45647449127e821bdf2b56453

思维导图模板

IT互联网

产品结构

正文

相似思维导图模版

思维导图模版推荐

首页

我的文件

我的团队

个人中心

二叉树的性质概念脑图思维导图

思维导图大纲

相关思维导图模版

﻿树的性质和概念

﻿二叉树的概念

﻿二叉树的性质

﻿二叉树的存储结构

﻿二叉树的遍历