性质1二叉树第i层上的结点数目最多为.doc

《性质1二叉树第i层上的结点数目最多为.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、性质1二叉树第i层上的结点数目最多为2^(i-1)(i≥1)。性质2深度为k的二叉树至多有2^k-1个结点(k≥1)。性质3在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。1、满二叉树(FullBinaryTree)　一棵深度为k且有2k-1个结点的二又树称为满二叉树。　满二叉树的特点：　　（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。2、完全二叉树(CompleteBinaryTree)若一棵二叉树至

2、多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。性质4具有n个结点的完全二叉树的深度为trunc(log2n)+1性质5一棵有n个结点的完全二叉树，对于任一编号为i的结点，有：（1）如果i=1，则结点为i为根，无父结点；如果i>1，则其父结点编号为trunc(

3、n/2)。（2）如果2*i>n，则结点为i为叶结点；否则左孩子编号为2*i。（3）如果2*i+1>n，则结点i无右孩子；否则右孩子编号为2*i+1。