[理学]第六章 树和二叉树.ppt

第六章 树和二叉树 一、教学内容： 1、树和森林的概念（树的定义、树的术语、性质及运算）； 2、二叉树的定义、性质及运算； 3、二叉树的存储结构（顺序、链式表示）； 4、遍历二叉树 5、树的存储结构；树、森林与二叉树的转换；遍历树和森林 6、哈夫曼树、哈夫曼编码。 二、教学要求： 1、了解树和森林的概念。包括树的定义、树的术语和性质； 2、熟悉二叉树的各种存储结构的特点及适用范围； 3、熟练掌握二叉树的遍历方法及遍历算法； 4、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法 5、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 树的定义 定义：树(tree)是n(n0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合 图形表示法： 性质1：在二叉树的第i层上最多有2i-1个结点（i=1） 特殊形式的二叉树 满二叉树 定义：如果深度为k的二叉树，有2k-1个结点则称为满二叉树； 特点：每一层上的结点数都是最大结点数 性质4： 假设深度为k,则： 2k-1-1n= 2k-1 即： 2k-1=n 2k k-1=log2nk 由于k为整数，所以k= 的整数。 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点：1、结点间关系蕴含在其存储位置中 2、浪费空间，只适于存满二叉树和完全二叉树 6.3 遍历二叉树和线索二叉树 6.3.1 什么是遍历 一种按某种方式系统地访问二叉树中的所有结点的过程，使每个结点都被访问一次且只被访问一次。 遍历的分类 1、深度优先遍历 先序遍历、中序遍历、后序遍历 2、广度优先遍历 逐层处理：从上到下、从左到右访问各结点 先序遍历：先访问根结点，然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 2005年 试题 假设一棵二叉树的后序遍历序列为 D G J H E B I F C A，中序遍历序列为 D B G E H J A C I F，则其前序遍历序列 为 。 A）A B C D E F G H I J B）A B D E G H J C F I C）A B D E G H J F I C D）A B D E G J H C F I 2006试题2 二叉树的查找有深度优先和广度优先二类，深度优先包括 C 。当一棵二叉树的前序序列和中序序列分别是 H G E D B F C A 和 E G B D H F A C时，其后序序列必是 D ,层次序列为 E . C: (1)前序遍历 后序遍历 中序遍历 (2)前序遍历 后序遍历 层次遍历 (3)前序遍历 中序遍历 层次遍历 (4)中序遍历 后序遍历 层次遍历 D: (1) B D E A G F H C (2) E B D G A C F H (3) H G F E D C B A (4) H F G D E A B C 软件设计师 2004上半年 设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。 A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后裔 非递归算法 先根算法 Void preOrder(BinTree t) Stack s; BinTreeNode *c; If(t==Null) return; InitStack(s);push(s,t); While(! StackEmpty (s)){ c=top(s);pop(s); if(c!=Null) { visit(root(c)); push(s,c-rchild); push(s,c-lchild);}} 中根算法 Void InOrder(BinTree t) InitStack(s); push(s,t); While(! StackEmpty (s)) { while(GetTop(S,p) p) push(S,p-lchild); pop(