[软考]之树和二叉树

r囧r小猫 2022-08-08 18:29 118阅读 0赞

对于具有层次的数据，需要用树形结构来描述，那么什么是树，树应该如何表示使用呢？下面，就随着这篇博文，来感受一下树的魅力吧。

##         树的基本组成： ##

关于树的基本组成，先来看一下定义：

树（tree）是包含n（n>0）个结点的有穷集，其中：  
           （1）每个元素称为结点（node）；  
           （2）有一个特定的结点被称为根结点或树根（root）。  
           （3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

我在网上找了几张表示树的图，大家可以看一下，帮助理解：

[![Center][]][Center 1]

说完了树，顺便提一下森林，森林是m（>=0）棵互不相交的树的集合，树的每个结点的子树是森林，删除一个非空树的根结点，它的子树便构成森林，比如上图中的3号树，将它的根A删除，那么以B为根和以C为根的两棵互不相交的树便构成了森林。

##         树的相关术语： ##

对于树，我们有一些比较专业的叫法来称呼它的各个部位，比如结点的度，叶子，树的度等等，下面仍旧用一张图来表示：

![Center 2][]

##                       二叉树： ##

我们所说的二叉树，就是树的一中特殊结构，即由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树，简而言之，任何一个结点的孩子，都不超过两个。二叉树有5个性质，即：

1.在二叉树的第i层上最多有2 i-1 个节点 。

2.二叉树中如果深度为k,那么最多有2k-1个节点。

3.n0=n2+1  n0表示度数为0的节点 n2表示度数为2的节点。

4.在完全二叉树中，具有n个节点的完全二叉树的深度为\[log2n\]+1，其中\[log2n\]+1是向下取整。

5.如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有  
  
              1.如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为\[i/2\]，向下取整    
  
              2.如果2i>n那么节点i没有左孩子，否则其左孩子为2i  
  
              3.如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

二叉树也分为几种类型，分别为：满二叉树，完全二叉树和非完全二叉树，我们直接上图来看：

![Center 3][]

满二叉树即满足深度为K且有2^K-1个结点。完全二叉树是从满二叉树的结构来判断的，即：一颗深度为k二叉树，有n个节点，然后，也对这棵树进行编号，如果所有的编号都和满二叉树对应，那么这棵树是完全二叉树。附图一张：

![Center 4][]

这就是树和二叉树的基本概念和组成标准了，下面一篇博文我们会讨论对于二叉树的遍历和一些计算，未完待续哦~

[Center]: /images/20220731/459b3e748d2a41129dd9a1467014e804.png
[Center 1]: http://www.cppblog.com/guogangj/archive/2009/10/16/98772.html
[Center 2]: /images/20220731/988e5385caa640fa892188d3c9192603.png
[Center 3]: /images/20220731/1f1046f5b3c649f18668baf47fe33851.png
[Center 4]: /images/20220731/fbe0212027924d0e9704a3ecb04c0a4d.png