中南大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 数据结构与算法概述（2.5）树 2.5.1 树的定义 2.5.2 二叉树（Binary Tree）

线性表 A.线性结构〈栈 数1.数据的逻辑结构 队 树形结构 据结构的三个主要问题 B.非线性结构 图形结构 2、数据的存储结构A顺序存储 B链式存储 3、数据的运算:检索、排序、插入、删除、修改等。 2/22 202l/2/

2021/2/22 2 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数 据 结 构 的 三 个 主 要 问 题

线性结构 A.B.C ,Ⅹ,Y,Z 线性表—结点间是以线性关系联结 学生成绩表 学号 姓名 成绩 9861109 张卓 100 9861107 刘忠赏 95 9861103 胡孝臣 86 2/22 202l/2/

2021/2/22 3 线性结构 A , B , C , ······· ，X ,Y , Z 学 生 成 绩 表 9861103 胡孝臣 86 9861107 刘忠赏 95 9861109 张卓 100 学号 姓名 成绩 线性表——结点间是以线性关系联结

线性表 A.线性结构栈 队 1.数据的逻辑结构 树形结构 数据结构的三个方面 B.非线性结构 图形结构 2、数据的存储结构A顺序存储 B链式存储 3、数据的运算:检索、排序、插入、删除、修改等。 2/22 202l/2/

2021/2/22 4 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数 据 结 构 的 三 个 方 面

树形结构 学校 系别 计算机系 数学系 物理系 专业计算机应用计算机软件数学 理论物理应用物理 班级991…95991……199…1 991 995991…995 学生张力……李扬 赵壮……王芳 全校学生档案管理的组织方式 2/22 202l/2/

2021/2/22 5 树形结构 全校学生档案管理的组织方式

A D B E FG H A B C E F G H 树形结构—结点间具有分层次的连接关系 202l/2/22

2021/2/22 6 A B C D E F G H 树形结构 —— 结点间具有分层次的连接关系 H B C D E F G A

25树 25.1树的定义:由一个或多个结点组成的有限集合。仅有 个根结点,结点间有明显的层次结构关系。 A B E G 现实世界中,能用树的结构表示的例子: 学校的行政关系、书的层次结构、人类的家族血缘关 系等。 202l/2/22

2021/2/22 7 2.5 树 2.5.1 树的定义：由一个或多个结点组成的有限集合。仅有 一个根结点，结点间有明显的层次结构关系。 A C G T2 D H I T3 J M B E K L T1 F 现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关 系等

介绍几个概念: 结点(Node):树中的元素,包含数据项及若干指向其 子树的分支。 结点的度( Degree):结点拥(A子树数。 结点的层次:从根结点开始算起,根为第一层。 叶子(Lea)为零的结点称端 孩子(T B 么 兄弟 E G 双亲 双亲 深度(K ① 结点的取层 森林( Forest,):M棵互不相交的枓 2021/2/22

2021/2/22 介绍几个概念： 8 结点（Node）：树中的元素，包含数据项及若干指向其 子树的分支。 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点，称为这些结点的 双亲。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：M棵互不相交的树的集合。 A C G T2 D H I T3 J M B E K L T1 F

252二叉树( Binary Tree) 1、二叉树的定义及其性质 (1)二叉树的定义 因为树的每个结点的度不同,存储困难,使对树的处理算法! 很复杂。所以引出二叉树的讨论。 仅有 右子树 空二叉树根结点为空 左子树 左右子树 为空 均非空 二叉树的五种基本形态 202l/2/22

2021/2/22 9 2.5.2 二叉树 （Binary Tree） 1 、二叉树的定义及其性质 (1) 二叉树的定义 二叉树的五种基本形态 二叉树一种特殊的树型结构，特点是树中每个结点只有两棵 子树，且子树有左右之分，次序不能颠倒。 空二叉树 仅有 根结点 右子树 为空 左子树 为空 左右子树 均非空 因为树的每个结点的度不同，存储困难，使对树的处理算法 很复杂。所以引出二叉树的讨论

10 二叉数是n(n≥0)个结点的有限集合。它或为空 数(n=0),或由一个根结点和两棵分别称为根的左子 树和右子树的互不相交的二叉数组成。 特别要注意:二叉数不是树的特殊情况。 a a 两棵不同的二叉数 2/22 202l/2/

2021/2/22 10 二叉数是n(n0)个结点的有限集合。它或为空 数(n=0),或由一个根结点和两棵分别称为根的左子 树和右子树的互不相交的二叉数组成。 特别要注意：二叉数不是树的特殊情况。 a a b b 两棵不同的二叉数

ll (2)二叉树的基本性质 A、二叉树的第谌上至多有2H(i≥1)个结点。 6 14 第三层上(i=3),有23-1=4个节点。 第四层上(i=4),有24-1=8个节点。 2/22 202l/2/

2021/2/22 11 A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 (2) 二叉树的基本性质 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 第三层上(i=3)，有2 3-1=4个节点。 第四层上(i=4)，有2 4-1=8个节点