Chinaunix首页 | 论坛 | 博客
  • 博客访问: 497055
  • 博文数量: 74
  • 博客积分: 750
  • 博客等级: 军士长
  • 技术积分: 1453
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-29 15:59
文章分类
文章存档

2014年(30)

2013年(8)

2012年(36)

分类: C/C++

2014-06-20 10:35:05

在中,二叉树是每个节点最多有两个子树的。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现和。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1

树和二叉树的三个主要差别:

  1. 树的结点个数至少为1,而二叉树的结点个数可以为0;
  2. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;
  3. 树的结点无左、右之分,而二叉树的结点有左、右之分。

<完全二叉树和满二叉树>

  1. 满二叉树:一棵深度为k,且有2^k-1个节点称之为满二叉树
  2. 完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树
相关链接是:%E4%BA%8C%E5%8F%89%E6%A0%91
阅读(1607) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~