数据结构与程序设计（6）.pptVIP

数据结构与　程序设计----第六章 上海东华大学 第六章　树 6．1　树的基本概念和术语 1．树的定义 树是由一个或多个结点组成的有限集合T，其中： （1）有一个特定的结点称为该树的根结点； （2）除了根结点之外的其它结点可以分为m（m≥0）个互不相交的集合T1，T2，…，Tm，且其中每个集合又是一棵树，称为根结点的子树。 　　这是一个递归的定义，即在定义树的时候又用到了树这个术语。 2．树的有关术语 （1）祖先结点和子孙结点： 　如果从结点x有一条路径通到结点y，则称结点x是结点y的祖先，或称结点y是结点x的子孙。 （2）父结点和儿子结点： 　如果结点x有一条边直接连接到结点y，即y是x的子树的根结点，则称结点x是结点y的父结点，或称结点y是结点x的儿子结点。 （3）兄弟结点： 　　具有同一个父结点的各结点称为兄弟结点。 （4）树叶结点和非树叶结点： 　　没有儿子结点的结点称为树叶结点，也称终结点；具有儿子结点的结点称为非树叶结点，也称非终结点。 （5）度： 　一个结点的度是指该结点的儿子结点数；一棵树的度是指该树中各结点的度的最大值。 （6）层次： 　　结点的层次值从根结点开始算起，根结点的层次值是1，其它结点的层次值是其父结点的层次值加1。 （7）高度和深度： 　　树中结点的最大层次称为树的高度或深度。 （8）森林：m（m≥0）棵互不相交的树构成森林。对树中的每个结点来说，其子树的集合即为森林，如图6.1的树去掉根结点A以后，其三棵子树就构成了森林。 6．2　二叉树 1．二叉树的定义 　　二叉树是n（n≥0）个结点的集合，它或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。 二叉树的五种基本形态：(a)空二叉树；(b)只有根结点的二叉树；(c)右子树为空的二叉树；(d)左子树为空的二叉树；(e)左、右子树都非空的二叉树。 特点:每个结点最多只能有两棵子树，而且它的子树有左右之分，其次序不能互换。 两种特殊的二叉树：满二叉树和完全二叉树 （1）满二叉树 如果一棵二叉树深度为k，它的结点数为2 k-1个，则称它为满二叉树。 　　满二叉树是每层上的结点数达到最大值，树中不存在度为1的结点，且树叶结点都集中在最下层。对满二叉树的结点可以从根结点开始自上向下，自左向右用自然数编号： （2）完全二叉树 对一棵深度为k的二叉树，其所有树叶结点都在第k或k-1层，第k-1层的非树叶结点都在左边，树叶结点都在右边，且允许第k-1层最右边的非树叶结点可以仅有左子树而没有右子树，树中其它非树叶结点的度为2（即左右子树都存在），这样的二叉树被称为完全二叉树。 完全二叉树也可以从根结点开始自上向下，自左向右用自然数编号。 2 ．二叉树的性质 [性质1] 在二叉树的第k（k≥1）层上最多有2 k-1个结点。 [性质2] 深度为k（k≥1）的二叉树最多有2 k-1个结点。 [性质3] 对任意二叉树，如果其树叶结点数是n0，度为2 的结点数为n2，则n0=n2+1。 [性质4] 具有n个结点的完全二叉树，它的深度是log2[ n]+1，其中括号[x]表示取不大于x的最大整数。 [性质5] 如果一棵n个结点的完全二叉树从根结点开始自上向下，自左向右用自然数编号，则对编号为k的（1≤k≤n）结点,有： （1）如果k=1，则第k个结点是根结点，它没有父结点；如果k1，则编号[k/2]的结点是它的父结点。 （2）如果2kn，则第k个结点没有左儿子结点；否则其左儿子结点编号是2k。 （3）如果2k+1n，则第k个结点没有右儿子结点；否则其右儿子结点编号是2k+1。 3．二叉树的存储结构 （1）顺序存储结构 　　用数组来存储二叉树，而这种存储方式适用于满二叉树和完全二叉树。 　　对完全二叉树可以按各结点的编号依次存储在一维数组中，这时结点的编号与数组的下标一致。根据二叉树性质5，我们可以方便地找出指定结点的父结点和左右儿子结点。顺序存储的完全二叉树又被称为顺序二叉树。 2．链接存储结构 　链接存储时，二叉树的每个结点至少由三个域组成：一个数据域用于存放数据元素，两个指针域用于分别指向左右子树。 定义结点的结构： typedef struct treenode{ char info; struct treenode ＊llink,＊rlink; } TREENODE; 4．二叉树的建立 用字符序列建立二叉树的方法 ，写出的字符串是从根结点开始，然后沿左子树，左子树结点写完后再沿右子树，遇到子树空时输入“00”。下图二叉树，输入的字符序列是：ABD000000CE00G00