初阶数据结构篇马上要迎来了一个新的成员,那就是"二叉树"。
但是我上来不可能直接带着大家立马实现二叉树这个数据结构的,因为这是一种对各位读者不负责的表现。俗话说得好,饭要一口一口地吃,路要一步一步地走!这样学的知识才真的是属于你自己。
为此,在本文我先会给大家介绍什么是“树”?什么又是“二叉树”?以及它们在编程中常用到的一些性质。在这里都会毫无保留地给大家详细地讲解,相信看完这篇文章,你对二叉树乃至树这个数据结构有更深地了解。
当然,我后期还会发布关于二叉树各种系列的博客,保证符合各位读者的胃口。同时也欢迎各位读者来看,大家一起进步!!!
好了,话不多说。让我们朝着二叉树的彼岸说一声:"Let’s go!"🚢💖💖
在讲二叉树之前,我们肯定得先知道什么是"树"。
树:由n(n>=0)个有限的结点组成的具有层次关系的集合。
树是一种非线性的数据结构!
这里就得说一下,什么叫做有层次关系? 你可以把数据结构中的“树”与日常生活我们所看见的“树”,做一个像形的融合。只不过数据结构中的"树"是倒着的(根朝上)。 我们在日常生活中看到的树,是有一定的高度的。相信大家可能有爬树的经历,如果没有的话,那也一定在某种场景下,看过别人爬树。看着他们一步一步的往上爬,直至爬到树顶,他们每往上爬一步,我们都可以认为这是"树的一层",这种关系一直持续到树顶。那"树"的每一层都是组成我们在日常生活的所看到的树的关键一环。这个就是层次关系(为了好区分,这里我就称它为“结构关系”)。
回到数据结构中的"树",也是有一层一层的结点构成的。这些结点间还有一些有趣的关系(后面会介绍),这里我们就可以认为层与层之间具备了一定关系。为此,层次关系这个抽象关系我们就给具象化了。希望大家能够理解。
树的一些专属名称:
如果没有理解上面这个枯燥的说法,可以看一下这幅图:
每个颜色的圈都可以看作是一棵子树。当然每一棵子树也可以分为根节点和子树!
那我们了解了树的一些定义,那我们在实际中该怎么判断题目给出的一幅图是否是一棵"树"呢?
现在我来教大家几招:
这里给大家一些小练习,来判断下面的图是不是树。
可以看到,上面的三幅图都不是树,因为它们都不满足我上述提到的三点。
相信到这里大家对树已经有足够的了解了。
为了让“树”变得更加的科学化、专业化,我们必须得学习有关于"树"的一些相关的概念。(温馨提示:概念可能有点多,大家重点了解我标出颜色的即可,这些概念都是大家在以后做题或者与人讨论“树”的必不可少的工具)
这里有个概念可能大家比较模糊,这里我就解释一下:
祖先:就是该结点到根节点所经过的结点,这些结点就称为"祖先"。需要注意的是,经过的路线只能是孩子结点到父节点这条路线。 举个栗子:比如我要找“ Q”结点的祖先
讲完了树相关的概念,相信大家对树是怎么用代码实现的探索兴趣又多了几分。 但是在这里,我不会带着大家真正去实现一棵树。这里会提供树的实现思路。
我们首先得知道一个点,树的实现是要比我们之前学到过的线性表(顺序表、链表、栈、队列)难得多。原因是,树不仅仅是要保存数据,同时还要维护数据之间(结点和结点)的关系。而我们之前学的线性表只是在如何正确保存数据的层面,而树增加了一个层面——数据之间的关系。
实际中树有很多种表示方法,比如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。在这里我给大家简单的介绍最常用的孩子兄弟表示法。(你看,这里就涉及到了有关于树的一些专有名词,如果我们都不去了解,那根本就不知道它在说什么。可见前期的铺垫有多重要。)
typedef int DataType;
struct TreeNode
{
struct TreeNode* _firstChild1; //第一个孩子结点
struct TreeNode* _pNextBrother; //指向其下一个兄弟结点
DataType _data; //结点中的数据域
}
这个方法是不是很巧妙!其可以完美的避开每个结点下有多少棵子树的问题,我们就解决一个结构体里设计多少个指针数量的问题。
要说树在实际中的应用,文件系统中的目录树就是经典中的经典!
那至于文件系统更深层次的相关知识,大家可以去看我往后会更新的Linux的文件系统管理!
二叉树,大家可以理解为是一种特殊的"树"!
那怎么个特殊法呢?
所以看到这里我们就知道了,二叉树无非就是在树的基础上,加上这俩个条件罢了。
这里给大家做一下二叉树的思维拓展: 对于任意的二叉树都是有以下的情况复合而成的:
如果看到这里,你还是对二叉树的概念有点懵懂的话,那你可以听听趣味讲解一下二叉树。
二叉树的双亲结点最多只能拥有两个孩子结点。这就好似"计划生育"政策,每一对夫妻最多只能生两个小baby,当然也可以选择不生或者是只生一个。 这个不就是二叉树双亲节点最多只有两个孩子结点的最好的描述了。
为了,强化大家对二叉树的印象,给大家看一下现实生活中存在的二叉树!
普通的二叉树讲完了。现在给大家讲一讲特殊的二叉树,这些二叉树在我们后期的编程扮演着重要的角色,希望大家能够认真理解这些特殊二叉树的性质。
特殊的二叉树:
如果,你不理解上述的这段话,没有关系。我给出两幅图,你肯定就会明白了。
判断一棵二叉树是否是完全二叉树的方法:
前提条件是该二叉树的深度为K。 条件1:前K-1层的结点必须是满的; 条件2:最后一层的结点必须在肉眼上是紧密挨着的。
- 1.
, 度为2的分支结点个数为
,则有
=
+1
. (ps:
.是log以2为底,n+1为对数)
这里的每一条性质都比较重要,希望大家都能理解性记忆!
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
答案: 1.B 2.A 3.A 4.B 5.B
好了到此,有关于树和二叉树的相关概念和性质,我们都已经学习完了。相信在今后当谈论到有关于树和二叉树的话题,你都能清楚的知道。更重要的是,在编程时能够有个清晰的认知!