开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2021.04.20
今天给大家带来的是数据结构中的树，包括是二叉树、完全/满/平衡二叉树，大家可以看下目录：
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。树型结构也是信息的重要组织形式之一，一切具有层次关系的问题都可用树来描述。
树的表示方法有许多，常用的方法是用括号：
如上图可使用括号表示法写成：(A(B(E,F),C(G),D(H,M)))
二叉树（BinaryTree）是包含n个节点的有限集合，当n为零时该集合为空集，或者该集合由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
对于深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2^k1，则它就是满二叉树。
满二叉树一定是平衡二叉树，平衡二叉树不一定是满二叉树；
平衡二叉树（又称平衡二叉查找树），由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
最小二叉平衡树的节点的公式为F(n)=F(n-1)F(n-2)1，这个类似于一个递归的数列，可参考Fibonacci数列，公式解释为：
平衡二叉树调整后，它的中序遍历的顺序是不会改变的。
所有的不平衡情况中，都是按照寻找最小不平衡树=>寻找所属的不平衡类别=>根据4种类别进行固定化程序的操作；
首先找到最小不平衡的子树，再以其根节点向右旋转（向右旋转后相当于右面的子数的树高加1，而左面的子数的树高减1）；旋转之后源根节点的左孩子作为新的根节点，原来根节点的左孩子作为新的根节点；中序遍历对比：调整前：123；调整后：123；LL型调整LL型调整
以下初始场景只会在删除时才会出现，删除后可按照LL型的调整策略进行调整；
以下初始场景只会在删除时才会出现，删除后可按照RR型的调整策略进行调整；