ch6树和二叉树(冲突_STEVEN-PC_2008-10-29 14-27-06).ppt

6.1 树的定义和基本术语 树形结构是一类重要的非线性数据结构，数据元素之间存在一对多的关系，是以分支关系定义的层次结构。 树的抽象数据类型定义： ADT Tree｛ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树; 若D仅含一个数据元素，则R为空集，否则R＝｛H｝，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－｛root｝≠φ，则存在D－｛root｝的一个划分D1, D2, ..., Dm （m＞0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=φ ，且对任意的i（1≤i≤m），唯一存在数据元素xiξDi，有root,xiξH; （3）对应于D－｛root｝的划分，H－｛root,x1，....，root,xm｝有唯一的一个划分H1 , H2 ,..., Hm （m＞0），对任意j≠k（1≤j,k≤m）有Hj∩Hk=φ ，且对任意的i（1≤i≤m），Hi 是Di上的二元关系，（Di ,{Hi}）是一棵符合本定义的树，称为根root的子树。 基本操作：p119 15个基本操作 } ADT Tree 基本术语： 树的表示方法： 6.2 二叉树 6.2.2 二叉树的性质 性质2：深度为k的二叉树至多有2^k-1 个结点(k?1) 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1 几种特殊形式的二叉树 完全二叉树 完全二叉树和满二叉树的关系： 性质4： 具有n个结点的完全二叉树的深度为 log2n +1； 性质5： 如果对一棵有n个结点的完全二叉树（其深度为 log2 n +1 ）的结点按层序编号（从第1层到第 log2n +1层，每层从左到右），则对任一结点i（1≤i≤n），有：（1）如果i＝1，则结点i是二叉树的根，无双亲；如果i＞1，则其双亲PARENT（i）是结点 i/2 。（2）如果2i＞n，则结点i无左孩子（结点i为叶子结点），否则其左孩子LCHILD（i）是结点2i。（3）如果2i＋1＞n，则结点i无右孩子； 否则其右孩子RCHILD（i）是结点2i+1. 6.2.3 二叉树的存储结构 二、链式存储结构：1.二叉链表 6.3 遍历二叉树和线索二叉树 二叉树遍历的方法： 中序遍历二叉树的递归算法 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(T-lchild,Visit)) if (Visit(T-data)) if (InOrderTraverse(T-rchild,Visit)) return OK; return ERROR; }else return OK;}//InOrderTraverse 后序遍历二叉树的递归算法 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (PostOrderTraverse(T-lchild,Visit)) if (PostOrderTraverse(T-rchild,Visit)) if (Visit(T-data)) return OK; return ERROR; }else return OK;}//PostOrderTraverse 构造二叉链表的二叉树的递归算法： Status CreateBiTree(BiTree T) // 按先序输入二叉树中接点的值，空格字符表示空树， //构造二叉链表表示的二叉树T { scanf(“%c”,ch); if (ch==‘#’) T=NULL; else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW); T-dat