最近看了篇文章,里面有个二叉树的数据结构,想具体了解一下这个方面的内容,包括二叉树结构的优点,如何设计等等都可以。欢迎讨论,2周结贴
解决方案 »
- 怎么样让文件保存的时候可以保存多种类型?
- vb程序中如何为后台的access数据库设置密码
- 用WebBrowser如何在WebBrowser中打开链接而不是在IE中打开
- 关于visual studio 6.0字装盘的问题?
- 请问VB中引用和部件有什么区别?
- 急急急,问在MDI窗体中想把一个MDI子窗体设置为永远最大化且在最后层(也就是最底层),调用其它的子窗体均最上面,其它MDI子窗体可切换
- 简单问题:如何让程序强制终止自己
- 资源文件的问题?(急用!!)
- 利用自己的专业特长
- 关于VB引用其他语言写的DLL文件
- 请教如何让窗体可以有上下左右的滚动条?在线等待.......
- 如何捕捉MSHFlexGrid控件改变列宽度时的消息??MouseDown()事件好象没有用啊?~~~各位帮帮忙!
http://www.vbzx.net/ArticleView/vbzx_Article_View_665.asp
它是结点的有限集合,这个集合或者为空集
或者由一个根及两棵不相交的分别称作这个根
的“左子树”和“右子树”的二叉树组成。
它的每一个结点至多有两棵子树,并且子树
有左右之分,不能随意颠倒。二叉树不是树的特殊情形,它们是两个概念。
树和二叉树之间最主要的差别是:二叉树中结点的子树要区分为左子树和右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 满二叉树:如果一棵二叉树的任何结点或者是树叶,或者有两棵非空子树,则此二叉树称作“满二叉树”。
完全二叉树:如果一棵二叉树至多只有最下面的两层结点度数可以小于2,并且最下面一层的结点都集中在该层最左边的若干位置上,则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。
扩充二叉树 :
把原二叉树的结点都变为度数为2的分支结点,也就是说,如果原结点的度数为2,则不变,度数为1,则增加一个分支,度数为0(树叶)增加两个分支。
在扩充的二叉树里,新增加的外部结点的个数比原来的内部结点个数多1。
“外部路径长度”E:在扩充的二叉树里从根到每个外部结点的路径长度之和。
“内部路径长度”I:在扩充的二叉树里从根到每个内部结点的路径长度之和。
E = I + 2n
其中,n是内部结点的个数。
二叉树的性质性质1. 在非空二叉树的第i层上至多有2i个结点
归纳: i=0, 结点数=1=20 .
假设对于j(0j i), 结点数至多有2j .
对于i=j+1, 结点数至多为 2* 2j=2j+1 .性质2. 深度为k的二叉树至多有2k+1-1个结点
性质3. 对任何一棵非空二叉树T,如果叶结点数 为n0,
度为2的结点数为n2,则n0=n2+1。
性质4. 具有n个结点的完全二叉树的深度k为log2n .
二叉树的基本运算
创建一棵空二叉树;
判断某棵二叉树是否为空;
求二叉树的根结点,若为空,则返回一特殊值;
求二叉树中某个指定结点的父结点,当指定结点为根时,返回一特殊值;
求二叉树中某个指定结点的左子女结点,当指定结点没有左子女时,返回一特殊值;
求二叉树中某个指定结点的右子女结点,当指定结点没有右子女时,返回一特殊值;
二叉树的周游。
二叉树的周游(Traversing Binary Tree):
按某条搜索路径访问二叉树中的所有结点 ,使得每个结点被访问一次且仅被访问一次。三种方式:
先根次序 (DLR)
对称序 (LDR)
后根次序 (LRD)
一。递归算法
先根次序
中根次序
后根次序
二。 非递归算法 (用自定义的栈来代替系统的栈)
先根次序
中根次序
后根次序 1 2