第7章二叉树 二叉树的基本概念 >二叉树的基本运算 二叉树的存储结构 叉树的遍历 二叉树其它运算的实现 >穿线二叉树 >树、森林和二叉树的转换
第7章 二叉树 ➢二叉树的基本概念 ➢二叉树的存储结构 ➢二叉树的基本运算 ➢二叉树其它运算的实现 ➢穿线二叉树 ➢树、森林和二叉树的转换 ➢二叉树的遍历
71二叉树的基本概念 叉树的定义为:二叉树是一个由结点构成的有 限集合,这个集合或者为空,或者由一个根结点及 两棵互不相交的分别称作这个根的左子树和右子树 的二叉树组成。当二叉树的结点集合为空时,称为 空二叉树 e(f(g
7.1 二叉树的基本概念 二叉树的定义为：二叉树是一个由结点构成的有 限集合，这个集合或者为空，或者由一个根结点及 两棵互不相交的分别称作这个根的左子树和右子树 的二叉树组成。当二叉树的结点集合为空时，称为 空二叉树 。 a b d e c h f g
二叉树有以下五种基本形态 a)空二叉树(b)根和空的左、右子树(c)根和非空左子树、空右子树 (d)根和空左子树、非空右子树(e)根和非空的左、右子树
二叉树有以下五种基本形态： (a) 空二叉树 (b) 根和空的左、右子树 (c) 根和非空左子树、空右子树 (d) 根和空左子树、非空右子树 (e) 根和非空的左、右子树
树型结构中使用的术语如父母(双亲或前件) 子女(后件)、祖先、子孙、兄弟和路径等在二叉树 中仍然可以沿用,但值得注意的是,二叉树并非一般 树型结构的特殊形式,它们为两种不同的数据结构。 叉树与一般树型结构的主要区别在于 (1)二叉树中每个非空结点最多只有两个子女,而 一般的树型结构中每个非空结点可以有0到多 个子女; (2)二叉树中结点的子树要区分左子树和右子树, 即使在结点只有一棵子树的情况下也要明确指 出是左子树还是右子树
树型结构中使用的术语如父母（双亲或前件）、 子女（后件）、祖先、子孙、兄弟和路径等在二叉树 中仍然可以沿用，但值得注意的是，二叉树并非一般 树型结构的特殊形式，它们为两种不同的数据结构。 二叉树与一般树型结构的主要区别在于： （1）二叉树中每个非空结点最多只有两个子女，而 一般的树型结构中每个非空结点可以有0到多 个子女； （2）二叉树中结点的子树要区分左子树和右子树， 即使在结点只有一棵子树的情况下也要明确指 出是左子树还是右子树
二叉树具有以下重要性质 性质1一棵非空二叉树的第层上至多有2个结点 (1)。 证明:当i=时,只有根结点,此时21=20=1,显然 上述性质成立;又由于在二叉树中每个结点最多只 能具有两个子女,因而第层上结点的最大个数是第 i-1层上结点的最大个数的两倍。于是第2层上结点的 最大个数为2,第3层上结点的最大个数为4, 则第层上结点的最大个数即为21 性质2深度为的二叉树至多有2-个结点(h>1) 根据性质1,深度为h的二叉树最多具有的结点的个 数为20+2+2+.+2h1=2h1
二叉树具有以下重要性质： 性质1 一棵非空二叉树的第i层上至多有2 i-1个结点 （i≥1）。 证明：当i=1时，只有根结点，此时2 1-1=20=1，显然 上述性质成立；又由于在二叉树中每个结点最多只 能具有两个子女，因而第i层上结点的最大个数是第 i-1层上结点的最大个数的两倍。于是第2层上结点的 最大个数为2，第3层上结点的最大个数为4，……, 则第i层上结点的最大个数即为2 i-1 。 性质2 深度为h的二叉树至多有2 h -1个结点（h>1）。 根据性质1，深度为h的二叉树最多具有的结点的个 数为2 0+21+22+…+2h-1=2h -1