C语言程序设计 清华大学 郑莉 安颖莲
Page 1
第十三讲 非线性结构及数据结构应用实例参考书：
①,计算机程序设计基础,
②,数据结构（ C语言版）,
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
树和二叉树的概念
二叉树的基本性质
二叉树的链式存储结构
二叉树的应用举例
二叉树的算法举例－生成二叉排序树
二叉树的算法举例－中序遍历二叉树
二叉树的算法举例－先序遍历二叉树
二叉树的算法举例－后序遍历二叉树
数据结构应用实例讨论
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
树和二叉树的概念
树的定义树是 n(n≥0) 个结点的有限集合,n为 0时称之为空树，
若 n不为 0，则其中一个结点称为根结点，其余结点分成
m(m≥0) 个互不相交的有限集合，其中每个集合又是一棵树，称之为根结点的子树。
二叉树的定义二叉树是一种特殊的树型结构。
二叉树是结点的有限集合，该集合或是空集，或是一个根结点加上分别称之为左子树和右子树的两个互不相交的二叉树组成。
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
二叉树的基本性质
二叉树的五种基本形态空、一个结点、仅有左子树、仅有右子树、有左右子树。
二叉树的性质
-在二叉树的第 i层上，至多有 2i-1个结点（ i≥1) 。
-深度为 k层的二叉树，至多有 2k -1 个结点（ k≥1) 。
满二叉树
完全二叉树
C语言程序设计 清华大学 郑莉 安颖莲
Page 5
二叉树的链式存储结构
设计不同的结点结构可以构成不同形式的链式存储结构
struct tree
{
char info;
struct tree *left;
struct tree *right;
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 6
二叉树的应用举例
用二叉树表示表达式
二叉排序树
C语言程序设计 清华大学 郑莉 安颖莲
Page 7
二叉树的算法举例
—— 生成二叉排序树
向二叉排序树中插入一个新结点
struct tree *inserttree(root,p)
struct tree *root,*p;
{
if(root==NULL)
root=p;
else
{
if(root->info>p->info)
root->left=inserttree(root->left,p);
else
root->right=inserttree(root->right,p);
}
return(root);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
二叉树的算法举例
—— 中序遍历二叉树
inorder(root)
struct tree *root;
{
if(!root) return;
inorder(root->left);
printf("%c",root->info);
inorder(root->right);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
二叉树的算法举例
—— 先序遍历二叉树
preorder(root)
struct tree *root;
{
if(!root) return;
printf("%c",root->info);
preorder(root->left);
preorder(root->right);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
二叉树的算法举例
—— 后序遍历二叉树
postorder(root)
struct tree *root;
{
if(!root) return;
postorder(root->left);
postorder(root->right);
printf("%c",root->info);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
数据结构应用实例讨论（一）
—— 如何处理一个稀疏矩阵
实例,电子表格程序
功能：
- 存储电子表格。
- 在电子表格中插入、删除、
查找单元内容。
- 显示全部内容。
方法：
- 链表法；
- 二叉树法；
- 指针数组法。
表格单元存储结构：
struct cell
{
char cell_name[9];
char formula[128];
struct cell *next;
struct cell *prior;
}
主要子函数,13-1.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
数据结构应用实例讨论（二）
—— 文本编辑程序
功能：
- 接收键盘输入。每行不超过 80个字符，行数不定。
- 显示全部已输入内容。
- 指定行号显示某一行。
- 指定行号删除某一行。
- 指定行号重写某一行。
- 在指定行号之前插入一行。
处理方法 — 链表
行存储结构
struct line
{ char text[81];
int num;
struct line *next;
};
C语言程序设计 清华大学 郑莉 安颖莲
Page 13
数据结构应用实例讨论（三）
—— 排序（应用二叉排序树）
程序功能：
- 接收键盘输入的若干个整数（整数个数不定，以 -32767为结束标记，整数之间以空格隔开），用二叉排序树进行排序，并显示输出排序后的序列。
分析：
- 数据结构：
定义二叉排序树结点结构，包含有数据、左子树指针、右子树指针。
- 算法要点：
将一个无序序列的各元素逐个插入到二叉排序数中，再用中序遍历二叉树便可得到一个有序序列。
程序,13-2.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 14
作 业
编写一简单的 电子表格程序,功能如前所述。单元格内容全部为字符串，不考虑公式计算。改用有头结点的单向链表。
从键盘输入若干学生的信息（人数不定），每条信息包括：姓名（字符串）、学号（整数）、班级（字符串），用二叉排序数对上述信息按姓名进行排序，并将排序后的信息存入文本文件中。
选做：
编写一个简单的 文本编辑程序,基本功能如前所述。其它功能自行设计。
Page 1
第十三讲 非线性结构及数据结构应用实例参考书：
①,计算机程序设计基础,
②,数据结构（ C语言版）,
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
树和二叉树的概念
二叉树的基本性质
二叉树的链式存储结构
二叉树的应用举例
二叉树的算法举例－生成二叉排序树
二叉树的算法举例－中序遍历二叉树
二叉树的算法举例－先序遍历二叉树
二叉树的算法举例－后序遍历二叉树
数据结构应用实例讨论
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
树和二叉树的概念
树的定义树是 n(n≥0) 个结点的有限集合,n为 0时称之为空树，
若 n不为 0，则其中一个结点称为根结点，其余结点分成
m(m≥0) 个互不相交的有限集合，其中每个集合又是一棵树，称之为根结点的子树。
二叉树的定义二叉树是一种特殊的树型结构。
二叉树是结点的有限集合，该集合或是空集，或是一个根结点加上分别称之为左子树和右子树的两个互不相交的二叉树组成。
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
二叉树的基本性质
二叉树的五种基本形态空、一个结点、仅有左子树、仅有右子树、有左右子树。
二叉树的性质
-在二叉树的第 i层上，至多有 2i-1个结点（ i≥1) 。
-深度为 k层的二叉树，至多有 2k -1 个结点（ k≥1) 。
满二叉树
完全二叉树
C语言程序设计 清华大学 郑莉 安颖莲
Page 5
二叉树的链式存储结构
设计不同的结点结构可以构成不同形式的链式存储结构
struct tree
{
char info;
struct tree *left;
struct tree *right;
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 6
二叉树的应用举例
用二叉树表示表达式
二叉排序树
C语言程序设计 清华大学 郑莉 安颖莲
Page 7
二叉树的算法举例
—— 生成二叉排序树
向二叉排序树中插入一个新结点
struct tree *inserttree(root,p)
struct tree *root,*p;
{
if(root==NULL)
root=p;
else
{
if(root->info>p->info)
root->left=inserttree(root->left,p);
else
root->right=inserttree(root->right,p);
}
return(root);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
二叉树的算法举例
—— 中序遍历二叉树
inorder(root)
struct tree *root;
{
if(!root) return;
inorder(root->left);
printf("%c",root->info);
inorder(root->right);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
二叉树的算法举例
—— 先序遍历二叉树
preorder(root)
struct tree *root;
{
if(!root) return;
printf("%c",root->info);
preorder(root->left);
preorder(root->right);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
二叉树的算法举例
—— 后序遍历二叉树
postorder(root)
struct tree *root;
{
if(!root) return;
postorder(root->left);
postorder(root->right);
printf("%c",root->info);
}
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
数据结构应用实例讨论（一）
—— 如何处理一个稀疏矩阵
实例,电子表格程序
功能：
- 存储电子表格。
- 在电子表格中插入、删除、
查找单元内容。
- 显示全部内容。
方法：
- 链表法；
- 二叉树法；
- 指针数组法。
表格单元存储结构：
struct cell
{
char cell_name[9];
char formula[128];
struct cell *next;
struct cell *prior;
}
主要子函数,13-1.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
数据结构应用实例讨论（二）
—— 文本编辑程序
功能：
- 接收键盘输入。每行不超过 80个字符，行数不定。
- 显示全部已输入内容。
- 指定行号显示某一行。
- 指定行号删除某一行。
- 指定行号重写某一行。
- 在指定行号之前插入一行。
处理方法 — 链表
行存储结构
struct line
{ char text[81];
int num;
struct line *next;
};
C语言程序设计 清华大学 郑莉 安颖莲
Page 13
数据结构应用实例讨论（三）
—— 排序（应用二叉排序树）
程序功能：
- 接收键盘输入的若干个整数（整数个数不定，以 -32767为结束标记，整数之间以空格隔开），用二叉排序树进行排序，并显示输出排序后的序列。
分析：
- 数据结构：
定义二叉排序树结点结构，包含有数据、左子树指针、右子树指针。
- 算法要点：
将一个无序序列的各元素逐个插入到二叉排序数中，再用中序遍历二叉树便可得到一个有序序列。
程序,13-2.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 14
作 业
编写一简单的 电子表格程序,功能如前所述。单元格内容全部为字符串，不考虑公式计算。改用有头结点的单向链表。
从键盘输入若干学生的信息（人数不定），每条信息包括：姓名（字符串）、学号（整数）、班级（字符串），用二叉排序数对上述信息按姓名进行排序，并将排序后的信息存入文本文件中。
选做：
编写一个简单的 文本编辑程序,基本功能如前所述。其它功能自行设计。
