《第6讲C语言.ppt》由会员分享，可在线阅读，更多相关《第6讲C语言.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 哈夫曼树及其应用哈夫曼树及其应用6.8 6.8 树的计数树的计数本章小结本章小结 习习 题题6.1 树的定义和基本树的定义和基本术语术语 树的定义：树树的定义：树(tree)(tree)是是n(n0)n(n0)个结点的有个结点的有限集限集，在任一棵非空树，在任一棵非空树中中：1 1）有且仅有一个特定的称为树）有且仅有一个特定的称为树根根(root)(root)的结点；的结点；2 2）当）当n
2、1n1时，其余结点可分为时，其余结点可分为m(m0)m(m0)个互不相个互不相交的有限集交的有限集T T1 1,T,T2 2,T Tm m，其中每一个集合本身其中每一个集合本身又是一棵树，称为根的又是一棵树，称为根的子树子树(subtreesubtree)。特点：特点：1 1）在非空树中）在非空树中至少有一个结点至少有一个结点根根 2 2）树中各子树是互不相交的集合）树中各子树是互不相交的集合例如例如:A(a)ABCDEFGHIJMKL(b)只有根结点的树根子树有子树的树数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称
3、为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm，其中每一其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系 R：基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类 Root(T)/求树的根结点求树的根结点 查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双
4、亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历InitTree(&T)/初始化置空树初始化置空树 插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i
5、,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空 删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:树的表示方法：树的表示方法：(c)凹入表（a）树形表示ABCDEFIJGH(A(B(D)(E(I)(J)(C(G)(H)(d)嵌套括号表示法CDEIJFGHAB(b)文氏图有序树：有序树：子树之间存在确定的次序关
6、系。无序树：无序树：子树之间不存在确定的次序关系。ABCDEFIJGH对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)基基 本本 术术 语语结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素+若干指向子树的分支分支的个数
7、树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2 二叉树二叉树 二叉树或为空树空树，或是由一个根结根结点点加上两
8、棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树 二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);B
9、iTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉树二叉树的性质的性质(重要特性重要特性)性质性质 1：在二叉树的第 i
10、层上至多有2i-1 个结点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总
11、数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij 性质性质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。