树概念+二叉树性质存储(2学时多).ppt

知识回顾 线性数据结构共同特点:? 线性表 栈与队列 串 数组与广义表 1:1 关系 1:n 关系? 第6章 树和二叉树 例子: 组织机构图: 族谱关系图: 系统模块功能结构图: 共同点? 6.1 树的定义和基本术语 教学目标: 掌握树和二叉树的基本概念 熟练掌握二叉树的特点和基本性质 重点: 二叉树的性质 难点: ADT定义 １.树的定义：是n(n=0)个结点的有限 　 n=0时为空树 　 n0时为非空树： 　　(1)有且仅有一个特定的称为根(root)的结点; 　　(2)其余结点可分为m(m0)个互不相交的有限集{T1,T2,…,Tm},其中每个集合本身又是一棵子树． 　 由上可知：树的定义为递归定义． 　 如下图： A B C D G F E H I J K L M T1={B,E,F,K,L}; T2={C,G}; T3={D,H,I,J,M} …… 2.树的ADT定义: tree=(D,R,P) 其中，D具有相同特性数据元素集合 　　　 R具有以下几种情况： 　　　 (1)D为空集，R为空集 　　　 (2)D中一个元素(根:Root)，R为空集 　　　 (3)D中有两个以上元素时，R={H} 存在D-{Root}的划分:D1,D2,…,Dm．对于任意Di非空,则有:xi∈Di,有Root,xi,Di-{xi}关系记作Hi. 则H={Root,x1,H1,……,Root,xm,Hm} P:119页(自己阅读,理解即可) 3.树的表示形式 (1)树形表示法 (2)文 氏图表示法 (3)凹入表示法 (4)广义表形式 (括号嵌套表示法) (A(B(E(K,L),F),C(G),D(H(M),I,J))) F K L E A B G C I J M H D 4.基本术语 结点: 数据元素+分支 度: 结点的分支数目 终端结点/非终端结点:叶子/分支结点,内部结点 树的度: max{结点的度} 双亲/孩子/兄弟: 同一双亲 祖先/子孙: 层次/堂兄/深度: 森林: A B C D G F E H I J K L M 6.2 二叉树 1.二叉树的定义 ①二叉树是另一种树型结构,但不是树的特例. ②特点: (1)每个结点至多只有两棵子树.(结点的度?) (2)二叉树的子树有左右之分,不能颠倒 ③二叉树中结点的5种基本形态: 没有结点 度为0 度为1 度为2 ④ ADT定义 BinaryTree=(D,R,P) 其中，D具有相同特性数据元素集合 　　　R：(1)D为空集，R为空集,空二叉树 　　　 (2)D中一个元素(根:Root)，R为空集 　　　 (3)D中有两个以上元素时，R={H} 存在D-{Root}的划分:Dl,Dr．假设Dl非空,则有: xl∈Dl,有Root,xl,Dl-{xl}关系记作Hl;对于Dr亦可. 则 H={Root,xl,Hl,Root,xr,Hr} P:121页-123页(自己阅读,理解即可) 2.二叉树的性质 性质1:在二叉树的第i层至多有2i-1个结点 证明:(用归纳法证明) ①i=1时,只有根结点,21-1=20=1 ②假设第i-1层上有2(i-1)-1,命题成立. 由二叉树的特点知:每个结点至多有2棵子树,所以:第i层上的结点数是i-1层上结点数的2倍, 即第i层的结点数为:2* 2(i-1)-1=2i-1 命题成立 证明:由性质1得 第1层至多有结点个数:20 第2层至多有结点个数:21 … … 第k层至多有结点个数:2k-1 总结点数= 20+21+… …+ 2k-1= 等比序列 2k-1 性质2:深度为k的二叉树至多有2k-1个结点 证明:假设度为1的结点数为n1,总结点数为n, 分支数目为B,则 n=n0+n1+n2 ……….. ① n=B+1 ……………… ② B=n1+2*n2 ……