注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天马行空

宠辱不惊,闲看庭前花开花落;去留无意,漫观天外云展云舒……

 
 
 

日志

 
 
 
 

关于树的一些概念  

2012-02-09 12:07:10|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

树状图是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个结点有零个或多个子结点;
  • 每一个子结点只有一个父结点;
  • 没有前驱的结点为根结点;
  • 除了根结点外,每个子结点可以分为m个不相交的子树;
关于树的一些概念 - 547502462 - 天马行空
 
 

术语

  1. 节点的度:一个节点含有的子树的个数称为该节点的度;
  2. 叶节点终端节点:度为零的节点称为叶节点;
  3. 非终端节点分支节点:度不为零的节点;
  4. 双亲节点父节点:若一个结点含有子节点,则这个节点称为其子节点的父节点;
  5. 孩子节点子节点:一个节点含有的子树的根节点称为该节点的子节点;
  6. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
  7. 树的度:一棵树中,最大的节点的度称为树的度;
  8. 节点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
  9. 树的高度深度:树中节点的最大层次;
  10. 堂兄弟节点:双亲在同一层的节点互为堂兄弟;
  11. 节点的祖先:从根到该节点所经分支上的所有节点;
  12. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  13. 森林:由m(m>=0)棵互不相交的树的集合称为森林;

树的种类

  • 无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;

二叉树
http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
满二叉树
http://baike.baidu.com/view/427110.htm 
霍夫曼树
http://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A0%91
完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。 
特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1   满二叉树:一棵深度为k,且有2的(k)次方-1个节点的二叉树  特点:每一层上的结点数都是最大结点数  满二叉树肯定是完全二叉树 完全二叉树不一定是满二叉树 
树、森林与二叉树的转换
 
http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.5.1.htm

  评论这张
 
阅读(234)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018