15-16树、二叉树性质及遍历.pptx

A示例只有根结点的树空树示例BCDAEGFHIJT2T1T3KLMA是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}； T2={C,G}；T3={D,H,I,J,M}；T1,T2,T3都是根A的子树，且本身也是一棵树。A树的递归定义数据集合D={e1, e2, e3, …,en}……S1,S2,…,Sm ? D，并且Si ∩ Sj = ?, D = S1 ∪ S2…∪ Sm 基础：空集是树。归纳：如果S1,S2…Sk-1,Sk+1,…Sm是树，则Sk={e},S1,S2…Sk-1,Sk+1,…Sm也是树,Sk叫做树根，Sk与Si的树根具有父子关系（层次关系）。树的表示方法ADBCHJGEFKLI树根树的表示方法ABET1KLFCT2GDHT3IJ树的表示方法JIM树的表示方法ABDEHFLK树的表示方法T2T3T1 A( )B(E, F(K, L)), C(G), D(H, I, J(M))MHDJI基本术语数据元素+若干指向子树的分支结点:结点的度:分支的个数树中所有结点的度的最大值树的度:MHDJI基本术语度为零的结点叶子结点:分支(非终端)结点:度大于零的结点A基本术语(从根到结点的)路径：由从根到该结点所经分支和结点构成路径长度：边的个数孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点MEBHGKCJLDFIBHGKEACJLDFIM基本术语结点的层次(级数):根到节点的路径长度+1树的深度（高度）：定义1、树中叶子结点所在的最大层次。定义2、最长路径的长度+1。1234MHDJI基本术语有向树：(１) 有确定的根；(２) 树根和子树之间为有向关系。C1CPPC3CC2C基本术语有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。森林：是 m（m≥0）棵互不相交的树的集合BGFD基本术语任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点，F 被称为子树森林MEKHACJLFIroot树型结构和线性结构特点的对比线性结构树型结构第一个数据元素无前驱根结点（无前驱）多个叶子结点(无后继)最后一个数据元素(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)二叉树的定义递归定义：基础：空树是二叉树归纳：由一个根结点和左子树和右子树构成，且左、右子树也是二叉树。GHKAE右子树二叉树的定义左子树CBFFDE根结点NNNN二叉树的五种形态3）?右子树为空2）?只含根结点1）空树LRRL4）左子树为空5）左右子树都不为空二叉树的特性二叉树具有以下五条重要性质： 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。(i≥1)层号1A二叉树的特性BC2GDEF34LNJMOHKI二叉树的特性用归纳法证明i = 1 时，只有一个根结点，满足 2i-1 = 20 = 1；归纳基础：假设第i-1层上至多有2i-2个结点;归纳假设：归纳：二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 × 2 = 2i-1 。二叉树的特性性质 2 ： 深度为 k 的二叉树上至多含 2k - 1 个结点（k≥1）二叉树的特性证明：第1层: ≤20第2层: ≤21……第k层: ≤2k-1≤ 20+21+ ? ? ? ? ? ? +2k-1 = 2k-1 二叉树的特性性质 3 ： 对任何一棵二叉树，若它含有n0个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0= n2 + 11二叉树的特性23证明：4567设 二叉树上结点总数 n = n0 + n1 + n2 公式(1)89101二叉树的特性23设二叉树上分支总数(边数)为b ，由树的性质： n =b+1因为度为1的点引出一条边度为2的点引出2条边 所以：b=n1 + 2n2所以：n=n1 + 2n2 + 1 公式(2)二叉树的特性由式1和2得到： n0+ n1 + n2= n1 + 2n2 + 1整理后 n0= n2 + 11二叉树的特性23两类特殊的二叉树：45671）满二叉树：指的是深度为k且含有2k - 1个结点的二叉树。891011121314151二叉树的特性232）完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应bcdefghij二叉树的特性性质 4 ：具有 n 个结点的完全二叉树的深度为 ? log2 n? +1?x? c++中的函数floor(x)?x? c++中的函数ceiling(x)floor(3.1)