您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

408复习笔记——数据结构(五):树和二叉树

408考研笔记系列(五)(PS:本人使用的是王道四本书和王道视频)

数据结构:(五)树和二叉树

  • 前言
  • 一、简介
  • 二、主要内容
    • 1.树
    • 2.二叉树
  • 三、常见题型及易错题总结


前言

至此,我们学习了线性表、栈和队列、串这几种逻辑结构为线性的数据结构,也了解了他们的不同存储结构实现以及在不同存储结构下各种基本操作的实现;自此,我们将开始学习非线性逻辑结构的数据结构,首先也就是今天这一章的主角——树,也就是树形逻辑结构,包括这种逻辑结构的各种树;我喜欢把这一章说成种树,因为我们可以在这一章里面种出各种各样的树(当然有些树还是很恶心人的);
在这里插入图片描述


一、简介

正如前言中提到的,这一章中会主要便是在种各种各样的树,从最简单也是最常见的二叉树,再到二叉树的各种变种——完全二叉树、二叉排序树、平衡二叉树、哈夫曼树等等;再到由树变为多棵树组成的森林;这也预示着本章内容将会是非常多也是非常之重要的;需要引起高度重视,在考试中也是经常出现相关考题;

二、主要内容

1.树

首先,我们需要知道树是什么,其实跟我们常见的树形结构一样,有根结点,也有分支节点还有叶子结点,他们组成了一棵树的结构;就像下图一样
在这里插入图片描述
其中树的根结点是没有前驱的,除了根结点以外的所有结点都是有且只有一个前驱;树中一个结点的孩子个数称为该结点的度;树的路径长度是指树根到每个结点的路径长的总和,根到每个结点的路径长度的最大值应为树的高度减一;

树常见的考点有以下几个(这里不对以下结论做解释):

1. 结点数 = 总度数 + 1
2. 度为m的树是指各结点度的最大值为m;m叉树是指每个结点最多只能有m个孩子;前者是一定有,后者是可以有;
3. 度为m的树第i层至多有m^(i-1)个结点
4. 高度为h的m叉树至多有(m^h - 1)/(m - 1)个结点(等比数列求和)
5. 高为h的m叉树至少有h个结点;高为h的度为m的树至少有(h + m - 1)个结点(大概就是每一层只有一个结点的样子)
6. 具有n个结点的m叉树最小高度为log[n(m - 1)+1]

其中第一和第二个考点考察的频率相对较高

2.二叉树

二叉树便是一种逻辑结构为树结构的数据结构,正如他的名字一般,其特点便是每个结点至多只有两个子树,左子树或者右子树;就像这样:
在这里插入图片描述
二叉树有一些非常重要的性质,当然上面树的特点二叉树都是具备的,除此之外,还有一些二叉树特有的性质也是在考试中非常经常出现的考点:

非空二叉树的叶子结点n0等于度为2的结点数n2加1(n0 = n2 +1),这个性质的来源便是上述中树的第一个考点,因为二叉树只有度为0、1、2三种类型的结点,因此设度为0、1、2的结点数分别为n0、n1、n2,结合树的第一条性质得到等式:n0 + n1 + n2 = n1 + 2*n2 + 1,化简便得到n0 = n2 + 1;

以上适用于所有情况的二叉树,但是基于实际情况,就同栈和队列相较于线性表一般,二叉树也有一些特殊的二叉树——满二叉树、完全二叉树、二叉排序树以及平衡二叉树等,这里主要介绍满二叉树和完全二叉树,剩下的树会在接下来的章节继续介绍;

这里放一张满二叉树的图片:
在这里插入图片描述
没错,图如其名,满二叉树就是满的二叉树;

那么完全二叉树呢?这个感觉看名字就和满二叉树一样呀!
那这里放一张完全二叉树的图片:
在这里插入图片描述
是的,这两张图都是完全二叉树!大家肯定会发现第一张图这不就是满二叉树嘛,没错,满二叉树也是一种完全二叉树;完全二叉树的定义是这样的:高度为h、有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中的1~n的结点一一相对应时,称为完全二叉树;
在这里插入图片描述

从上面这张图中,我们可以看到F所在的位置在右图是与满二叉树相对的,而左图是不对应的,右图正式我们的完全二叉树,大家可以结合下图看一下完全二叉树以及满二叉树的相同与不同之处

在这里插入图片描述
那完全二叉树和满二叉树的考点又是什么呢?

  1. 第一个考点就是二叉树的考点,不过会结合下面的考点一起考察
  2. 当完全二叉树按1、2、3……n依次编号,结点 i 的左孩子编号为2i ,右孩子编号为2i + 1(如果他们的左右孩子都存在的情况下),若已知孩子结点的编号,反之可以得到父亲结点的编号;
  3. 满二叉树第 k 层有2^(k-1)个结点
  4. 完全二叉树的度为1的结点个数为0或者1,因此结合第一个考点,在已知结点总数的情况下是可以得到完全二叉树的叶子结点和度为2的结点数量;

至此我们已经知道了二叉树和二叉树的特殊情况,那么按照数据结构的三个要素,接下来,我们需要看一下二叉树的存储结构,跟线性表一样,二叉树的存储结构也可以分为顺序存储结构和链式存储结构‘;

顺序存储结构的关键就在于我们在满二叉树中关于孩子与父亲之间的编号的关系,但是有一个很大的问题便是当我们存储一个普通二叉树时,如果树比较高,但是树中元素数量不多时,由于我们需要这个二叉树高度的满二叉树所有元素的存储空间,因此空间的利用率会十分低下,导致存储密度很低,浪费存储空间;如下图所示:
在这里插入图片描述
所以一般在二叉树存储时,我们都会采用链式存储的方式来存储二叉树,又称二叉链表;像这样:
在这里插入图片描述
我们的二叉树结点代码会这样写:

// 用于定义一个二叉树结点
typedef struct BiTNode{
	int data;
	struct BiTNode *lchild, *rchild;// 分别指向二叉树的左结点和右结点
}BiTNode,*BiTree;

有时为了实际需要,会加上一个指向头结点的指针,这里的二叉链表有一个非常重要的性质:
n个结点的二叉链表中,含有n + 1个空链域,就是指针指向为空;大家可以结合上面的二叉链表图片理解一下;

之后,我们便会开始我们的第三个要素:运算,展开新的篇章,也会给大家种新的树;


三、常见题型及易错题总结

串和模式匹配算法的答案:C

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
答案见下一章


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进