资源简介

(共14张PPT)
一、 树、二叉树的概念及其性质
第四章　树
知识过关
1. 树的概念
树(Tree)可以描述为由n(n≥0)个节点(Node)构成的一个有限集合，以及在该集合上定义的一种节点关系。集合中的元素称为树的节点,n=0的树称为空树。
2. 树的相关概念及性质
(1)对于一棵具有n个节点的树,它有n－1条边。
(2)树的一个节点所拥有的子树个数称为该节点的度,最大的节点的度称为树的度。线性表是度为1的特殊树状结构。
(3)在树状结构中,没有前驱的节点称为根节点(Root),又称为开始节点。度为0的节点称为叶子节点(Leaf),它又称为终端节点。
(4)树中节点的层数从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度(Depth)。
(5)在树状结构中,对于两个以边直接连接的节点,上端节点称为下端节点的父节点或双亲节点。相应地,下端节点称为上端节点的孩子节点。同一双亲节点的孩子节点之间互为兄弟节点。
3. 二叉树的概念
二叉树是一个具有n (n≥0)个节点的有限集合,它的所有节点的度都小于或等于2。当n=0时,二叉树是一棵空树;当n不等于0时,它是一棵由根节点和两棵互不相交的、分别称为这个根节点的左子树和右子树组成的二叉树。
4. 二叉树的相关概念及性质
(1)完全二叉树至多只有最下面两层中的节点度数小于2,最下面一层的叶子节点都依次排列在该层的最左边位置(如有缺少,则缺少的只能是最下层最靠右的连续元素)。
完全二叉树
(2)二叉树的性质。
①二叉树的第k层上最多有2k－1(k≥1)个节点。
②深度为k的二叉树最多有2k－1(k≥1)个节点。
③在任意一棵二叉树中,若度为2的节点数量为n2,叶节点(度为0的节点)数量为n0,则n0=n2+1。
(3)具有n个结点的完全二叉树的深度为 log2n」+1。(注: 」表示向下取整)
典例精选
【例1】 关于二叉树,下列说法中错. 误. 的是(　　)
A. 用数组的方式存储二叉树,容易造成空间浪费
B. 若有前序和中序遍历,可以推导出一棵唯一的二叉树
C. 只有最下面两层有叶子节点的二叉树称为完全二叉树
D. 完全二叉树的第3层有3个叶子节点,则该树的节点数量可能是8
【解析】 本题考查二叉树的存储、二叉树的遍历、完全二叉树的基本性质。完全二叉树除了要满足至多只有最下面两层中的节点度数小于2这一条件外,还需要符合最下面一层的叶子节点都依次排列在该层的最左边位置这一条件。C符合题意。
C
【例2】 在一棵二叉树上,第4层的节点数最多为(　　)
A. 2 B. 4
C. 8 D. 16
【解析】 本题考查二叉树的性质。二叉树的第k层上最多有2k－1(k≥1)个节点,C正确。
C
【例3】 有一棵完全二叉树具有100个结点。下列说法中,正确的是(　　)
A. 树的深度为8 B. 有1个节点只有非空左子树
C. 此完全二叉树有49个叶子结点 D. 有50个度为2的节点
【解析】 本题考查二叉树的基础知识。树的深度为7时,27－1就有127个节点,树的深度为7的话,就有127个节点了,深度不可能为8,A错误。(100－n1－1)/2,n1要么是0要么是1,总结点数为100,n1有1个,B正确。叶子节点有(100－n1－1)/2,n1的个数为1,所以叶子节点为50个,C错误。根据以上总结n0=50,n1=1,n2=49个,D错误。
B
自我检测
1. 下列选项中,不. 属. 于. 树状结构的是(　　)
A. B.
C. D.
【解析】 根据树的相关性质可知,n个节点的树通过n－1条边相连,B有3个节点,共有3条边,与树的性质不符,符合题意。
B
2. 下列关于树和二叉树的说法,错. 误. 的是(　　)
A. 树是一种非线性的数据结构
B. 二叉树是树的特殊形式
C. 完全二叉树是二叉树的特例
D. 二叉树所有节点的度都是2
【解析】 二叉树所有节点的度都小于等于2,D符合题意。
D
3. 有一棵树,如图所示。
该树中,节点B的度和树的度分别为(　　)
A. 2,4
B. 3,4
C. 3,5
D. 2,5
【解析】 本题考查节点的度和树的度的概念。
树的一个节点所拥有的子树个数称为该节点的
度,所以节点B的度为3。最大的节点的度称为
树的度,C节点的度最大为4,所以树的度是4。
B正确。
B

展开更多......

收起↑