计算机应用基础1.4树b

第第页计算机应用基础1.4树b计算机应用基础

第1章

数据结构1065

1.1基本数据结构与算法1.2线性表865

1.3栈和队列

1.4树和二叉树1.5查找1.6内部排序姓名学号成果班级机97.6

李红976105995

计算机应用基础

1.4树和二叉树1.4.1树的定义和基本术语1.4.2二叉树

1.4.3遍历二叉树

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语树型结构是一类重要的非线性数据结构，元素结点间存在明显的分支和层次关系。现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。A

T1E

BC

D

FG

H

I

J

K

L

T2

M

T3

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义概念：树是n(n≥0)个结点构成的有限集合。n=0为空树；n≠0时，树中结点应当满意两个条件(1)有且仅有一个特定的根的结点。(2)其余的n-1个结点可划分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中Ti又是一棵树，称为根的子树。

示意图：T1={B,E,F,J,K}T2={C,G}T3={D,H,I,L}

T1T2

T3

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)1)根结点:没有前驱的结点只有一个,称为根结点。2)双亲(父)结点:树中每个结点只有一个径直前驱,称为该结点的双亲结点或父结点。

3)孩子(子)结点：一个结点的子树的根或者后继结点数称为该节点的孩子结点或子结点。

4)叶子结点(终端结点):没有子结点(后继)的结点。

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)A

A:是根结点,同时是B、C、D结点的父结点或双亲结点DHLI

BEJKF

CG

B:是E、F的父结点，E、F是B的子结点或孩子结点J、K、L、F、G、I:是叶子结点

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)5)兄弟：同一个双亲的孩子结点之间互称兄弟。

6)堂兄弟：其双亲在同一层的结点互为堂兄弟。7)结点的祖先：结点的祖先是从根到该结点所经分支的全部结点。8)结点的子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)

B的子孙为E、F、J、K。ABCD

B,C,D互为兄弟

G与E、F、H、I互为堂兄弟结点

EJK

F

G

HL

I

L的祖先为A、D、H。

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)9)结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。假设某结点在第k层，那么其子树的根就在第k+1层。10)结点的度:一个结点的子树的个数(拥有后继的个数)。11)树的度:全部结点度的最大值。12)树的深度或高度

:树中结点的最大层次称为树的深度。

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)ABEJKFCGHLDI

结点A的层次：1结点L的层次：4结点的度:A的度为3;C的度为1F的度为0树的度：3树的深度：4

留意:一棵树中,每个结点的度数之和=结点总数-1=树中边的条数

计算机应用基础

1.4树与二叉树1.4.1树的定义和基本术语1.树的定义2.树的基本概念(相关术语)

13)有序树：假如将树中结点的各子树看成从左至右是有次序的(即不能互换),那么称该树为有序树。否那么为无序树。在有序树的最左边的根称为第一个孩子，最右边的称为最末一个孩子。14)森林：是m(m≥0)棵互不相交的树的集合。对树中根结点而言，其子树的集合即为森林。由此，可用森林和树相互递归的定义来描述树。由于树的每个结点的度不同，存储困难，使对树的处理算法很繁复，所以引出二叉树的争论。返回

计算机应用基础

1.4树与二叉树1.4.2二叉树1.二叉树的定义定义：二叉树是n(n0)个结点的有限集，它或为空树二叉树的五种基本形态(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。特点：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒

空二叉树

仅有根结点

右子树为空

左子树为空

左右子树均非空

计算机应用基础

1.4树与二叉树1.4.2二叉树21.二叉树的定义2.二叉树的性质8

13

4910

51112

61314

715

性质1:二叉树的第i层上至多有2i-1(i1)个结点。证明：依据二叉树的特点，结论是显着的。(用归纳法证明)。性质2:深度为k的二叉树中至多2k-1个结点。证明：深度为k的二叉树最多有k层，依据性质1,只要将第1层到第k层的最大结点数相加，就可得到整个二叉树中结点的最大值。21-1+22-1+……+2k-1=2k-1(k1)

计算机应用基础

1.4树与二叉树1.4.2二叉树1.二叉树的定义2.二叉树的性质叶子结点：n0=3CEB

A

DF

度为2的结点：n2=2

性质3:对任何一棵二叉树T,假如其终端结点数为n0,度为2的结点数为n2,那么n0=n2+1。证明：(1)结点总数n=n0+n1+n2(n1是度为1的结点数)(2)由树的性质：n=B+1,有：n=n1+2*n2+1由(1)、(2)合并，可推出：最末得:n0=n2+1度为0的结点没有下连的边，度为1的结点下连的边为1,度为2的结点下连的边为2

计算机应用基础

1.4树与二叉树1.4.2二叉树1.二叉树的定义2.二叉树的性质满二叉树

定义：假如一个二叉树深度为K,结点数为2k-1,那么称为满二叉树特点：除最末一层外，每一层全部结点都有两个子结点。1满二叉树23

48

5

6

7

9101112131415

计算机应用基础

1.4树与二

叉树1.4.2二叉树1.二叉树的定义2.二叉树的性质

留意:满二叉树必是完全二叉树；而完全二叉树未必是满二叉树。

完全二叉树定义:指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。特点:叶子结点只可能在最下面两层上,且最下层叶子结点集中在树的左部。任一结点,右分支下子孙结点最大层次为h,那么左分支必为h或h+1。1124563

274657非完全二叉树

3

8910

计算机应用基础

1.4树与二叉树1.4.2二叉树1.二叉树的定义2.二叉树的性质性质4:具有n个结点的完全二叉树的深度k为[log2n]+11证明：依据完全二叉树的定义和性质2可知，当一棵完全1二叉树的深度为k,结点个数为n时，第k层最少有1个结232点，最多为满，故有342k-1-1+1≤n≤2k-15674即2k-1≤n2k对不等式取对数，有深度为3的完全二叉树结点深度为3的完全二叉树结点数k-1≤log2k-1最少状况是4,即2nk-1=3个数最多状况是2k-1=7个由于k是整数，所以有k=[log2n]+1。【注：此处运算，为向下取整运算】

计算机应用基础

1.4树与二叉树1.4.2二叉树1.二叉树的定义2.二叉树的性质8491025

1367

性质5:具有n个结点的完全二叉树，从上至下和从左到右作用：很简单确定每个结点的父结点、左子和右子结点的位置。的顺次对全部结点从1开始顺次编号，那么对任意结点i有:1)i=1,该结点是根结点。否那么(i1),其双亲结点序号为i/2。2)假如2i≤n,其左孩子结点的序号为2i。如2、3、4、5结点)假如2in,那么i结点，无左子结点,显着也没右结点。

(如图中6、7结点)3)假如2i+1≤n,那么序号为i的结点的右孩子结点的序号为2i+1(如2、3、4的右结点分别为5,7,9);假如2i+1n,那么序号为i的结点无右孩子结点。(如5、6、7)

计算机应用基础

练习1.在一棵二叉树上第4层的结点数最多是______。A.4B.8C.32D.122.在深度为5的满二叉树中，叶子结点的个数为______。A.32B.31C.16D.153.在深度为5的二叉树中，至多有______个结点。A.32B.31C.16D.154.在具有10个结点的树中，其边的树目为______。A.11B.10C.8D.95.设一棵完全二叉树共有10个结点，那么在该二叉树中的叶1子结点数为______。A.9B.5C.2D.423解答：BCBDB

489

510

6

7

5.依据性质5,可知最末叶子结点为10,其父结点是5,且该结点5是最末一个非叶子结点,那么从结点6~10均为叶子结点。(10-6+1)

返回

计算机应用基础

6.设一棵二叉树中有3个叶子结点，有8个度为1的结点，那么该二叉树中总的结点数是______。A.12B.13C.14D.157.下面关于完全二叉树的表达中，错误的选项是______。A.除了最末一层外，每一层上结点数均达到最大值B.可能缺少假设干个左右叶子结点C.完全二叉数

一般不是满二叉数D.具有结点的完全二叉树的深度为[log2n]+1解答：BB6.=n0+n1+n2=3+8+(3-1)(性质3:n0=n2+1)

返回

计算机应用基础

8.在深度为7的满二叉树中，叶子结点的个数为___。(06.4月)A)32B)31C)64D)639.设树T的度