完整二叉树，完整二叉树，二叉搜索树，平衡二叉树

为什么每种树都需要“存在是合理的”，所以本文不再赘述每种树的性质，让我们集中讨论它.

二叉树（Binary Tree）主要包括: 完整的二叉树，完整的二叉树平衡二叉排序树，二叉搜索树，平衡二叉树

属性太多，定义太复杂. 只是了解那棵树.

1，完整的二叉树

2. 完整的二叉树

完整的二叉树是从完整的二叉树转换而来的，也就是说，完整的二叉树从最后一个节点删除，从后到前一个接一个地删除，其余的就是完整的二叉树.

3. 二进制搜索树

二叉搜索树（也称为二叉搜索树），它是具有以下属性的二叉树:

如果左子树不为空，则左子树上所有节点的值小于其根节点的值;

如果右子树不为空，则右子树上所有节点的值都大于或等于其根节点的值;

左右子树也是二叉搜索树.

简而言之: 在二叉搜索树中，左子树小于其根节点，右子树大于其根节点，这是递归定义的.

要点了！二叉搜索树的中序遍历必须按从小到大的顺序进行.

例如平衡二叉排序树，上图中的中间序列遍历结果: 1、3、4、6、7、8、10、13、14

二进制搜索树的搜索性能:

在最佳情况下，二叉搜索树的搜索效率较高，为O（logn），其访问性能类似于二分法；

但在最坏的情况下，它将为O（n）. 例如，插入的元素是有序的. 生成的二进制搜索树是一个链表，树的一条腿变得很长. 仅（请参见下图b）.

如果我们可以保证二进制搜索树不会在上述极端情况下出现（插入的元素是有序的，则导致链接列表），我们可以保证较高的搜索效率.

但这在插入有序元素时不是很容易控制. 根据二叉排序树的定义，我们无法判断当前树是否需要调整.

因此，将使用平衡二叉树（AVL）.

4. 平衡二叉树

提出平衡二叉树以确保该树不具有二叉搜索树的极端单腿现象，并尝试确保两腿平衡. 因此其定义如下:

定义: 平衡二叉树要么是空树，要么左右子树的高度差不大于1，并且子树还必须是平衡二叉树.

平衡二叉树的性能:

平衡的二叉树需要复杂的旋转来添加和删除，以维持整个树的平衡. 最后，插入和搜索的时间复杂度均为O（logn），并且性能已经相当不错.

著名的红黑树是平衡的二叉树！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-187189-1.html