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