当前位置:鱼C工作室 >数据结构和算法 > 查看文章

二叉树 – 数据结构和算法43

二叉树

 

让编程改变世界

Change the world by program


 

二叉树的定义

 

世上树有万千种,唯有二叉课上讲。这里的二叉是二叉树,因为二叉树使用的范围最广,最具有代表意义,因此我们重点讨论二叉树。

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

 

这个定义显然是递归形式的,所以咱看上去有点晕,因为自古有“神使用递归,人使用迭代!”

 

二叉树的特点

 

每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。(注意:不是都需要两棵子树,而是最多可以是两棵,没有子树或者有一棵子树也都是可以的。)

左子树和右子树是有顺序的,次序不能颠倒。

 

即使树中某结点只有一棵子树,也要区分它是左子树还是右子树,下面是完全不同的二叉树:

 

二叉树的五种基本形态

 

  1. 空二叉树
  2. 只有一个根结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

 

 

分页阅读: 1 2 3 下一页
为您推荐

报歉!评论已关闭.