一、二叉树的性质
性质1、二叉树的第i层上至多有2 i-1(i ?1)个结点。用数学归纳法证明
推广:k叉树(或度为k的树)的第i层上至多有k i-1(i ?1)个结点
性质2、度为h的二叉树中至多含有2h-1个结点。
21-1 + 2 2-1+……+ 2 h-1 = 2 h-1
推广:深度为h的k叉树(或度为k的树)中至多含有 (k h-1)/(k-1)个结点
k1-1 + k 2-1+……+ k h-1 =( k h-1)/(k-1)
性质3、若在任意一棵二叉树中,有n0个叶子结点,
有n2个度为2的结点,则:n0=n2+1
证明:设:有n0个叶子结点,有n1个度为1的结点,有n2个度为2的结点, 则二叉树中结点总数为:n=n0+n1+ n2 (1)
设分支的总数为m,则:m= n1+2 n2 (2)
因为n=m+1(3)
所以: n0+n1+ n2 = n1+2 n2 +1
整理得: n0= n2+1
推广: 度为k的树有n1个度为1的结点, n2个度为2的结点,nk个度为k的结点则n0为:
?
i=1 k ( i- 1)ni+1
性质3推广的证明于性质3的证明
设:有n0个叶子结点,有n1个度为1的结点, n2个度为2的结点,nk个度为k的结点 则结点总数为:n=n0+n1+ n2 +……+nk(1)
设分支的总数为m,则:m= n1+2 n2+……+knk
因为n=m+1(3)
所以:n0+n1+ n2 +……+nk = n1+2 n2+……+knk +1
整理得: n0= 0n1+1n2+……+(k-1)nk+1
性质4、具有n个结点的完全二叉树,其深度为?㏒2n?+1
证明:设n个结点的完全二叉树的深度为k,根据性质2可知,k-1层满二叉树的结点总数为: 2k-1-1
k层满二叉树的结点总数为: 2k-1
显然有:
2k-1 - 1 < n ? 2k- 1 ? 2k- 1 ? n < 2k
取对数有:k -1 ? log2n < k
因为k是整数,所以k -1 = ?log2n? , k= ?㏒2n?+1
结论成立。
推广: 具有n个结点的完全k叉树,其深度为? logk(k-1) n ? +1
设n个结点的完全k叉树的深度为h,根据性质2推广可知,
h-1层满k叉树的结点总数为:(k h-1-1)/(k-1)
h层满二叉树的结点总数为:(k h-1)/(k-1)
显然有:
(k h-1-1)/(k-1) < n ? (k h-1)/(k-1)
k h-1-1 <(k-1) n ? k h-1
k h-1 ? (k-1) n< k h
取对数有:h -1 ? logk(k-1) n <h
因为h是整数,所以h -1 = ? logk(k-1) n ? , h= ? logk(k-1) n ? +1
性质5、设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,3……,n给结点进行编号,则对于编号为k(k=1,2,……n)的结点有以下结论:
(1)若k=1,则该结点为根结点,它没有双亲结点;若k>1,则该结点的双亲结点编号为 [k/2 ] 。
(2)若2k<=n,则编号为k的左孩子结点编号为2k;否则该结点无左孩子结点(显然也没有右孩子结点)。
(3)若2k+1<=n,则编号为k的右孩子结点编号为2k+1;否则该结点无右孩子结点
推广:一个深度为L的满K叉树有以下性质:第L层上的结点都是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点进行编号,求:
1)各层的结点的数目是多少?
2)编号为n的结点的双亲结点(若存在)的编号是多少?
3)编号为n的结点的第i 个孩子结点(若存在)的编号是多少?
4)编号为n的结点有右兄弟的条件是什么?如果有,其右兄弟的编号是多少? 答:
h-1(1)k(h为层数)
h-1(2)因为该树每层上均有K个结点,从根开始编号为1,则结点i的从右向左数第2个
孩子的结点编号为ki。设n 为结点i的子女,则关系式(i-1)k+2<=n<=ik+1成立,因i是整数,故结点n的双亲i的编号为?n-2)/k?+1。
(3) 结点n(n>1)的前一结点编号为n-1(其最右边子女编号是(n-1)*k+1),故结点 n的第 i个孩子的编号是(n-1)*k+1+i。
(4) 根据以上分析,结点n有右兄弟的条件是,它不是双亲的从右数的第一子女,即 (n-1)%k!=0,其右兄弟编号是n+1。
二:满二叉树:
一棵深度为k且有2k-1个结点的二叉树
特点:每一层上都含有最大结点数。叶子结点在同一层次上;无度为1的结点
具有n个结点的满二叉树则
叶子结点的个数为:(n+1)/2
度为2的结点的个数为:(n-1)/2
三、无度为1的结点
1: 具有n个结点的无度为1的结点的二叉树,求叶子结点的个数
n1=0
n=n1+n2+n0=n0+n2+0
n= 2n0-1
n0=(n+1)/2 n2=(n-1)/2
2:若已知叶子结点个数n0求总的结点的个数n
N=n0+n2=2n0-1
四、完全二叉树:深度为k的有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中的编号从1至n的结点一一对应
特点:除最后一层外,每一层都取最大结点数,最后一层结点都集中在该层最左边的若干位置。
叶子结点在最后两层上,度为1的结点的个数最多为1
1:具有n个结点的完全二叉树,求叶子结点的个数
n是偶数:
则n1=1
n=n1+n2+n0=n0+n2+1
n= 2n0
n0=n/2 n2=n/2-1
n是奇数:
则n1=0
n=n1+n2+n0=n0+n2+0
n= 2n0-1
n0=(n+1)/2 n2=(n-1)/2
2:若已知完全二叉树叶子结点个数:求总的结点的个数
n=n0+n1+n2
n1=1 或n1=0 n2=n0-1
n最大为2n0,最小为2n0-1
3:若已知完全二叉树第k层上具有n个叶子结点,求最多的结点个数及最少的结点个数 最多的结点个数:共有k+1层
前k层共有2k-1个结点
k+1层: 第k+1层结点数最多为第k层的非叶子结点数乘以2;第k层的
结点数为2k-1,叶子结点数为n, 非叶子结点数为(2k-1-n) ,所以第k+1层结点数最多为2(2k-1-n)个结点,所以最多结点数为2k-1+ 2(2k-1-n)
最少的结点个数:共有k层 前k-1层具有2k-1-1个结点,k层有n个共有2k-1-1+n
第二篇:求二叉树的深度叶子结点数总结点数(免费)
#include"malloc.h"
#define NULL 0
#include"stdio.h"
typedef struct node
{
char data;
struct node *lchild,*rchild;
}NODE;
int count;
NODE *crt_bt_pre()/*二叉树先序创建算法*/
{
NODE * bt;
char ch;
printf("\n\t\t\t");
scanf("%c",&ch);
getchar();
if(ch==' ') bt=NULL;
else
{
bt=(NODE*)malloc(sizeof(NODE));
bt->data=ch;
printf("\n\t\t\t请输入%c结点的左孩子:",bt->data); bt->lchild=crt_bt_pre();
printf("\n\t\t\t请输入%c结点的右孩子:",bt->data); bt->rchild=crt_bt_pre();
}
return(bt);
}
void Preorder(NODE* bt)/*二叉树先序递归遍历算法*/ {
if(bt!=NULL)
{
printf("\n\t\t\t %c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
void Inorder(NODE* bt)
{
if(bt!=NULL)
{
Inorder(bt->lchild);
printf("\n\t\t\t %c",bt->data);
Inorder(bt->rchild);
}
}
void Postorder(NODE* bt)
{
if(bt!=NULL)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("\n\t\t\t %c",bt->data);
}
}
int CountLeaf(NODE *bt)/*求二叉树叶子结点数的递归遍历算法*/ {
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
count++;
CountLeaf(bt->lchild);
CountLeaf(bt->rchild);
return(count);
}
int CountNode (NODE* bt)/*求二叉树结点数的递归遍历算法*/ {
if(bt==NULL)
return 0;
else
count++;
CountNode(bt->lchild);
CountNode(bt->rchild);
return(count);
}
int TreeDepth(NODE* bt)/*求二叉树深度的递归遍历算法*/ {
int x,y;
if(bt==NULL)
return 0;
else
x=TreeDepth(bt->lchild);
y=TreeDepth(bt->rchild);
if(x>y)
return(x+1);
else
return(y+1);
}
void main()
{
NODE *bt;
char choice;
int j=1;
int x;
while(j)
{
printf("\n\n\n");
printf("\t\t\t-二叉树的基本运算--\n");
printf("\n\t\t\t************************************");
printf("\n\t\t\t* 1-------建二 差树 *");
printf("\n\t\t\t* 2-------先序 遍历 *");
printf("\n\t\t\t* 3-------中序 遍历 *");
printf("\n\t\t\t* 4-------后序 遍历 *");
printf("\n\t\t\t* 5-------统计 叶子数 *");
printf("\n\t\t\t* 6-------统计 结点数 *");
printf("\n\t\t\t* 7-------求二叉树深度 *");
printf("\n\t\t\t* 0-------退 出 *");
printf("\n\t\t\t************************************");
printf("\t\t\t请选择菜单号(0--7):");
scanf("%c",&choice);getchar();
if(choice=='1')
{
printf("\n\t\t\t请输入按先序建立二叉树的结点序列: ");
printf("\n\t\t\t说明: 逐个输入,输入空格代表后续结点为空,按回车输入下一个结点.");
printf("\n\t\t\t请输入根结点: ");
bt=crt_bt_pre();
printf("\n\t\t\t二叉树成功建立!\n");
}
else if(choice=='2')
{ printf("\n\t\t\t该二叉树的先序遍历序列为: "); Preorder(bt); } else if(choice=='3') { printf("\n\t\t\t该二叉树的中序遍历序列为: "); Inorder(bt); } else if(choice=='4') { printf("\n\t\t\t该二叉树的后序遍历序列为: "); Postorder(bt); } else if(choice=='5') { count=0; CountLeaf(bt); printf("\n\t\t\t该二叉树有%d个叶子结点。\n",count); } else if(choice=='6') { count=0; x=CountNode(bt); printf("\n\t\t\t该二叉树共有%d个叶子结点。\n",count); } else if(choice=='7') { x=TreeDepth(bt); printf("\n\t\t\t该二叉树的深度为%d",x); } else if(choice=='0') { j=0; printf("\t\t\t程序结束!\n"); }
}
}