第06章-1 树和二叉树.ppt

第六章 树和二叉树 6.1 树的定义和基本术语 树的定义 二叉树的定义 是结点的有限集合。该集合或者为空集，或者由一个根及两棵互不相交的称为这个根的左子树和右子树的二叉树构成。 二叉树中每个结点的度不大于2. 二叉树的五种基本状态 二叉树抽象数据类型定义 二叉树的性质 二叉树的性质 例:请分别写出二叉树的先序、中序和后序序列 二叉树的遍历 遍历序与二叉树的对应 前序遍历序+中序遍历序唯一确定二叉树 后序遍历序+中序遍历序唯一确定二叉树 二叉树的遍历 遍历的算法描述(采用二叉链表结构) 递归描述 非递归描述 二叉树的遍历 遍历思想的应用：创建二叉树 二叉树的遍历 遍历的算法描述 递归描述 非递归描述 记录“来时未访问的结点” 二叉树的遍历 遍历的算法描述 递归描述 非递归描述 线索二叉树 结构定义 * 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 树(Tree)是n(n0)个结点的有限集T，非空树满足以下条件: 有且仅有一个特定的称为根的结点; (2) 除根结点外的其余结点可分为m(m0)个互不相交的有限集T1,T2...Tm,其中,每一个集合本身又是一棵树, 并且称为根的子树。 (a)是有13个结点的树,其中A是根,其余结点分成三个互不相交的子树； (b)是只有一个根结点的树; 6.1 树的定义和基本术语 树的描述 树型结构的其他表示方法：广义表表示 (A(B(E(K,L),F),C(G),D(H(M),I,J)))集合表示  B H M J I F D A K L E C G A B E F C D G H J K I 凹入表示 L M 树的结点：包含一个数据元素及若干个指向其子树的分支。 结点的度：结点拥有的子树数。 树的度：树内各结点的度的最大值。 叶子（终端结点）：度为零的结点。 非终端结点（分支结点）：度不为零的结点。 孩子、双亲、兄弟、祖先、子孙 结点的层次和树的深度、堂兄弟 有序树和无序树 森林：是m棵互不相交的树的集合 6.1 树的定义和基本术语 树的基本术语 (a) 空二叉树 A (b) 根和空的左右子树 A (c) 根和左子树 A (d) 根和右子树 A (e) 根和左右子树 6.2 二叉树 ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：R={H} 存在唯一根结点root。 若D-{root}不为空，则存在互不相交的集合{DL,DR}，分别表示左/右子树的元素集合。 若DL不为空，则存在唯一结点xL与root存在有序关系root,xL∈H，且存在DL上的一组关系HL ∈H. 若DR不为空…… (4) (DL,{HL}) 与 (DR,{HR}) 是符合本定义的二叉树. } 6.2 二叉树 H={root,xL,root,xR,HL,HR} 二叉树抽象数据类型定义 基本操作： InitBiTree(T) DestroyBiTree(T) CreateBiTree(T,definition) BiTreeEmpty(T) BiTreeDepth(T) Parent(T,e) LeftChild(T,e) InsertChild(T,p,LR,C) DeleteChild(T,p,LR) Traverse(T,Visit()) 6.2 二叉树 性质1：在二叉树的第i层上至多有2i-1个结点(i=1) 性质2：深度为k的二叉树至多有2k-1个结点。 性质3：对于任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1 满二叉树：一棵深度为k且有2k-1个结点的二叉树。 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。 6.2 二叉树 性质4：具有n个结点的完全二叉树的深度为└log2n┘+1 性质5：如果对一棵n个结点的完全二叉树的结点按层序编号，则对任意结点编号i(1≤i≤n)，有 (1)若i=1，该结点为根，它无双亲结点； (2)若i1，该结点的双亲结点编号为└i/2┘； (3)若2in，则结点i没有左孩子,否则有编号为2i的左孩子； (4)若2i+1n，则结点i没有右孩子，否则有编号为2i+1的右孩子。 6.2 二叉树 顺序存储结构 连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。 a b c d e f g h i j