【数据结构之二叉树】

本文主要介绍常见的树结构，以助于我们学习后面的集合框架。

一、二叉树

节点内部结构

常见概念

特点：存储数据无规则，查找比较麻烦

二、二叉查找树

为什么二叉查找树会呈现出这样的规律？

这取决于它添加节点的方式，查找节点也是通过比较的方式进行查找

特点：查找效率高，添加元素遵守的规则可能导致左右子树的高度差很大导致查询效率降低

三、二叉树的遍历方式

1、前序遍历（根左右）

2、中序遍历（左根右）

3、后序遍历（左右根）

4、层序遍历

四、二叉平衡树

为了解决二叉搜索树的树左右高度差很大的弊端

定义：任意节点左右子树高度差不超过1

五、演变

二叉树 -> 二叉搜索树 -> 平衡二叉树

六、平衡二叉树的旋转机制

为什么平衡二叉树能保证左右子树的高度差不超过1？是按照以下规则和时机的。

1、左旋

旋转前：被添加的节点为12

旋转后：被添加的节点为12

特殊情况（支点为根节点）

旋转前：被添加的节点为12

旋转后：被添加的节点为12

2、右旋

旋转前：被添加的节点为1

旋转后：被添加的节点为1

特殊情况（支点为根节点）

旋转前：被添加的节点为1

旋转后：被添加的节点为1

备注：还有左左、左右、右右、右左这四种方式。