选择性必修1 专题四 树及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教师用书word(浙江专用)

| 26页
| 119人阅读
| 9人下载
教辅
山东瀚海书韵教育科技有限公司
进店逛逛

学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

专题四 树及应用

一、树与二叉树

1.树(Tree)的几个基本概念

树是一种非线性的数据结构。

(1)树可以描述为由n(n≥0)个节点构成的一个有限集合以及在该集合上定义的一种节点关系。

(2)节点(Node):集合中的元素称为树的节点,n=0的树称为空树。page number 0

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

根节点:在树形结构中,没有前驱的节点称为根节点(Root),又称为开始节点。

父节点、孩子节点:在树形结构中,对于两个以边直接连接的节点,上端节点称为下端节点的父节点(Parent),下端节点称为上端节点的孩子节点(Child),简称为子节点。

(3)子树:树中某个节点下面所有节点所构成的树称为该节点的子树。

(4)边:树的两个节点之间如果有一条边连接,那么称这两个节点之间存在一条边。

对于一棵有n个节点的树,它有(n-1)条边。

(5)度(Degree)

节点的度:树的一个节点所拥有的子树个数称为该节点的度。

树的度:最大的节点的度称为树的度。

节点的度和树的度共同体现了树的宽度。

(6)叶子节点:度为0的节点称为叶子节点(Leaf),又称为终端节点。

(7)树的深度(高度):树中节点的层数(Level)从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度(Depth)。

2.二叉树

(1)二叉树的定义

二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合,分别称为左子树和右子树,左子树和右子树也是二叉树。

二叉树的所有节点的度都小于或等于2,当n=0时,二叉树是一棵空树。page number 1

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

二叉树的子树有左右之分,且左右子树的次序不能颠倒。

(2)二叉树的高度(深度)

二叉树中节点的最大层数称为二叉树的深度或高度。

(3)二叉树的五种形态:

3.特殊的二叉树

(1)满二叉树

符合满二叉树的两个条件为:

①每个节点的度数为2或为0。

②所有叶子节点都在同一层。

(2)完全二叉树

符合完全二叉树的两个条件为:

①至多只有最下面两层中的节点度数小于2。

②最下一层的叶子节点都依次排列在该层最左边位置。

(3)哈夫曼树

①哈夫曼树又称最优二叉树。

②树的带权路径长度(WPL)的计算公式为:WPL=Wi×Pi,其中,n为树中叶子节点的个数,Wi和Pi分别是第i个叶子节点的权值和从根节点到该路径的长度。page number 2

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。