第1章数据结构ppt课件.ppt

《第1章数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数据结构1.1数据结构的基本概念1.2线性结构1.3非线性结构1.4查找与排序1.3.1树1.3.2图1.3非线性结构逻辑结构1.3.1树与二叉树1.3.1.1树的基本概念1.3.1.2二叉树及其基本性质1.3.1.3二叉树的存储结构1.3.1.4二叉树的遍历1.3.1.5二叉排序树1.3.1.6树、森林与二叉树的转换1.3.1.7二叉树应用举例父结点：每一个结点只有一个前件，称为父结点。子结点：每一个结点可以有多个后件，都称为该结点的子结点。根结点：没有前件的结点只有一个，称为树的根结点。叶子结点：没有后件的结点称为叶子结点。1.3.1.1树的基本概念结点的度：一个结

2、点所拥有的后件个数称为该结点的度。度树的度：所有结点中的最大度称为树的度。树的深度：树的最大层次称为树的深度。子树:在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。1.3.1.1树的基本概念父结点、根结点、子结点、叶子结点、结点的度、树的度、树的深度1.3.1.1树的基本概念1.3.1.1树的基本概念1.3.1.1树的基本概念树链表中的结点结构1.3.1.1树的基本概念1.3.1树与二叉树1.3.1.1树的基本概念1.3.1.2二叉树及其基本性质1.3.1.3二叉树的存储结构1.3.1.4二叉树的遍历1.3.1.5二叉排序树1.3.1.6树、森林与二叉树的转换1

3、.3.1.7二叉树应用举例1.什么是二叉树(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。1.3.1.2二叉树及其基本性质例画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，1.3.1.2二叉树及其基本性质例画出具有3个结点的树和二叉树的所有不同形态。解：(2)具有3个结点的二叉树有5种不同的形态，树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树。即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。1.3.1.2二叉树及其基本性质2.二叉树的基本性质性质1在二

4、叉树的第k层上，最多有2k－1(k≥1)个结点。性质2深度为m的二叉树最多有2m－1个结点。性质3在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4具有n个结点的二叉树，其深度至少为[log2n]＋1其中[log2n]表示取log2n的整数部分。1.3.1.2二叉树及其基本性质3.满二叉树与完全二叉树满二叉树除了最后一层外，每一层上的所有结点都有两个子结点。1.3.1.2二叉树及其基本性质(2)完全二叉树除了最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。1.3.1.2二叉树及其基本性质1.3.1.2二叉树及其基本性质性

5、质5具有n个结点的完全二叉树的深度为[log2n]＋1。性质6设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k(k＝1，2，…，n)的结点有以下结论：(1)若k＝1，则该结点为根结点，它没有父结点；若k＞1，则该结点的父结点编号为INT(k/2)。1.3.1.2二叉树及其基本性质123456789101211(2)若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。(3)若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。1234567

6、891011121.3.1.2二叉树及其基本性质1.3.1树与二叉树1.3.1.1树的基本概念1.3.1.2二叉树及其基本性质1.3.1.3二叉树的存储结构1.3.1.4二叉树的遍历1.3.1.5二叉排序树1.3.1.6树、森林与二叉树的转换1.3.1.7二叉树应用举例1.二叉链表#include"stdlib.h"structbtnode/*定义结点类型*/{ETd；/*数据域*/structbtnode*lchild；/*左指针域*/structbtnode*rchild；/*右指针域*/}；1.3.1.3二叉树的存储结构1.3.1.3二叉树的存储结构1.3.1.3二叉树

7、的存储结构2.二叉链表的生成(1)输入根结点值；(2)若左子树不空，则输入左子树，否则输入一个结束符；(3)若右子树不空，则输入右子树，否则输入一个结束符。1.3.1.3二叉树的存储结构例如，FA▲▲DB▲▲▲E▲GH▲▲P▲▲其中▲表示结束符C1.3.1.3二叉树的存储结构二叉链表的生成#include"stdio.h”#include"stdlib.h”structbtnode{intd；structbtnode*lchild；structbtnode*rchild；}；structbtnode*c