二叉树的性质有些啊？怎么求它的深度？

yxm忍 · 2018-4-30 01:59:27

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2 1。

整体上考虑：每一层递归返回该层往下的最大高度，上一层的最大高度就是下一层的最大高度加。考虑上一层就是根，那么二叉树的最大高度就是次一层的最大高度加1。很明显，次一层的最大高度不是左子树的高度就是右子树的高度，以此类推，每一层都有这个性质。

If(left>right)

Height=lift;

Else

Height=right;

Return Height;

对不，这个递归的结尾是不是应该就是这个样子的，再来，就是求left，和right的值，而它们都是根据自己的左右结点递归来求的，那么下一步就是往里面加递归了。

Int may_height(Node* head)

{

Node* p=head;

Int height;

If(p->left==NULL)return -1;

Else

Left= may_height(p->left);

If(p->right==NULL)return -1;

Else

right= may_height(p->right);

If(left>right)

Height=lift;

Else

Height=right;

Return Height;

}

运用特值代入，求得左右子树为空时，返回-1。

OK，完成了！

cui735697452 · 2018-4-30 01:59:26

二叉树性质
性质1 ：在二叉树的第i层上至少有2^（i-1）个结点
性质2：深度为k的二叉树至多有2^(k-1)个结点
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
性质4：具有n个结点的完全二叉树的深度是【log2n】+1（向下取整）
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1飩?飩?)，有：
如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是飪玦/2飪

追隨心靈 · 2018-4-30 01:59:25

第二点，不是2的k-1次方，应该是2的k次方-1

热心网友 · 2018-4-30 01:59:24

　　二叉树性质如下：
　　1 ：在二叉树的第i层上至少有2^（i-1）个结点
　　2：深度为k的二叉树至多有2^(k-1)个结点
　　3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
　　4：具有n个结点的完全二叉树的深度是【log2n】+1（向下取整）
　　5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1飩?飩?)，有：
　　如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是飪玦/2飪

二叉树的性质有些啊？怎么求它的深度？

4 个回复