第六章 树和二叉树：树的定义和基本术语 树的存储 二叉树 遍历二叉树和线索二叉树 树、森林与二叉树的转换 赫夫曼树及其应用.ppt

树的定义和基本术语 树的存储 二叉树 遍历二叉树和线索二叉树 树、森林与二叉树的转换 赫夫曼树及其应用 树的类型定义 数据对象 D： D是具有相同特性的数据元素的集合。 数据关系 R： 若D为空集，则称为空树 。 否则: 在D中存在唯一的称为根的数据元素root； 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 树的逻辑特征： 树中只有根结点无直接前驱 除了根结点，其余结点都有且仅有一个直接前驱 树中每个结点可以有零个或多个直接后继 基本术语 结点 结点的度 叶子结点或终端结点 分支结点或非终端结点 树的度 孩子和双亲 兄弟 祖先和子孙 结点的层次 堂兄弟 树的深度 基本术语 有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。 森林：森林是m棵互不相交的树的集合。 左孩子右兄弟表示法 二叉树的类型定义 二叉树是n（n≥0）个结点的有限集，它或者为空，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树的特点： 二叉树的度小于等于2 二叉树是一棵有序树 二叉树的五种形态： 二叉树的性质 性质1 在二叉树的第i层上至多有 2i－1个结点。 性质2 深度为k的二叉树至多有 2k-1个结点(k?1)。 性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0＝n2＋1。 两类特殊形态的二叉树 满二叉树：深度为k，且有2k-1个结点的二叉树。 完全二叉树：深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。 二叉树的性质 性质4 具有 n (n ? 0) 个结点的完全二叉树的深度为?log2(n) ?＋1。 性质5 如果对一棵有n个结点的完全二叉树的结点按层次顺序编号，则对任一结点有： 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点 i/2 如果2in，则结点i无左孩子；否则其左孩子是结点2i 如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1 在一棵度为m树中，度为1的结点数为n1，度为2的结点数为n2，……，度为m的结点数为nm，则该数中含有多少个叶子结点？有多少个非终端结点？ 二叉树的顺序存储表示 按满二叉树的结点层次编号，用一组地址连续的存储单元，依编号存放二叉树中的数据元素，结点的相对位置蕴含着结点之间的关系。 二叉树的二叉链表存储表示 结点结构 二叉链表的类型描述 typedef char TElemType; typedef struct BiNode{ TElemType data; struct BiNode *lchild; struct BiNode *rchild; }BiTNode,*BiTree; 遍历二叉树定义： 按某条有哪些信誉好的足球投注网站路径巡访二叉树中的结点，使得每个结点均被访问，且仅被访问一次。 先序遍历二叉树 若二叉树为空，则空操作；否则 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历二叉树 若二叉树为空，则空操作；否则 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历二叉树 若二叉树为空，则空操作；否则 后序遍历左子树 后序遍历右子树 访问根结点 思考1： 满足下列条件的所有二叉树： 1、先序序列和中序序列相同 2、中序序列和后序序列相同 3、先序序列和后序序列相同 思考2： 1、怎样由二叉树的先序序列和中序序列构造一颗二叉树？ 2、怎样由二叉树的后序序列和中序序列构造一颗二叉树？ 先序序列为： 中序序列为： 例如： 后序序列为：D E B H F G C A 中序序列为：D B E A H F C G 画出该二叉树 二叉树遍历算法递归实现 void InOrder ( BiTNode *T ) { if ( T != NULL ) { InOrder ( T-lChild ); Visit( T-data); InOrder ( T-rChild ); } } 二叉树遍历非递归算法的实现 －－借助栈实现 在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需通过栈来进行。 为了保证递归函数的正确执行，系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶，每退出一层递归，就从栈顶弹出一个工作记录