什么是二叉树

本篇内容介绍了"什么是二叉树 "的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

什么是二叉树：

二叉树有两个节点 分别是左子节点和右子节点

二叉树中叶子节点全在最底层，除了叶子节点外每个节点都有左右两个子节点，这种二叉树叫做满二叉树。

叶子节点在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

=======================================================

如何存储（表示）一颗二叉树？
1 链式存储法： 每个节点有三个字段，其中一个节点存储数据，另外两个指向左右子节点的指针。

2 基于数组的顺序存储法：根节点存储在下标为i=1的位置，左子节点存储在下标2*i=2的位置，右子节点存储在2*i+1=2*2+1=5的位置。 所以节点x存储在数组中下标为i的位置，下标2*i的位置存储的就是左子节点，下标2*i+1的位置存储的就是右子节点。

所以如果该二叉树是一颗完全二叉树，那么用数组来存储是最节省内存的一种方式，因为数组的存储方式并不像链式存储那样需要存储额外的左右子节点的指针，这也是为什么完全二叉树辉单独列出来的原因。

二叉树的遍历包括 前序遍历 中序遍历和后序遍历。二叉树的遍历其实是一个递归的过程。遍历的时间复杂度为O（n）。

==========================================================

二叉查找树：二叉查找树就是为了实现快速查找而生的，不仅可以快速查找一个数据，还支持快速插入、删除一个数据。

二叉树的查找操作： 我们先取根节点，如果它等于我们要查找的数据，那就返回，如果查找的数据比根节点的值小，那么在左子树中递归查找。如果要查找的数据比根节点的值大，那么就在右子树中递归查找。

二叉树的插入操作： 如果要插入的数据比节点数据大，并且节点的右子树为空，就将新数据直接插入右子节点的位置，如果不为空，就再遍历递归右子树，查找插入位置。同理，要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子树的位置，如果不为空，就遍历左子树找到插入的位置。

二叉树的删除操作： 有三种情况 1 如果要删除的节点没有子节点，只需要将父节点中指向要删除的节点的指针设置为null。 2 如果要删除的节点只有一个子节点，只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。 3 如果要删除的节点有两个子节点，我们需要找到这个节点的右子树的最小节点，把它替换到要删除的节点，然后再删除掉这个最小节点，因为最小节点肯定没有左子节点。

时间复杂度： 不管是插入、删除还是查找，时间复杂度都是跟树的高度成正比，也就是O（height） 这样问题就转换成了如何求一颗包含n个节点的完全二叉树的高度。树的高度为最大层数减一，为了方便计算，转换为层来表示。在完全二叉树中，第一层有1个节点，第二层有2个节点，第三层有4个节点。 下面一层节点个数是上一次的二倍，第k层包含节点个数是2^(k-1)个。最后一层节点个数在1到2^(L-1)个之间。平衡二叉树的高度接近logn，所以插入 删除 查找操作的时间复杂度也比较稳定，是O（logn）。

===========================================================

红黑树

平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于1。完全二叉树，满二叉树都是平衡二叉树。

平衡二叉树中平衡的意思就是让整棵树看起来比较对称，比较平衡，不要出现左子树很高，右子树很矮的情况。这样就可以让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作效率更高些。

红黑树定义：1 根节点是黑色的

2 每个叶子节点都是黑色的空节点，，也就是说叶子节点不存储数据

3 任何相邻的节点都不能同时为红色，红色节点是被黑色节点分开的。

4 每个节点从该节点到达其叶子节点的所有路径，都包含相同数目的黑色节点。

工程中为什么都喜欢用红黑树？

堆和栈在绝大多数情况下，操作的效率很高，但也无法避免极端情况下时间复杂度的退化，尽管概率不大，ALV树是一种高度的平衡二叉树，查找效率非常高，但是有利有弊，ALV树为了维持这种高度的平衡，就要付出很大的代价，每次的插入、删除都要做调整，会比较复杂，耗时，所以堆有频繁的插入、删除等操作的数据集合，使用ALV树的代价就比较高了。而红黑树只是做到了近似平衡而非真正的平衡，所以在维护成本上就i比ALV树要低一些。所以红黑树的插入、删除、查找等操作都比较稳定，在工程中需要面对各种情况，所以更倾向于这种稳定性能的二叉查找树。

"什么是二叉树 "的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！