0
回答
数据结构之Tree

     数据结构和数据的关系,就如同水和盛水的器皿一样, 比如: 消防员会选择用消防水栓装水,原因是他需要处理高压大量的水,解救火灾;茶馆的伙计会用茶壶, 茶壶受热均匀,煮出的茶才韵味无穷;家庭用的话,就用饮水机或者开水壶。 这些容器就是数据结构。容器提供了使用数据(查询,遍历,打印)的接口,就像消防栓,提供的接口是高压皮套,解开水就喷涌而出,茶壶是涓涓溪流,饮水机的冷热开关...

 

    Tree也是一种数据结构, 有别于线性结构,Tree表明的是一种非线性的层次关系(想想哪里会用这样的数据结构,家谱,公司人事结构等,  HTML,XML结构....应用的范围实在太广了).

 

全局来看:

组成: 根节点 + 方法

即:知道根节点,然后提供方法, 就能将这棵树的信息全部搞定, 从根节点开始,
攀爬到你需要的任何叶子或者枝干上去。

所以,如果你想写一颗树, 则应该这样:

Tree的类,

1. 这个类有一个Field,叫root, 类型为Node类型; 根节点下面会延伸出其他节点,也为Node
2. 这个类有无数的访问方法,大体是顺着节点去摸索其他的节点,让你方便的找到树中,你需要的任意信息

.

OK, 就这些!够简单!

然后再深入一点点:提到的类型Node,还没有定义,怎样定义一个节点?

定义一个Node主要有以下:

1. 她自己所描述的数据.
2. 她的子孙Node.
3. 它的方法,得到子孙Node,得到数据.

Over!

整个树从用途到实现,也就讲完了, 此时,我们遗留了问题,怎么去查找树中的信息? 上面提到查找信息的方法,是通过树的方法来实现,但这里并没有说到具体的方法?

 

为了处理不同的应用,Tree的数据结构还可以细分:衍生出大量的Tree, 最常见的是二叉树。二叉树,再继续细分为红黑树,平衡二叉树,等等。

 

二叉树用到最多,来看看它的集中形式:

二叉平衡树: 左右子树的深度相差不超过1.

二叉查找树:左节点小于父节点,有节点大于等于父节点(或者相反)

二叉平衡查找树:查找树,同时是平衡的(这样组织数据的话, 在搜索树的时候,可以二分的方式进行,另外可以保证不会出现左右子树深度不一, 查询次数不均衡)。

AVL树: 是一种二叉查找树,每个节点记录平衡因子, 通过旋转的方式,能达到平衡。


红黑树,也是一个二叉查找树, 是一种让查找树达到平衡的算法结构,牵涉到树旋转。

 

AVL和红黑树这样的结构,能方便判断一颗二叉树,是否是平衡查找树。 

 


原文链接:http://blog.csdn.net/ostrichmyself/article/details/4724974
<无标签>
举报
晨曦之光
发帖于7年前 0回/165阅
顶部