数据结构期末总结

2.3.1线性表的链式存储—链表链式存储不要求逻辑上相邻的数据元素在物理位置上也相邻，仅通过指针来映射数据元素之间的逻辑关系。存储结点包含数据域：所有存元素本身的信息；指针域：元素之间逻辑关系的信息；包含有后继结点的地址信息。循环队列：将存储队列的数组头尾相接。如何解决假溢出？01234入队出队a3a4fronta5rearreara6队列的顺序存储结构及实现（顺序队列）不存在物理的循环结构，但可用软件方法实现。求模：（4＋1）mod5＝0如何实现循环队列？01234入队出队a3a4frontreara6队列的顺序存储结构及实现（顺序队列）a5append

job1append

job2append

job3Popjob1append

job4append

job5Popjob2append

job6append

job7append

job8【0】【1】【2】【3】【4】【5】rearfront空队：front=rearjob11rear2job23job3rear45job4front6job5rear7front8job69job710job8rear队满：front=rear3.2.2队列的顺序存储结构及其实现---几个问题1、当rear指向数组的最大下标的时候，如何向下标为0的位置改变？2、队空和队满的条件都是front=rear,如何区分？3、如何表示出队和入队操作？【0】【1】【2】【3】【4】【5】CDEfrontrearBMaxSize=6chardata[MaxSize];rear=5rear=?data[rear]=‘F’;rear=(rear+1)%MaxSize3.2.2队列的顺序存储结构及其实现---问题一

循环队列首尾相连,这可以利用除法取余的运算(％)来实现:

队首指针进1:front=(front+1)％MaxSize

队尾指针进1:rear=(rear+1)％MaxSize

循环队列的队头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按顺时针方向进1。队空和队满的条件都是front=rear,如何区分？

rear

0

1

2

3

4

front

(a)空队

rear

0

1

2

3

4

front

(e)出队多

次,

队空

front==rear

rear

0

1

2

3

4

front

(e),队满

ABCDEfront==rear3.2.2队列的顺序存储结构及其实现---问题二循环队的入队和出队操作示意图

rear

0

43

2

1

front

(a)空队

(b)a,b,c入队

0

4

3

2

1

front

c

b

ar0

4

3

2

1d

c

b

afront

(c)d入队,队满

reara队满：(rear+1)%MaxSize==front

怎样区分队空与队满之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为:

(q->rear+1)%MaxSize==q->front队空条件仍为:

q->rear==q->front假设以数组sq[0..7]存放循环队列元素，变量f指向队头元素的前一个位置，变量r指向队尾元素，如果用A和D分别表示入队和出队操作，请回答如下问题：执行操作训练A4D2A6时的状态.（A3表示三次入队操作，D1表示一次出队操作）A4r=4,f=0D2f=2,r=4A6溢出1.1通俗定义树形表示法树的括号表达式a(b(e,f,g),c(h),d(i,j))会根据括号表达式画出树形图7.1.3树的基本术语

1.树的结点：包含一个数据元素和指向其子树的所有分支。

2.结点的度：一个结点拥有的子树的个数。

A

C

G

J

B

E

D

F

I

H

M

K

L

树形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。4.树的度：树中所有结点的度的最大值max(D(I))。含义：树中最大分支数为树的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

树形表示法

树的度：3结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC树的基本术语 5.7.2.1二叉树概念二叉树也称为二次树或二分树，它是结点数为0或当节点数不为0时每个结点最多只有左右两棵子树的树。特点是：（1）每个结点最多只有两棵树，既不存在度大于2的结点。（2）子树有左右之分，不能颠倒。思考：二叉树和度为2的树一样吗有什么区别？度为2的树中至少有一个节点的度为2，而二叉树没有此要求。结点孩子的有序性：度为2的树不区分左右树，二叉树严格区分。二叉树的特点：⑴每个结点最多有两棵子树；⑵二叉树是有序的，其次序不能任意颠倒。

7.2.1二叉树的逻辑结构注意：二叉树和树是两种树结构。ABCDEFGABAB二叉树的基本形态Ф空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树二叉树的逻辑结构二叉树的逻辑结构具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结构。特殊的二叉树斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。

二叉树的逻辑结构---斜树的特点：ABCABC满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。CDEFGHIJKLMNO1112131415特殊的二叉树二叉树的逻辑结构---满二叉树?不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树二叉树的逻辑结构---完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉树二叉树的逻辑结构---在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点特殊的二叉树二叉树的逻辑结构---1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。

3.深度为k的完全二叉树在k-1层上一定是满二叉树。完全二叉树的特点CDEFGHIJ特殊的二叉树二叉树的逻辑结构---7.2.2二叉树性质（5个）

性质1非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。

性质2高度为h的二叉树至多有2h-1个结点(h≥1)。证明：深度为h的二叉树的最大结点数是二叉树中每层结点的最大数之和，即=20+21+22+……+2h-1=2h-1(等比级数求和)

性质3非空二叉树上叶结点数等于度为2的结点数加1。有如下关系：n0=n2+1

证明：设二叉树上叶结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数n=n0+n1+n2。在一棵二叉树中,度为i(i=0,1,2)的结点，有i个孩子。孩子数=n1+2n2。由于二叉树中除根结点以外,每个结点都是另一个结点的孩子,因此二叉树中有：孩子数=总结点数-1=n-1。由上述三个等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉树

在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的结点进行连续编号,约定编号从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。图中每个结点外边的数字为对该结点的编号。每一层上结点树都达到最大度为1的结点n1=0完全二叉树:若二叉树中度小于2的结点只能出现在最大层或次大层,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同。

性质4具有n个(n＞0)结点的完全二叉树的高（深）度为log2n+1。证明：设深度为H余下的性质是针对完全二叉树的：证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1层———第k层…最少结点数最多结点数

log2n+1[log2n]log2n[log2n]+1k所在区间证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k性质4

具有n个结点的完全二叉树的深度为log2n+1。

对不等式取对数，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整数，故必有k＝log2n+1一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为

i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。

在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。完全二叉树的基本性质

思考题：二叉树和树的区别有哪些？7.8哈夫曼树与哈夫曼编码

哈夫曼(Huffman)树，又称最优二叉树，是一类带权路径长度最短的树。概念：两结点间的路径：从一结点到另一结点所经过的结点序列。路径长度：从树中一个结点到另一个结点之间路径上的分支数。树的路径长度：树根到每一个结点的路径长度之和称为。4123567结点1到5之间的路径：（1）（2）（5）结点1到5之间的路径长度：2树的路径长度：1+1+2+2+2+2=10定理：对于具有n个叶子节点的哈夫曼树，共有2n-1个节点。树的带权路径长度WPL：设树中有M个叶结点，每个叶结点带一个权值WK，树根到每一个叶结点K的路径长度为LK则WPL=。哈夫曼树：WPL最小的树称为最优二叉树，又称哈夫曼树7A5B4C2DWPL=7*2+5*2+4*2+2*2=36相关概念叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。记为：WPL=7.8哈夫曼树及哈夫曼编码å=nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。例：给定4个叶子结点，其权值分别为{2，3，4，7}，可以构造出形状不同的多个二叉树。

7.8哈夫曼树及哈夫曼编码WPL=32WPL=41WPL=30234723477423哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

7.8哈夫曼树及哈夫曼编码2347WPL=32WPL=41WPL=3023477423哈夫曼树的构造过程

abcd2347(a)c4d7ab5(b)d7cab9(c)dcab16(d)哈夫曼算法基本思想：⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；⑶删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；

⑷

重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。

7.8哈夫曼树及哈夫曼编码W＝{2，3，4，5}

哈夫曼树的构造过程7.8哈夫曼树及哈夫曼编码重复第2步54325549重复第3步554932哈夫曼树的构造过程

例1：W={5,29,7,8,14,23,3,11}7.8哈夫曼树及哈夫曼编码前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可能。P196例7.15：一组字符{A,B,C,D,E,F,G,H}出现的频率分别是{7,19,2,6,32,3,21}，设计最经济的编码方案。答案参考教材哈夫曼树应用——哈夫曼编码8.1图的基本概念8.1.1图的定义（多对多）

图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合V(G),E是连接V中两个不同顶点的边的有限集合,记为E(G)。

1

3

0

2

4

(a)

8.1.2图的基本概念和术语基本术语顶点：图中数据元素弧（边）：有向图：由顶点和弧构成的图（图a）无向图：由顶点和边构成的图（图b）无向完全图：无向图有n(n-1)/2条边(图8.2a)有向完全图:有向图有n(n-1)个弧(图8.2b)权：与图的边或弧相关的数值叫做权网：带权的图称为网12453573841628.1.2图的基本术语1.顶点的度、入度和出度在无向图中,顶点所具有的边的数目称为该顶点的度。在有向图中,以顶点vi为终点的弧的数目,称为该顶点的入度。以顶点vi为始点的弧的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。

图的存储方法很多，但是目标是相同的。即不仅要存储图中各个顶点的数据信息，还要存储顶点与顶点之间的关系（边或弧）。两种存储方法：邻接矩阵（数组存储）邻接表8.2图的存储结构

8.2图的存储结构

8.2.1邻接矩阵存储方法（教材P207) 邻接矩阵是一个（n×n）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为：

无向图的邻接矩阵

DCBAAúúúúûùêêêêëé=0111101111011110A

B

C

D

有向图的邻接矩阵8.2.2邻接表存储方法

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中,对图中每个顶点建立一个单链表,对于无向图链表中每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。

无向图的邻接表VA

B

C

D∧

A

B

D

∧

A

C

D

∧

A

B

C

∧

VBVCVD有向图的邻接表

AVBVCV

C

∧

B

C∧

B∧

8.3图的遍历8.3.1图的遍历的概念从图中某一顶点出发访遍图中其余结点，且使每一个顶点仅被访问一次，这一过程称为图的遍历图的遍历有两种：深度优先搜索广度优先搜索。深度优先搜索过程：从图中某个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没有被访问过的顶点w为初始顶点，再从w出发进行深度优先遍历，直到图中与当前顶点v邻接的所有顶点都被访问过为止。递归调用

图的深度优先遍历例子深度优先遍历序列：12485367深度优先遍历序列：12485367访问结点1访问结点2访问结点4访问结点8访问结点5访问结点3访问结点6访问结点7

例如,以上图的邻接表为例调用DFS()函数,假设初始顶点编号v=2,写出深度优先遍历序列。

图的广度优先遍历例子广度优先遍历序列：12345678访问结点1访问结点2访问结点3访问结点4访问结点5访问结点6访问结点7访问结点8广度优先遍历过程：首先访问初始顶点v，接着访问顶点v的所有未被访问过的邻接点v1，v2，v3..vt，然后在按照v1，v2，v3..vt的次序访问每一个顶点的所有未被访问过的邻接点，以此类推，直到途中所有和初始顶点v有路径相通的顶点都被访问过为止。

一个有向图的邻接表深度优先序列：13452广度优先序列：132458.3.3广度优先搜索遍历

广度优先搜索遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

1、已知一个有无向图的邻接矩阵P208图8.5A1.根据无向图的邻接矩阵，写出无向图的邻接表存储结构。图8.6(a).

根据无向图的深度优先遍历算法，写出从顶点v0出发所得到的顶点序列。(3)根据无向图的广度优先遍历算法，写出从顶点v0出发所得到的顶点序列。2、给定某图求其深度优先搜索遍历和广度优先搜索遍历。8.4图的应用----生成树和最小生成树最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？

应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。8.4图的应用----生成树和最小生成树8.4.1生成树的概念在一个无向连通图G中，含有N个顶点（1）N个顶点（2）N-1条边（3）无环路最小生成树生成树中，每个边都有权值，权值总和最小的树。8.4.2普里姆算法普里姆算法求解最小生成树的过程

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

0

2

(b)

1

0

2

5

(c)

1

4

0

2

3

5

(d)

1

4

2

0

2

1

3

5

(e)

1

5

4

2

0

2

1

3

4

5

(f)

1

3

4

2

5

普里姆(prim)算法描述假设G=(V,E)是一个具有n个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U={V1}；然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中Vi∈U，Vj∈V-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U；普里姆(prim)算法描述续如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。克鲁斯卡尔算法求解最小生成树的过程4

1

0

2

1

3

4

5

(a)

1

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

0

2

1

3

4

5

(d)

1

4

2

(e)

0

2

1

3

4

5

1

3

4

2

5

2

2

3

3

0

0

3

5

4

1

0

03

3

1

1

0

0

3

3

1

1

0

0

0

0

1

1

1

1

1

1

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

8.4.3克鲁斯卡尔算法

克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,则构造最小生成树的步骤如下：

(1)置U的初值等于V(即包含有G中的全部顶点),TE的初值为空集(即图T中每一个顶点都构成一个分量)。

(2)将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路,则加入TE；否则舍弃,直到TE中包含(n-1)条边为止。已知某带权无向图，用普里姆算法求其最小生成树，写出算法过程。粘图？？

AOE网络AOE网络有向图边表示活动(ActivityOnEdge)的网络，简称为AOE网络顶点表示事件，弧表示事件完成的过程也就是活动，弧上的权值表示完成该项活动需要的时间。源点：入度为0，表示工程的开始汇点：出度为0，表示工程的结束事件V:表示以它为弧头的所有活动已经结束，也表示以它为弧尾的活动可以开始了。求关键路径首先分别求出活动的最早发生时间与最迟发生时间，然后利用两者之差是否为0来确定关键活动，因为活动的最早发生时间与最晚发生时间为0就意味着该活动的时间余量，时间余量为0的活动为关键活动。

例如,下图表示某工程的AOE网。共有9个事件和11项活动。其中A表示开始事件,I表示结束事件。根据三元组画出AOE网（1，2，3）a1（1，3，2）a2（2，4，2）a3（3，4，4）a5粘图9.2顺序查找structRecord{intkey;……};Recordr[n];

无监视哨的顺序查找:

intSeqSearch(Recordr[],intn,intk)

{

inti=0;

while(i<n&&r[i].key!=k)i++;

if(i<n)returni;

elsereturn-1;

}

顺序查找的平均查找长度为：顺序查找的特点：算法简单，但查找效率低。9.3二分查找

二分查找又称为折半查找。

二分查找要求顺序表是有序的。二分查找的基本思想是：首先将待查的K值与有序表R[0]到R[n-1]的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若

R[mid].key>K，则说明待查找的结点只可能在左子表R[0]到R[mid-1]中，只需在左子表中继续查找；否则在右子表R[mid+1]到R[n-1]中继续查找。这样，经过一次关键字的比较就缩小了一半的查找区间。如此进行下去，直到找到为止（当然也存在最后找不到的可能）。例:[0513192137566475808892][0513192137]566475808892051319[2137]566475808892查找K=21的过程（查找成功）[0513192137566475808892]051319213756[6475808892]051319213756647580[8892]查找K=85的过程（查找失败）051319213756647580[8892]9.4Hash查找1.基本概念

Hash,哈希,也称为散列.

Hash是一种重要的存储方法，也是一种常见的查找方法。它的基本思想是：以数据元素的关键字K为自变量，通过一个确定的函数关系，计算出对应的函数值f(K)，把这个值作为数据元素的存储地址。查找时也是根据这个函数计算其存储位置。【例】假设一组记录的关键字分别为{18，27，1，20，22，6，10，13，41，15，25}。选取关键字与记录位置间的函数为f(key)=key%11。Hash函数----关键字与记录位置间的函数.Hash地址----据Hash函数计算出的存储位置.Hash表----存储记录的查找表,该表中根据Hash函数计算出的存储位置.基于Hash表的查找称为Hash查找。在建立Hash表时，若Hash函数是一个一对一的函数，则在查找时，只需根据散列函数对给定值进行某种运算，即可得到待查数据的存储位置。在一般情况下，Hash表的空间必须比数据的集合大，此时虽然浪费了一定的空间，但换取的是查找效率。设散列表的空间大小为m，填入表中的数据个数为n，则称α=n/m为散列表的装填因子。Hash函数的选取原则是：运算尽可能简单；函数的值域必须在表长的范围内；尽可能使得关键字不同时，其散列函数值亦不相同。若某个Hash函数对于不相等的关键字计算出了相同的

Hash地址，则称该现象为hash冲突，发生冲突的两个关键字该Hash函数的同义词。在实际应用中，不产生冲突的Hash函数极少存在。例9.9假设哈希表长度m=13，采用除留余数法加线性探查法建立如下关键字集合的哈希表(16,74,60,43,54,90,46,31,29,88,77)并计算查找成功和查找不成功时候的平均查找长度。提示：n=11(记录个数)m=13（表长）h(key)=key%pp应该为小于等于m素数二叉排序树特点、判断什么样的树是二叉排序树，P257二叉排序树上的重要性质。10.7堆排序堆排序是选择排序的改进（1964提出）。在排序过程中，将r[1]到r[n]看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小元素。堆的定义：n个数据序列K1,k2,...,Kn称为堆，当且仅当该序列满足特性：

此种情况称为小顶堆。或者，均大于也可以。此种情况情况称为大顶堆。从堆的定义可以看出，堆实质上是满足如下性质的二叉树：树中任一非叶子结点的值均小于等于它的孩子结点的值。