二叉树概念及结构1.

树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。

把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。

有一个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合

T_1、T_2、……、T_m

Ti​(1im)又是一棵结构与树类似的子树。

每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。

如上图B、C、H、I…等结点为叶结点非终端结点或分支结点度不为0的结点

如上图D、E、F、G…等结点为分支结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点

如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点

如上图B是A的孩子结点兄弟结点具有相同父结点的结点互称为兄弟结点

如上图树的度为6结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次

如上图树的高度为4堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。

如上图所有结点都是A的子孙森林由mm0棵互不相交的树的集合称为森林

树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef

二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树

满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。

也就是说如果一个二叉树的层数为K且结点总数是

2^k

则它就是满二叉树。

完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。

对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

i层上最多有

因为二叉树中每个结点都有双亲根结点没有双亲每个节点向上与其双亲之间存在一条边

为n12*n2

hlog2​(n1)是log以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有

若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子

某二叉树共有

顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。

而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。

二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。

链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址

。

链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面学到高阶数据结构如红黑树等会用到三叉链。

typedef

普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。

而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。

k_0

kn−1​}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足

k_ik_{2i

012…则称为小堆(或大堆)。

将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。

堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树

建堆时间复杂度

因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果)

选择题

2.已知小根堆为8,15,10,21,34,16,12删除关键字

3.一组记录排序码为(5

4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是

A[3257468]

堆的实现我们按照动态顺序表为物理结构即顺序存储结构以完全二叉树为逻辑结构。

typedef

下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。

根结点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子结点的子树开始调整一直调整到根结点的树就可以调整成堆。

int

}现在我们只是把一个元素插入到了数组之中接下来我们要对该元素进行向上调整。

4.6

删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。

//时间复杂度O(logN)

1]);php-size--;AdjustDown(php-a,

php-size,

}现在我们也同样只是把堆顶元素根位置元素从数组中删除接下来的向下调整算法才是堆的核心算法也是堆排序的核心算法。

4.8

现在我们给出一个数组逻辑上看做一颗完全二叉树。

我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。

向下调整算法有一个前提左右子树必须是一个堆才能调整。

int

{27,15,19,18,28,34,65,49,25,37};void

a,int

i);//}//建堆//从最后一个父亲节点开始依次向上执行向下调整算法for

(int

a[end]);//将排列好的元素放在最后面AdjustDown(a,

end,

建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。

5.2

TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。

比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

最佳的方式就是用堆来解决基本思路如下

用数据集合中前K个元素来建堆

前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void

(int*)malloc(sizeof(int)*n);srand(time(0));//造数据for

(size_t

1]);php-size--;AdjustDown(php-a,

php-size,

HPTop(hp);HPPop(hp);}HPDestroy(hp);

}void

{//TestHeap01();TestHeap02();return