0%

tree

为什么要学习树?

相信大家都听说过一些带的名字,比如二叉搜索树,最小生成树……,这些都是以离散数学中的最简单的为基础的。把树学习好,也能给将来数据结构的学习打下了坚实的基础。

什么是树?

定义1

1.点与点没有成环

2.互相连通

3.简单图

如果无法理解的话,不妨拿生活中的树来举例子

一棵树,首先枝条不能长成环

其次,不能说一棵树在东边长一部分,在西边长一部分,这样也不能叫做一棵树

定义2

图中的任意两点之间有且只有一条简单路,叫那么这个图就是树

这个也很好想象,如果一个图里面点与点已经形成了一个环,那么肯定存在两点,能够用不止一条简单路来连接

跟生活中的树一样,图中的树也有叶子

在树中度数为1的点称为叶

一个树图中一定会有叶

实际上,在图论中的树对叶的定义更加的宽泛

例如,现实生活中的树,到冬天就没有叶子了

但是,在图论中,如果一个树没有叶子,那它必须要成环,但这又与树的定义相违背了,所以一棵树一定会有叶

树的边数

在树中,自环,多重边,以及点与点之间形成环都已经被禁止了

所以,树具有了额外的一条的性质

有n个点的树,一定有n-1条边

最小生成树

所谓生成树,就是要把原本不是树的图,删成树

这里的最小,首先要确定是哪方面最小

比如想要最便宜的生成方法,和想要看到最好风景的生成方法肯定不一样

假如现在甲方的要求是最便宜的生成方法,那么,我们首先对道路成本进行评估

得到不同道路的分数后,就可以开始生成最小树了

Prim’s algorithm

用一句话概括这个算法,就是:走一步看一步

先随便选择一个分值最小的边,连完后,在从相邻的边中选择一条分值低的,按照这个规则进行迭代,直到把所有点连接上为止

Kruskal’s algorithm

用一句话概括这个算法,就是先把分数低的连上

先按照分数把边进行分类,先连接分数低的边,按照这个规则进行迭代,直到所有点都被连接为止

两种算法的关系

如果最小生成树只有一种,那么无论采取什么算法,最后得到的最小生成树都是一样的

但是如果最小生成树不只有一种,那么得到了最小生成树可能不一样,但是从边的总分数来说,生成的树肯定是一样的

有向树

如果一个有向图在不考虑边的方向时是一棵树,那么,这个有向图称为有向树

简单来说,就是把一个有向图的边都换成无向边后,是一棵树,那么这个有向图称为有向树

根树

一棵有向树,如果恰好有一个结点的入度为0,其余所有结点的入度都为1,则称这棵有向树为根树

其中,入度为0的那个点称为根

级数和高度

级数:从一个点到根的路的长度

根据级数的定义,我们可以知道,由于根和自己的长度是0,所以根的级数是0

高度:一个根树中的最大级数

比如一个有九个点的根树,它的最大高度就是8,这个时候,这个树就是一根杆子

画的有点抽象💩

二叉树

顾名思义,指的是一个枝最多分叉两次

类似这种,需要注意的是

二叉树带有方向

至于为什么,到后面就会明白

二叉搜索树

比如我们要做一个小字典,能够实现的功能是可以搜索单词

有这样几个单词

math, computer, power, north, zoo, dentist, book.

该怎么实现这样一个搜索树呢?

让我们先选择一个参考单词math

画出math后,下一个是computer,由于首字母c在m前面,所以把computer排到math的左分支

再下一个是power,由于p比m靠后,所以把power排到math的右分支,math排满后,就可以排子节点computer和power,比如north,n比m靠后,但是比p靠前,所以把north放到power的左分支,按照这个规则进行迭代,就可以得到最终结果

这样,一个简单的二叉搜索树就完成了,芜湖✈️!

这也解决了前面的问题,再看下面这张图,一定能够恍然大悟

最后

今天补上树的部分,算是完成了创博客网站时周更的承诺,还有几天就要考离散了,希望我能没事🙏

-------------本文结束感谢您的阅读-------------