平衡二叉树的高度怎么算,平衡二叉树求高度
二叉树 的 常用公式 谁能和新手 说说啊！
(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
(2) 深度为h的二叉树最多有2^h-1个结点(h=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为int（log2n）+1；
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I1，则其父结点的编号为I/2；
如果2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；
如果2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
扩展资料：
类型
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）左、右子树也分别为二叉排序树。
若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度：结点拥有的子树的数目。
叶子结点：度为0的结点。
分支结点：度不为0的结点。
树的度：树中结点的最大的度。
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的高度：树中结点的最大层次。
森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。
参考资料：百度百科---二叉树
这个树是不是平衡二叉树，如果不是，请说明为什么？怎么算？
首先，对于不同的平衡定义有不同的平衡二叉树
1. 如果定义”平衡“为：左右子树的高度差的绝对值不超过1，也就是说|h(tree.left)-h(tree.right)|=1。那么称这样的平衡二叉树为AVL数
2.若定义”平衡“为：较深的子树的高度不超过另一个子树的两倍，如H(tree.left)=2*H(tree.right)，其中左子树较深。那么称这样的平衡二叉树为红黑树（RB-Tree）
3.当然，还有很多其他的平衡二叉树
另外：这个平衡的定义是递归的，也就是说：左子树和右子树也必须是一个平衡二叉树。
对二叉树进行平衡的目的是使得整个二叉树的高度降下来，那么我们对二叉树进行遍历或者查找的时间复杂度就能降下来，因为这个时间复杂度和二叉树的高度是正相关的。通常我们所说的平衡二叉树指的是AVL树。
因此图中的二叉树既是AVL平衡二叉树，也是一个红黑树。可以通过定义验证。
平衡二叉树的具体算法
平衡二叉搜索树双称为AVL树，它也是一棵二叉搜索树，是对二叉搜索树的一种改进，或都是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
平衡因子（Balance Factor,BF）定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的了。
使用二叉排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子s树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
对于平衡二叉搜索树，保持树的平衡的基本机制就是旋转。旋转是对树的元素顺序进行调节。旋转的目的是消除由于临时插入和删除对树的平衡产生的影响。
对于平衡二叉树的遍历，搜索，等都有不同的算法，你要具体实在无法确定，都说一遍那就是一本书了，呵呵！！
n个节点的平衡二叉树,最大高度和最小高度是多少
高度为log2(n+1)，seethepic
数据结构课本上有最大高度。
最小高度就是完全二叉树了。
设N是深度为h的平衡二叉树的最少结点数，对于 h = 1，有 N = F(h + 2) - 1 成立，其中的F(n)为Fibonacci 数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
于是最大高度H为F(H + 2) - 1 = n F(H + 3) - 1
扩展资料：
若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i1时，该节点的双亲节点的编号为i/2。
若2i≤n，则有编号为2的左叶子，否则没有左叶子。
若2+1≤n，则有编号为2i+1的右叶子，否则没有右叶子。
参考资料来源：百度百科-二叉树
平衡二叉树叶子结点的最大高度差是多少？
平衡树的定义是这样的，任意节点的子树的高度差都小于等于1，二叉树是指的树的每个节点的指数个数小于等于2。所以，从定义可以知道，平衡二叉树叶子节点的最大高度差就是1。
二叉树的深度怎么算
二叉树的深度计算，首先要判断节点，以下是计算二叉树的详细步骤：
1、一颗树只有一个节点，它的深度是1；
2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；
3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；
4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。
一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。
具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子节点，至多有2k-1个节点。
扩展资料
二叉树深度的性质：
1、在非空二叉树中，第i层的结点总数不超过, i=1；
2、深度为h的二叉树最多有个结点(h=1)，最少有h个结点；
3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
4、具有n个结点的完全二叉树的深度为
5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I1，则其父结点的编号为I/2；
如果2*I=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*IN，则无左孩子；
参考资料：百度百科—二叉树