树和二叉树简介

树的定义

为了保证数据的能够有效的查询,可以使用顺序结构。为了保证数据的插入效率,我们可以使用链型结构。但在某些场合,我们需要同时兼顾查询效率和插入的效率,应该怎么做?

树(Tree)型结构是一类常用的高效的非线性的数据结构,兼顾了顺序表的查询效率和链表的插入效率。例如我们电脑中的目录结构,采用的就是一种树形结构关系。 树的具体结构形状如下图:

树结构

关于树有以下几个定义:

度:每个节点拥有的叶子的个数称之为度。A节点的度是3
树的度:是指节点的最大值,当前树的度是4。
根节点:树的开始节点,A节点是根节点
叶子节点:没有子节点的节点,K、L、F节点是叶子节点

为什么树能够保持较高的查询和插入效率,对比顺序结构, 顺序结构的查询效率的时间复杂度为O(1),插入的效率为O(n),链式结构正好相反。

如果我们把数据结构由线形结构转成树形结构的话,查询和遍历节点的数量一定是小于等于n,所以树的效率一般是优于线性结构。

树的存储形式

  1. 双亲表示法

    双亲表示法是指用顺序结构来表示数,每个节点设置一个变量,来指示双亲节点所在的位置,如下:

    树结构

  2. 孩子表示法

    每个节点可能有多个子节点,可以用使用多级链表来分别表示。具体如下:

    树结构

  3. 孩子兄弟表示法

    又称为二叉树表示法,是以二叉链表的方式进行存储。表示如下:

    树结构

阅读更多