树和二叉树的概念
文章目录[*]前言
[*]树的概念
[*]树的表示
[*]树结构在实际中的运用
[*]二叉树的概念
[*]特殊的二叉树
[*]
[*]满二叉树
[*]完全二叉树
[*]二叉树性质
[*]二叉树的存储结构
[*]
[*]次序存储
[*]链式存储
[*]认识树结构的习题训练
前言
陆陆续续的,我们已经学完了次序表,链表,栈和队列等线性的数据结构,而今天博主要介绍的就是树形的数据结构,和线性数据结构一样,我们先介绍什么是树形结构以及树的特点
树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有条理关系的集合。把它叫做树是因
为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
如下图所示:
下面是介绍树的一些常用术语概念,博主先上一张图,方便大家区分各个术语
[*] 根结点:没有双亲节点的结点,比如结点A.
[*] 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如B是A的孩子节点
[*] 双亲结点若一个节点含有子节点，则这个节点称为其子节点的父节点,如A是B的父节点
[*] 节点的度:一个节点含有的子树的个数称为该节点的度； 如A的度为6
[*]
[*] 叶节点或终端节点度为0的节点称为叶节点, 如B、C、H、I等节点为叶节点
[*] 非终端节点或分支节点度不为0的节点； 如D、E、F、G等节点为分支节点
[*] 兄弟节点具有相同双亲节点的节点互称为兄弟节点； 如I,J是兄弟结点,K,L,M是兄弟结点,H,I不是兄弟结点
[*] 树的度一棵树中，最大的节点的度称为树的度； 如树的度为6(因为A的度是所有结点中度最大的,结果为6)
[*] 节点的条理从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
[*] 树的高度或深度树中节点的最大条理； 如上面的树的高度为4(即具有四层)
[*] 节点的祖先从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
[*] 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
树的表示
前面简朴介绍了树的概念,但是树毕竟是逻辑结构,我们想要实现它,该怎么做呢?最常用的是借助链表,用孩子兄弟表示法进行演绎树结构.如下图:
结点的代码构建如下:
typedef int DataType;
typedef struct node
{
struct node* child; //指向左孩子结点
struct node* brother; //挨个指向兄弟结点
DataType data; //存储当前结点数据
}node; 树结构在实际中的运用
树结构在实际生活中运用最多的就是文件结构,如下示意图:
二叉树的概念
符合树的概念,但特点是树的度最大只能为2,也就是说每个结点的子节点最多只能有两个.
二叉树特点:
[*]每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
[*]二叉树的子树有左右之分，其子树的序次不能颠倒。
特殊的二叉树
满二叉树
**概念:**每一层的结点都到达最大值,且第n层的结点数目符合公式2^(n-1),层数是从1开始数
完全二叉树
概念: 对于层数(n>=2)的树,其n-1层符合满二叉树,第n层结点数目必须从左向右都符合222...1特性,即有且只有1个单结点,位置处于末尾,该单结点一定是左孩子结点.
二叉树性质
[*] 若规定根节点的层数为1，则一棵非空二叉树的第n层上最多有2^(n-1) 个结点.
[*] 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1(该公式由等比数列求和得到).
[*] 若规定根节点的层数为1，具有n个结点的满二叉树的深度h=Log2(n+1)
[*] 恣意一颗二叉树,假设度为0的结点数目为n0,度为2的结点数目为n1,则满意 n0= n1+1;
二叉树的存储结构
次序存储
即用数组进行存储,在逻辑结构上是二叉树,在物理结构上是一个数组,用数组的下标进行表示每个结点,从0开始,如下图:
次序存储的特点:
[*]只适用二叉树,因为二叉树要求即使空结点也存储,所以空间不会浪费,但是其他树结构就会造成严重空间浪费
[*]次序存储二叉树一般适用于堆排序
链式存储
链式存储有两种:
[*]二叉链:拥有三个域,分别是左右指针域和数据域,左右指针域分别指向左孩子和右孩子
[*]三叉链:拥有四个域,分别是左右指针域以及双亲域和数据域,左右指针域同上,双亲域指向双亲节点.
示意图如下:
二叉链结点构建代码:
typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
}; 三叉链结点构建代码:
typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
}; 认识树结构的习题训练
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386 答案:
[*]B,原因二叉树中 叶子结点数目 = 度为2结点数目 + 1
[*]C,因为次序结构的优点是 尾删尾插方便,但是队列用的更多的是 头插头删
[*]A,一颗满二叉树的结点数目是2n-1,现在所有结点是2n,相称于在满二叉树后增加了一个结点.所以为n
[*]B,2^9的结果是512,是一个满二叉树,531比512多19个结点,所以高度是10.
[*]B,前9层是满二叉树结点有512,剩余255叶节点,但是这255个结点有254个结点有双亲,即有127个度为2结点,然后前8层的结点都是度为2结点,2^8-1即是255,所以度为2的结点为255+127=382,那么剩下的结点为767-382=385(包含叶节点和一个度为1结点),所以答案是384
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]