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; }
C语言程序设计 清华大学郑莉安颖莲 二叉树的应用举例 用二叉树表示表达式 二叉排序树
C语言程序设计 清华大学 郑莉 安颖莲 Page 6 二叉树的应用举例 • 用二叉树表示表达式 • 二叉排序树
C语言程序设计 清华大学郑莉安颖莲 二叉树的算法举例 生成二叉排序树 向二叉排序树中插入一个新结点 struct tree *inserttree(root, p struct tree半root,半p; if (root==NULL root=p: e⊥se if(root->info>p->info) o root->left=inserttree(root->left, p) se root->right=inserttree(root->right, p) return (root );
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 skroot if(!root) return inorder (root->left printf( %c", root->info) inorder(root->right)
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 kroot if(root) return printf %c", root->info) preorder (root->left preorder (root->right)
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
C语言程序设计 清华大学 郑莉 安颖莲 Page 10 二叉树的算法举例 ——后序遍历二叉树 postorder(root) struct tree *root; { if(!root) return; postorder(root->left); postorder(root->right); printf("%c",root->info); }