MyException - 我的异常网
当前位置:我的异常网» 综合 » 二叉树的几种门类

二叉树的几种门类

www.MyException.Cn  网友分享于:2013-08-29  浏览:0次
二叉树的几种类型

本文基于邓俊辉编著的《数据结构(C++语言版)(第3版)》和网上博文,仅介绍完全二叉树、满二叉树,平衡二叉树的相关概念。

 

一、二叉树

1、二叉树的概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree),其次序不能任意颠倒。(百度百科

2、性质

(1)若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0);

(2)高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1);

(3)对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

二、几种特殊的二叉树

1、满二叉树

所有叶结点同处于最底层(非底层结点均是内部结点),一个深度为k(>=-1)且有2^(k+1) - 1个结点。如图(图来源于veil的博客):

 

2、完全二叉树

叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧。规模为n的完全二叉树,高度为

 

3、平衡二叉树

 平衡二叉树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树AVL替罪羊树Treap伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci(斐波那契)数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。(百度百科)

对于平衡二叉树要特别注意的是,不要求非叶节点都有两个子结点,仅要求两个子树的高度差的绝对值不超过1,或者为空树。

三、存储方式

存储的方式和图一样,有链表和数组两种,用数组存访问速度快,但插入、删除节点操作就比较费时了。实际中更多的是用链来表示二叉树的。

 

Ref:

http://www.cnblogs.com/idorax/p/6441043.html#top

http://blog.csdn.net/ysu108/article/details/7687728

文章评论

鲜为人知的编程真相
鲜为人知的编程真相
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
每天工作4小时的程序员
每天工作4小时的程序员
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员的鄙视链
程序员的鄙视链
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
代码女神横空出世
代码女神横空出世
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
那些争议最大的编程观点
那些争议最大的编程观点
我的丈夫是个程序员
我的丈夫是个程序员
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
一个程序员的时间管理
一个程序员的时间管理
如何成为一名黑客
如何成为一名黑客
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员都该阅读的书
程序员都该阅读的书
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
漫画:程序员的工作
漫画:程序员的工作
中美印日四国程序员比较
中美印日四国程序员比较
 程序员的样子
程序员的样子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
我是如何打败拖延症的
我是如何打败拖延症的
程序员应该关注的一些事儿
程序员应该关注的一些事儿
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
编程语言是女人
编程语言是女人
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
10个调试和排错的小建议
10个调试和排错的小建议
为什么程序员都是夜猫子
为什么程序员都是夜猫子
老程序员的下场
老程序员的下场
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有