二叉树

二叉树的特点总结

非空二叉树的特点：

1、每一层的结点个数: 最多是 （i>=1） 

2、高度是h的二叉树总结点个数：最多 

3、设度为0的结点个数是n0，度为2的结点个数是n2，则有 n0 = n2 + 1

n = n0 + n1 + n2

边数 = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1

n1 + 2*n2 = n0 + n1 + n2 -1

n0 = n2 + 1

1、真二叉树

定义：所有结点的度都是0或2的二叉树

2、满二叉树

定义：满足所有叶子结点都在最后一层的真二叉树叫满二叉树

性质：

a.同样高度的二叉树中，满二叉树的叶子结点数最多，总结点数也是最多的

b.满二叉树一定是真二叉树，真二叉树不一定是慢二叉树

c.高度为h(>=1)的满二叉树的第i层节点数是 2的(i-1)次方，总结点数是2的h次方-1

3、完全二叉树

定义1：叶子结点只会出现在最后2层，且最后一层的叶子结点靠左对齐

定义2：将满二叉树的叶子结点从右向左依次移除x个，得到完全二叉树

性质：

a.满二叉树一定是完全二叉树

b.完全二叉树度为1的结点，最多有一个，且一定是左子树

c. h = ceiling(log2n)

完全二叉树的特点是什么?

完全二叉树的叶子节点数公式为：设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。2、当n为偶数（即度为1的节点为1个）， n0= n/2。n1，n2，都可以求。特殊类型：1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。相关术语：1、结点：包含一个数据元素及若干指向子树分支的信息。2、结点的度：一个结点拥有子树的数目称为结点的度。3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。以上内容参考 百度百科-二叉树

二叉树的高度是什么？

二叉树的高度是高度是从下往上数。二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。二叉树性质：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：当i=1时，该节点为根，它无双亲节点。当i>1时，该节点的双亲节点的编号为i/2。若2i≤n，则有编号为2i的左节点，否则没有左节点。若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

二叉树的高度是多少？

二叉树的高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。二叉树的高度是垂直方向上树的长度的量度。 叶节点的高度为0，因为它们下面没有节点。 二叉树的根节点的高度是整个树的高度。 特定节点的高度是从该节点到叶节点的最长路径上的边数。特点：很多时候，人们对二叉树的深度和高度感到困惑。 这是因为二叉树的深度始终等于二叉树的高度，但是它们不相同，并且互换使用这些术语是不正确的。 因此，重要的是要了解二叉树的高度和深度之间的差异。二叉树的高度是垂直方向上树的长度的量度，它是从孩子到父母的向上方向测量的，叶节点的高度为0，因为它们下面没有节点。二叉树的根节点的高度是整个树的高度。 特定节点的高度是从该节点到叶节点的最长路径上的边数。