第六章 树与二叉树－树的基本概念.pptVIP

第六章 树与二叉树 －树的基本概念 任课教师：代丽( dlzist@163.com) 本小节主要内容 6.1 树的基本概念和术语 6.1.1 树的定义----非线性结构、层次结构 树（tree）是由一个或多个结点组成的有限集合T。 其中: (1) 有一个特定的结点称为该树的根（root）结点; (2) 除根结点之外的其余结点可分为m（m≥0）个互不相交的有限集合T1, T2, …, Tm, 且其中每一个集合本身又是一棵树, 称之为根的子树（subtree）。  这是一个递归的定义。它反应了树的固有特性。可以认为仅有一个根结点的树是最小树, 树中结点较多时, 每个结点都是某一棵子树的根。 6.1.2 树的常用术语 树结构常常用到一些术语, 如度、 双亲、 孩子、 树深等。 结点的度是结点的子树的个数。 树的度是树中结点度的最大值。 度为零的结点称为叶子或终结点。 度不为零的结点称为非终端结点。 某结点的各子树的根结点称为该结点的孩子, 而该结点又称为孩子们的双亲结点。 具有相同双亲的结点互称为兄弟。 6.1.2 树的常用术语 一棵树上除根结点以外的其它结点称为根结点的子孙。 对于树中某结点, 从根结点开始到该结点的双亲是该结点的祖先。 结点的层次值从根算起, 根的层次值为１, 其余结点的层次值为双亲结点层次值加１。 一棵树的深度是该树中结点最大层次值。 树结构的不同表示法 6.2 二叉树 6.2.1 二叉树的定义 二叉树（binary tree）是n（n=0）个结点的有限集合。 它或为空树（n=0）, 或为非空树; 对于非空树有:  (1) 有一个特定的称之为根的结点。  (2) 除根结点以外的其余结点分为两个互不相交的称之为左子树和右子树的二叉树构成。 这个定义是递归的。由于左、 右子树也是二叉树, 因此子树也可为空树。 图6.3中展现了五种基本形态不同的二叉树。 图6.3：二叉树的五种基本形态 6.2.2 二叉树的重要性质 性质1：二叉树第i(i≥1)层上至多有2i-1个结点。  证明：根据图可知, 根结点在第一层上, 这层结点数最多为1个, 即20个; 显然第二层上最多有2个结点, 即21个; … 假设第i-1层的结点最多有2i-2个, 且每个结点最多有两个孩子, 那么第i层上结点最多有 2*2i-2= 2i-1个。  6.2.2 二叉树的重要性质 性质2：深度为k(k≥1)的二叉树至多有2k-1个结点。  证明：由性质1可知各层结点最多数目之和为 20+21+22+…+2k-1; 6.2.2 二叉树的重要性质 性质3：在任意二叉树中, 若叶子结点（即度为零的结点）个数为n0, 度为1的结点个数为n1, 度为2的结点个数为n2, 那么 n0 = n2+1。 证明： 　 设n代表二叉树结点总数, 那么 n = n0 + n1 + n2 (6.1)　　　　 　　由于有n个结点的二叉树总边数为n-1条, 于是得  n-1=0*n0 +1*n1+2*n2 (6.2)  　 将式(6.1)代入式(6.2)得 n0= n2+1 两种特殊形态的二叉树 有两种特殊形态的二叉树, 它们是满二叉树和完全二叉树。 深度为k并且含有2k-1个结点的二叉树称为满二叉树, 这种树的特点是每层上的结点数都是最大结点数。 对满二叉树的结点可以从根结点开始自上向下, 自左至右顺序编号。 深度为k, 含有n个结点的二叉树, 当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时, 则称此二叉树为完全二叉树。 完全二叉树的特点是： （1)所有的叶结点都出现在第k层或k－1层。 （2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。 图6.4: 满二叉树和完全二叉树 6.2.2 二叉树的重要性质 性质4：具有n个结点的完全二叉树的树深为 ［log2n］+1（其中［x］表示不大于x的最大整数） 证明： ……..…. 6.2.2 二叉树的重要性质 性质5：若对有n个结点的完全二叉树进行顺序编号(1≤i≤n), 那么对于编号为i(i≥1)的结点: 当i=1时, 该结点为根, 它无双亲结点;  当i1时, 该结点的双亲结点编号为［i/2］;  若2i≤n, 则有编号为2i的左孩子, 否则没有左孩子 若2i+1≤n, 则有编号为2i+1的右孩子, 否则没有右孩子。 如图所示为完全二叉树上结点及其左右好在结点之间的关系。 性质5证明