数据结构之树与二叉树

目录

前言

一、树的概念及其结构

1.1树的概念

1.2树的其他相关概念

1.3树的表示

1.4树的在实际中的应用

二、二叉树的概念及结构

2.1二叉树的概念

2.2特殊的二叉树

2.3二叉树的性质

三、二叉树的存储结构

前言

兄弟们，前面已经介绍了链表（单向和双向）、栈和队列，这些都是一对一的线性结构，可是在现实生活中还有很多一对多的情况需要处理，接下来我们就进入一个新的世界了，那就是树，这个就十分的厉害了，那么先从它们的概念开始讲起！

一、树的概念及其结构

1.1树的概念

树是一种
非线性
的数据结构，它是由
n
（
n>=0
）个有限结点组成一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

        ①有一个
特殊的结点，称为根结点，
根节点没有前驱结点

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

        ③除了根节点之外，每个节点有且仅有一个父节点

        ④一棵n个节点的树有n-1条边

        

因此，
树是递归定义
的。

注意：
树形结构中的子树不能有任何交集，否则它就不是树形结构

1.2树的其他相关概念

1.3树的表示

树的结构相对于线性结构来说比较复杂，要存储起来就比较的麻烦了，既要保存值域，又要保存节点与节点之间的关系，所以在实际中树的存储结构有很多种表示方法，如双亲表示法，孩子表示法，孩子兄弟表示法以及孩子双亲表示法等等

双亲表示法：在每个节点中，设置一个指示器指示其双亲结点在数组中的位置

结构如下：

规定：因为根节点没有双亲，所以根结点位置附为-1

代码定义如下

#define MAX_SIZE 6

typedef int elemtype;

typedef struct TreeNode         //结点结构
{
    elemtype data;             //结点数据
    int parent;                //双亲位置  
}TreeNode;

typedef struct                 //树的结构
{
    TreeNode node[MAX_SIZE];   //结点数组 
    int root;                  //根的位置 
    int n;                     //结点个数 
}Tree;

孩子表示法：每个结点有多个指针域，其中每个指针指向一棵子树的根节点

struct TreeNode
{
    int val; 
    struct TreeNode* child1;
    struct TreeNode* child2;
    struct TreeNode* child3;
    //.....
    struct TreeNode* childn;
};

为了简洁，我们放在一个指针数组里，但是呢，这需要根据树有多少度去定义多少个结点

//假设树的度为6
#define N 6
struct TreeNode
{
    int val; 
    struct TreeNode* childArry[N];//指针数组
};

又或者可以用顺序表来存储孩子

struct TreeNode
{
    int val; 
    Seqlist childsl;
    //顺序表存储孩子
};

总的来说，还是不好去控制的，所以最常使用的还是孩子兄弟表示法，下面来简单了解一下

孩子兄弟表示法：

        我们都知道，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是为唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结构定义代码如下

//左孩子右兄弟
struct TreeNode
{
    int val;
    struct TreeNode* leftchild;
    struct TreeNode* rightbrother;
};

这样的做法比其他的方式要容易控制了很多，就不需要考虑到树的度的问题，有几个连几个它给查找某个孩子的带来了方便，当然了，如果要找到双亲，那这个就有缺陷了。那怎么办呢？其实完全可以在增加一个parent指针域，这里就不细谈了

        其实这个表示法最大的好处是它把一棵复杂的树变成了一棵二叉树，什么是二叉树呢？别急，后面的文章将会细谈

1.4树的在实际中的应用

一般树在实际中表示文件系统的目录树结构，如LInux系统

二、二叉树的概念及结构

2.1二叉树的概念

二叉树：一棵二叉树是结点的一个有限集合，该集合
:

                1. 或者为空

                2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

1.
二叉树
不存在度大于2
的结点（不一定度为2）

2.
二叉树的子树有左右之分，次序不能颠倒，因此
二叉树是有序树

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

2.2特殊的二叉树

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

②完全二叉树
：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
对于深度为K 的，有n个结点的二叉树，
当且仅当其每一个结点都与深度为K的满二叉树中，按照从上到下，从左到右，编号从1至n的结点一一对 应时称之为完全二叉树。
要注意的是满二叉树是一种特殊的完全二叉树（
前K-1层是满的，最后一层不一定满，但是从左到右必须连续的
）。

        两点特性：

        ①叶子节点只会在最后两层出现

        ②当某个结点左右孩子为空或者右孩子为空时，后面所有结点孩子均为空

那么，问题就来了，看下图

很显然这不是，因为根据完全二叉树的特性以及定义可知，最后一层可以不满，但从左到右必须连续！

2.3二叉树的性质

①  
若规定根节点的层数为
1
，则一棵非空二叉树的
第
i
层上最多有
2^(i-1)
个结点.（
如满二叉树
）

②  
若规定根节点的层数为
1
，则
深度为
h
的二叉树的最大结点数是
2^h-1(如满二叉树)

③ 对任何一棵二叉树
,
如果度为
0
其叶结n0
,
度为
2
的分支结点个数为n2
 
,
则有 n0＝n2 ＋
1

④ 
若规定根节点的层数为
1
，具有
n
个结点的满二叉树的深度
，
h=log2（n+1）(ps： 是log
2

为底，
n+1
为对数
)

⑤.
对于具有
n
个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从
0
开始编号，则对 于序号为i
的结点有：

1.
若
i>0
，
i
位置节点的双亲序号：
(i-1)/2
；
i=0
，
i
为根节点编号，无双亲节点

2.
若
2i+1=n
否则无左孩子

3.
若
2i+2=n
否则无右孩子

ps:对于上述的性质，大家可以将一棵二叉树画出来，就可以得到对应得性质了

下面给几道简单例题加深理解

1.
某二叉树共有
399
个结点，其中有
199
个度为
2
的结点，则该二叉树中的叶子结点数为（ ）

A
不存在这样的二叉树

B 200

C 198

D 199

答案 ：根据性质③得出n0=n2+1  ——>n0=200,故选B

2.
在具有
2n
个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

解析:n0代表度为0，n1代表度为1，n2代表度为2

n0+n1+n2=2n

n0=n2+1

—->2n0+n1=2n+1

因为度为1的结点那么0，要么1，而结果2n+1为奇数，2n0为偶数，只有偶数+奇数才得奇数

所以n1=1

–>n0=n

选A

3.一棵完全二叉树的节点数位为
531
个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

答案:B

4.
一个具有
767
个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386

选B

三、二叉树的存储结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而
完全二叉树更适合使用顺序结构存储
。现实中我们通常把
堆(一种二叉树)
使用顺序结构的数组来存储，要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

从上图可知，父子结点的下标存在着一定的规律

左孩子=父*2+1

右孩子=父*2+2

父=（左孩子-1）/2

对于非完全二叉树来说，就不太适合采用顺序存储了，很难找到具体结点的位置

二叉链式存储：用链表来表示一棵二叉树，即用链来指示元素的逻辑关系，通常的方法就是孩子兄弟法，
一个结点有数据域、指向左孩子的指针以及指向右孩子的指针!具体内容，后期尽请期待

好了，兄弟们，今天就先分享到这里，对于堆以及更多二叉树的内容，作者后面会有更加详细的讲解!如果对于今天的内容你有所收获，可以给个三连，如有问题，欢迎留言！