数据结构789树.pptx

该【数据结构789树 】是由【niuww】上传分享，beplayapp体育下载一共【69】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【数据结构789树 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。学时数:48(32+16)
学分:3
教材:严蔚敏等,数据结构(C语言版),清华大学出版社,1997年4月(配题集)
参考书:
[1]殷人昆等,数据结构(用面向对象方法与C++描述),清华大学出版社,1999年7月。￥26
[2]殷人昆等,数据结构****题解析,清华大学出版社,2002年4月。￥26
[3]李春葆,数据结构****题与解析(C语言篇),清华大学出版社,2001年1月。￥28
[4]丁宝康等,数据结构自学考试指导,清华大学出版社,2001年5月。￥23
内容安排
章
内容
学时
章
内容
学时
1
绪论
2
7
图
6
2
线性表
4
8
动态存储管理
略
3
栈和队列
6
9
查找
4
4
串(自学)
2
10
内部排序
4
5
数组和广义表(自学)
4
11
外部排序
略
6
树和二叉树
6
12
文件
略
实验:课内上机(16规定内容)+课外上机(24平时作业中编程题验证)
数据结构课程的内容
各种数据结构的应用
1、树的定义和基本术语 2、二叉树 3、遍历二叉树和线索二叉树 4、树和森林 5、树和等价问题 6、赫夫曼树及其与树的应用 7、回溯法与树的遍历 8、树的计数
目录
第六章树和二叉树
特点:非线性结构,一个直接前驱,但可能有多个直接后继。(一对多或1:n)
1、树的定义和基本术语
(1).树的定义
注:树的定义具有递归性,即“树中还有树”。
由一个或多个(n≥0)结点组成的有限集合T,有且仅有一个结点称为根(root),当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树。
(1).树的定义
(2).若干术语
(3).逻辑结构
(4).存储结构
(5).树的运算
树的表示法主要有5种:
图形表示法
嵌套集合表示法
广义表表示法
凹入表示法
左孩子-右兄弟表示法
1、树的定义和基本术语
自学
图形表示法:
教师
学生
其他人员
2004级
2005级
2006级
2007级
……
南工大信息学院
计算机系
电子系
通信系
……
叶子
根
子树
左孩子-右兄弟表示法
A
B
C
D
E
F
G
H
I
J
K
L
M
数据
左孩子
右兄弟
(2).若干术语
——即上层的那个结点(直接前驱)
——即下层结点的子树的根(直接后继)
——同一双亲下的同层结点(孩子之间互称兄弟)
——即双亲位于同一层的结点(但并非同一双亲)
——即从根到该结点所经分支的所有结点
——即以某结点为根的子树中的任一结点
A
B
C
G
E
I
D
H
F
J
M
L
K
根
叶子
森林
有序树
无序树
——即根结点(没有前驱)
——即终端结点(没有后继)
——指m棵不相交的树的集合(例如删除A后的子树个数)
双亲
孩子
兄弟
堂兄弟
祖先
子孙
——结点各子树从左至右有序,不能互换(左为第一)
——结点各子树可互换位置。
(2).若干术语(续)
——即树的数据元素
——结点挂接的子树数
结点
结点的度
结点的层次
终端结点
分支结点
树的度
树的深度
(或高度)
A
B
C
G
E
I
D
H
F
J
M
L
K
——从根到该结点的层数(根结点算第一层)
——即度为0的结点,即叶子
——即度不为0的结点(也称为内部结点)
——所有结点度中的最大值(Max{各结点的度})
——指所有结点中最大的层数(Max{各结点的层次})
问:右上图中的结点数=;树的度=;树的深度=
13
3
4
(有几个直接后继就是几度,亦称“次数”)