首页 > 编程学习 > 【数据结构】树和二叉树以及经典例题

【数据结构】树和二叉树以及经典例题

发布时间:2022/11/19 0:28:49

目录

  • 1.树的基本概念
    • 1.1 树的特点
    • 1.2 树的一些相关概念
    • 1.3 树的表示
      • 1.3.1 那种结构表示树最优?(不是二叉树,就是普通的树)
    • 1.4 树在实际中的运用(表示文件系统的目录树结构)
  • 2. 二叉树(重点!!!)
    • 2.1 二叉树的概念
    • 2.2 特殊的二叉树
    • 2.3 完全二叉树的范围
    • 2.4 二叉树的性质
  • 3.例题
    • 3.1
    • 3.2
    • 3.3

1.树的基本概念

在认识数据结构里的“树”之前,我们先来看看现实生活中的树

在这里插入图片描述

我们现实生活中的树有什么特征?
有树根,有枝节,有叶子。
编程来源于生活,我们数据结构里的“树”也有这些特征。

在这里插入图片描述
概念如下:

树是一种非线性数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 ————百度百科

注意 “非线性” 这个词,表面了该数据结构是一对多或者多对多的关系

1.1 树的特点

1.有一个特殊的结点,称为根结点,根节点没有前驱结点(就是最上面的结点)
2.除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

我们主要来看第二条:
“互不相交的集合”,就是结点之间不能有交集
如下图

在这里插入图片描述

其实,仔细观察的话,我们可以发现,这个说法还能换成:
树结构之间不能有回路

在这里插入图片描述

这几个点之间产生了回路,所以就不是树。
再来看看第二个特点:子树
就是,一颗大的树里面,包含了多个子树。
如图:

在这里插入图片描述

图中圈出来就是子树,这些子树还能被分为更小的子树。
再来刨析第二条特点:
每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
“前驱”“后继”是什么?
在上面树的逻辑图中   (仔细想想什么是逻辑图,后面会讲)
我们可以看到,除了第一层,和最后一层外,中间的结点都连了相应的结点
连接在上面的叫“前驱”,连接在下面的叫“后继”
根结点只有后继没有前驱,
最后一层的结点(也叫叶结点),只有前驱,没有后继
所以总结为:
 子树的根结点只有一个前驱,有0个或者多个后继

1.2 树的一些相关概念

在这里插入图片描述

概念挺多的,我们这里划分一下分为常用的和不常用的
常用的并且重要的:
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推
树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
不常用的:
非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
森林:由m(m>0)棵互不相交的树的集合称为森林;(就是两棵或多棵互不相干的树)

1.3 树的表示

还记得我们上面提到的逻辑图吗?

在这里插入图片描述

这种能形象地表示数据结构的图,我们称为逻辑图。
比如链表,那种两个结点之间有箭头指向的图,以及我们上面这幅图都是逻辑图
其最大的特点就是,这种图是我们想象出来的,真实结构并不是这样的
所以在计算机里,我们还要利用更底层的数据结构实现它。
比如利用数组实现树,或者链表实现树

1.3.1 那种结构表示树最优?(不是二叉树,就是普通的树)

如果仅仅是一棵普普通通的二叉树,每个结点最多连两个结点,那么我们分别创建
左孩子指针和右孩子指针就能表示了。
但是,这里是树,也就是说一个结点可能连接两个以上的结点,
可能3个,4个,5个,6...
那我们可以利用“指针数组”去实现这么多的结点。
但是,有没有更好的方法?
同样只利用两个指针就可以一直表示下去?
思考一下
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
//孩子兄弟表示法
typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

在这里插入图片描述

有牛人发明了这种“孩子兄弟表示法”,能完美实现2个度以上的树
一个结点里存有 “孩子”和“兄弟”
“孩子“指向自己的下一个结点,没有”兄弟“就不用指向
”孩子“指向的结点,也有自己的”孩子“和”兄弟“,然后可以可以无限表示下去了。
仔细感受一下,牛人发明的这种方法,不得不佩服。

1.4 树在实际中的运用(表示文件系统的目录树结构)

在这里插入图片描述

2. 二叉树(重点!!!)

2.1 二叉树的概念

在这里插入图片描述

在这里插入图片描述

在上面学习了树以后,我们接下来看看二叉树
二叉树:由一个根节点加上两棵别称为左子树和右子树的二叉树组成

在这里插入图片描述

注意:
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的:

在这里插入图片描述

2.2 特殊的二叉树

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是
说,如果一个二叉树的层数为K,且结点总数是2^k - 1 ,则它就是满二叉树。
(注意是结点总数)

记住这个层数为k时,结点总数是 2 k − 1 2^{k}-1 2k1,非常重要,后面需要用到

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
简单理解完全二叉树就是,最后一层可以满,满了就是满二叉树。也可以不满,不满的话起码结点从左往右排好

在这里插入图片描述

2.3 完全二叉树的范围

因为满二叉树是一种的特殊的完全二叉树,所以完全二叉树的总结点最多是 2 k − 1 2^{k} -1 2k1,(k表示总层数)

那么最少是多少?
最少的话是不是最后一层只有一个结点
既然这样的话,那么最后一层的上一层总结点数是不是 2 k − 1 − 1 2^{k-1} -1 2k11
那么上一层是满的,再 +1 是不是就是最后一层加一个结点
答案就是:
2 k − 1 2^{k-1} 2k1

所以完全二叉树的总结点范围就是
2 k − 1 2^{k-1} 2k1 ~ 2 k − 1 2^{k} - 1 2k1 (k是总层数)

2.4 二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 2 ( i − 1 ) 2^{(i-1)} 2(i1)个结点. (注意这里是某一层上的最多结点)

  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数 2 h − 1 2^{h}-1 2h1 (就是满二叉树)

  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0= n2 +1(度为0的结点永远比度为2的结点多1,这个结论也挺重要的,自己画图理解一下)

  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1)

  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
    5.1 若i>0i 位置节点的双亲序号(i-1)/2;i=0,i为根节点编号,无双亲节点
    5.2 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
    5.3 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子

3.例题

光看性质是不是觉得很乱,我们来做几道题就明白了。

3.1

在一颗度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,则叶子结点有( )个

解答:
设该树共有n个结点,这是一棵度为3的树,
则 n = n0 + n1 + n2+n3 … …(1)
有n个结点的树的边有 n - 1 条
根据度的定义,总边数与度之间的关系为
n - 1 = n0* 0 + n1 * 1 + n2 * 2 + n3 * 3 … … (2)

(1)(2)式联立可得 n0=n2+2 * n3 + 1
叶子结点就是度为0的点
所以答案就是 n0 = 1 + 2 * 2 + 1 = 6

3.2

一颗拥有1000个结点的树度为4,则它的最小深度是()

解答:
如果这棵树每一层都是满的,则它的深度最小,

n层k叉树的总结点个数 ( k n − 1 k^{n}-1 kn1) / (k - 1)
所以树的度为4,表示4叉树,
4 n − 1 4^{n}-1 4n1)/ 3
当n = 5,最大结点数为 341
当n = 6,最大结点数为 1365

所以最小深度为6

3.3

一颗完全二叉树有1001个结点,其叶子结点的个数是()

解答:
这里需要用到 二叉树的性质 3
n0 = n2 + 1,度为0的结点永远比度为2的结点多一个

这是一棵二叉树,度可能是0,1,2,分别用 n0,n1,n2表示

n= n0+n1+n2

另外,在完全二叉树中,如果节点总个数为奇数,则没有度为1的节点,如果节点总个数为偶数,只有一个度为1的节点。(自己画个图能推出来)
那么1001个结点,没有度为1的结点

所以 n = n0 + n0 - 1 = 1001
所以 n0 = 501
所以叶子结点就是 501

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式