数据结构伸展树介绍及C语言的实现方法

概述本文章向大家介绍数据结构伸展树及C语言的实现方法，需要的朋友可以参考一下

阅读了skywang的伸展树的讲解，觉得讲的很不错，再次也推荐大家无论是新手还是老手都可以去阅读下。

-----------------------------------------------------------------------------------------

伸展树(一)之 图文解析 和 C语言的实现

概要

本章介绍伸展树。它和"二叉查找树"和"AVL树"一样，都是特殊的二叉树。在了解了"二叉查找树"和"AVL树"之后，学习伸展树是一件相当容易的事情。和以往一样，本文会先对伸展树的理论知识进行简单介绍，然后给出C语言的实现。后序再分别给出C++和Java版本的实现；这3种实现方式的原理都一样，选择其中之一进行了解即可。若文章有错误或不足的地方，希望您能不吝指出！

目录

1.伸展树的介绍

2.伸展树的C实现

3.伸展树的C测试程序

转载请注明出处：http://www.cnblogs.com/skywang12345/p/3604238.HTML

---------------------------------------------------------------------------------------------

特性要点：

1.如果寻找的key值小于tree->key值的话，则进行右旋:

1 Node N,*l,*r,*c;

2

3 N.left = N.right = NulL;

4 l = r = &N;

5 if(key < tree->key)

6 {

7 if(key< tree->left->key)

8 {

9 c = tree -> left;

10 tree->left = c->right;

11 c->right = tree;

12 tree = c;

13 }

14 r->left = tree; /* 02,link right */

15 r = tree;

16 tree = tree->left;

17 }

2.寻找的key值大于tree->key的话，则左旋，同理之；

3.如何简单的判断左旋还是右旋：

因为伸展树就是为了将寻找的key值对应的节点变为根节点，所以根据二叉树的特性：x节点包含关键字key，如果y是x的左子树的一个节点，则 key[y]<= key[x]。如果y是x的右子树的一个节点，则key[y] >= key[x]。那么如果key > tree->key ，则key就在tree的右子树的某个节点上，那么你就需要将右子树旋转直到根节点上。那么根据生活常识，你需要向左旋转才能将右子树旋转到根节点上。右旋同理之。

而所谓的左旋、右旋，则相当于；

左旋：将节点旋转为右孩子的左节点

右旋：将节点旋转为左孩子的右节点

总结

以上是内存溢出为你收集整理的数据结构伸展树介绍及C语言的实现方法全部内容，希望文章能够帮你解决数据结构伸展树介绍及C语言的实现方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。