第06章 树.pptVIP

第六章 树 教学目的与要求 本章目的是介绍二叉树的定义、性质、存储结构、二叉树遍历、线索化，树的定义、存储结构、树遍历，树和森林与二叉树的转换，哈夫曼树和哈夫曼编码等内容。要求在熟悉这些内容的基础上，重点掌握二叉树的遍历算法及其有关应用。 重点和难点 重点掌握二叉树的遍历算法及其有关应用。难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树有关的应用问题。 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 6.1 树的定义 定义 定义：树(tree)是n(n0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合 基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m?0)棵互不相交的树的集合 6.2 二叉树 定义 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态 二叉树性质 性质1： 几种特殊形式的二叉树 满二叉树 定义： 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 链式存储结构 二叉链表 性质5：对于具有n个结点完全二叉树，我们从根结点起，自上而下，从左到右给所有结点编号，假设编号为i的结点为ki(1≤i≤n)，则有： ①若i1，则ki的双亲编号为；若i＝1，则ki是根结点，无双亲； ②若2i≤n，则ki的左孩子编号为2i；否则，ki无左孩子。即完全 二叉树中编号i的结点必定是叶子结点。 ③若2i+1≤n，则ki的右孩子编号为2i+1。 ④若i为奇数且不为1，则ki的左兄弟编号为i-1。 ⑤若i为偶数且小于n，则ki的右兄弟编号为i+1。 6.3 二叉树的遍历 二叉树的遍历是指沿着某条有哪些信誉好的足球投注网站路线，对树中每个结点做一次且仅一次访问。 方法 按层次遍历：从上到下、从左到右访问各结点 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 自然语言描述的遍历算法 （1）先序遍历算法 若二叉树非空，则： ①访问根结点； ②先序遍历左子树； ③先序遍历右子树。 C语言描述的遍历算法（以先序遍历算法为例） void preorder(Bintree T) {//先序遍历T所指二叉树，算法中①、②、③是为说明方便额外添加的 if(T) { ① printf(＂%c＂,T-data); //这里用printf语句代表一般访问 ②　preorder(T-lchild); ③　preorder(T-rchild); }//preorder 中序遍历算法 若二叉树非空，则： ①中序遍历左子树； ②访问根结点； ③中序遍历右子树。 中序遍历算法将语句①、②互换，函数名作对应改变即可 后序遍历算法 若二叉树非空，则： ①后序遍历左子树； ②后序遍历右子树； ③访问根结点。 后序遍历算法将语句①移至语句③之后即可。 可以看出，二叉树是一个递归定义，上述算法也是递归算法，若用非递归算法，则应引入工作栈方可。遍历过程访问结点所得结点序列称为遍历序列，即先序遍历序列、中序遍历序列、后序遍历序列。遍历算法的时间复杂度为O(n)。 遍历算法的应用 遍历是二叉树的最重要的运算之一，它是二叉树上其它运算的基础。能够访问到每一个结点，就可以对结点做各种操作。因此，许多涉及二叉树的操作都是二叉树遍历算法的直接应用或变形。例如：统计二叉树中某类结点的个数；将二叉树中各结点的左、右子树互换；求某个结点的位置；建立二叉树；求二叉树的高；释放二叉树中所有结点；建立线索二叉树等。 例 1：建立二叉树 void creatbintr