二叉树——初识

本文主要是介绍二叉树——初识，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链表 ——> 二叉树 ——> 二叉查找树 ——> 平衡二叉树

二叉树时间复杂度：O(logn) ，即2^x(树的深度)=N

如：21亿点需要查找几次：2^32 = 21亿，查找32次。

1、满二叉树

2、完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。（除最后一层外，为一颗满二叉树）

3、二叉排序树（二叉查找树）的定义：

某结点左子树的所有结点的值都小于该节点的值且该结点右子树的值都大于该节点的值

4、平衡二叉树是特殊的二叉排序树

改进版：平衡二叉树 AVL 为了尽量降低树的高度，平均查找长度越小，查找速度越快

平衡因子 = 左子树的高度 - 右子树的高度

平衡二叉树的条件：

１、是二叉排序树

２、满足每个结点的平衡因子绝对值不大于１

平衡二叉树的平衡调整：

左旋如下：

S结点上提，E结点下降，伴随指针向左滑动

右旋示例：

5、红黑树：寻找相对平衡的二叉树

1.每个结点要么是红的要么是黑的。

2.根结点是黑的。

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

4.如果一个结点是红的，那么它的两个儿子都是黑的。

5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

红黑树变换：

1、改变颜色：红变黑、黑变黑

2、左旋、右旋

这篇关于二叉树——初识的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程