6.2二叉树 ●二叉树在树结构的应用中起着非常重要的作用,因为对二叉 树的许多操作算法简单,而任何树都可以与二叉树相互转 换,这样就解决了树的存储结构及其运算中存在的复杂性。 定义:二叉树是由n(n>=0)个结点的有限集合构成,此集合 或者为空集,或者由一个根结点及两棵互不相交的左右子树 组成,并且左右子树都是二叉树 ●这也是一个递归定义。二叉树可以是空集合,根可以有空的 左子树或空的右子树。二叉树不是树的特殊情况,它们是两 个概念。 北京邮电大学自动化学院北京邮电大学自动化学院 6 6.2 二叉树 ⚫ 二叉树在树结构的应用中起着非常重要的作用，因为对二叉 树的许多操作算法简单，而任何树都可以与二叉树相互转 换，这样就解决了树的存储结构及其运算中存在的复杂性。 ⚫ 定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合 或者为空集，或者由一个根结点及两棵互不相交的左右子树 组成，并且左右子树都是二叉树。 ⚫ 这也是一个递归定义。二叉树可以是空集合，根可以有空的 左子树或空的右子树。二叉树不是树的特殊情况，它们是两 个概念