C语言程序设计 清华大学郑莉安颖莲 第十三讲非线性结构 及数据结构应用实例 参考书: ①《计算机程序设计基础》 ②《数据结构(C语言版)》
C语言程序设计 清华大学 郑莉 安颖莲 Page 1 第十三讲 非线性结构 及数据结构应用实例 参考书： ①《计算机程序设计基础》 ②《数据结构（C语言版）》
C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 树和二叉树的概念 二叉树的基本性质 二叉树的链式存储结构 二叉树的应用举例 二叉树的算法举例一生成二叉排序树 二叉树的算法举例一中序遍历二叉树 二叉树的算法举例一先序遍历二叉树 叉树的算法举例一后序遍历二叉树 数据结构应用实例讨论
C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 树和二叉树的概念 • 二叉树的基本性质 • 二叉树的链式存储结构 • 二叉树的应用举例 • 二叉树的算法举例－生成二叉排序树 • 二叉树的算法举例－中序遍历二叉树 • 二叉树的算法举例－先序遍历二叉树 • 二叉树的算法举例－后序遍历二叉树 • 数据结构应用实例讨论
C语言程序设计 清华大学郑莉安颖莲 树和二叉树的概念 树的定义 树是n(n≥0)个结点的有限集合,n为0时称之为空树, 若n不为0,则其中一个结点称为根结点,其余结点分成 m(m≥0)个互不相交的有限集合,其中每个集合又是 棵树,称之为根结点的子树。 二叉树的定义 二叉树是一种特殊的树型结构。 二叉树是结点的有限集合,该集合或是空集,或是一个根 结点加上分别称之为左子树和右子树的两个互不相交的二 叉树组成
C语言程序设计 清华大学 郑莉 安颖莲 Page 3 树和二叉树的概念 • 树的定义 树是n(n≥0)个结点的有限集合，n为0时称之为空树， 若n不为0，则其中一个结点称为根结点，其余结点分成 m(m≥0)个互不相交的有限集合，其中每个集合又是一 棵树，称之为根结点的子树。 • 二叉树的定义 二叉树是一种特殊的树型结构。 二叉树是结点的有限集合，该集合或是空集，或是一个根 结点加上分别称之为左子树和右子树的两个互不相交的二 叉树组成
C语言程序设计 清华大学郑莉安颖莲 二叉树的基本性质 二叉树的五种基本形态 空、一个结点、仅有左子树、仅有右子树、有左右子树 二叉树的性质 在二叉树的第层上,至多有211个结点(i≥1) 深度为k层的二叉树,至多有2k-1个结点(k≥1) 满二叉树 完全二叉树
C语言程序设计 清华大学 郑莉 安颖莲 Page 4 二叉树的基本性质 • 二叉树的五种基本形态 空、一个结点、仅有左子树、仅有右子树、有左右子树。 • 二叉树的性质 -在二叉树的第i层上，至多有2 i-1个结点（i≥1)。 -深度为k层的二叉树，至多有2 k -1 个结点（k≥1)。 • 满二叉树 • 完全二叉树
C语言程序设计 清华大学郑莉安颖莲 叉树的链式存储结构 设计不同的结点结构可以构成不同形式的链式 存储结构 struct tree char info struct tree left struct tree *right
C语言程序设计 清华大学 郑莉 安颖莲 Page 5 二叉树的链式存储结构 • 设计不同的结点结构可以构成不同形式的链式 存储结构 • struct tree { char info; struct tree *left; struct tree *right; }