数据结构学习笔记_树

野性酷女 2021-12-16 23:49 278阅读 0赞

### **一、查找二叉树** ###

**1.查找二叉树的性质**

![1572587-20190624090132506-2118870707.png][]

**2.contains 方法**

如果树T中含有节点X,那么返回true,如果节点不存在返回false(并且在左子树或右子树进行递归调用);

**3.findMin和findMax方法**

finMin是从根节点向左儿子进行,递归调用,终点就是最小的元素;

findMax是从根节点向右儿子进行,递归调用,终点就是最大的元素;

**3.insert方法**

![1572587-20190624090825923-370263772.png][]

比如,要将5插入到上面的左树中,只需要找到4, 继续向右进行,但右边不存在子树,所5的插入位置就是在这里

**4.查找二叉树的remove(最困难)**

1.节点是一篇树叶(没有儿子),立即被删除;

2.节点只有一个儿子,父节点绕过该儿子节点后被删除,例如下面左图;

3.节点有两个儿子,一般的删除策略是用其右子树的最小数据代替该节点的数据(下面由图,从右子树5里面找最小数3来代替2),并递归地删除那个节点(例如交换后的节点2).因为右子树的最小节点不可能有左儿子;

![1572587-20190624103715799-1782509597.png][]

删除程序如下:

![1572587-20190624104937460-1358599084.png][]

**5.平均深度**

一个树的所有节点的深度和称为 内部路径长,

![1572587-20190624163204783-2142421267.png][]

### **二、AVL树** ###

**1.性质 **

带有平衡条件的查找二叉树.  一个AVL树,每个节点的左子树和右子树最多相差1(空树的节点为-1).

![1572587-20190624172030441-387624124.png][]

** 2.单旋转**

** 3.双旋转**

转载于:https://www.cnblogs.com/coloz/p/11062472.html

[1572587-20190624090132506-2118870707.png]: /images/20211214/4048d3706d574ee29d55fb0fb53a576b.png
[1572587-20190624090825923-370263772.png]: /images/20211214/5293706f8030433c867ffaa9f0a7c91f.png
[1572587-20190624103715799-1782509597.png]: /images/20211214/86c264f0992746628f5d035f7cc93465.png
[1572587-20190624104937460-1358599084.png]: /images/20211214/9935517b058c435dad546e4c71601e05.png
[1572587-20190624163204783-2142421267.png]: /images/20211214/f7227840db4647139cee7ad0c752a64c.png
[1572587-20190624172030441-387624124.png]: /images/20211214/2b03fb0cf8af42389b231a12bc565d5f.png