一、二叉树的性质

性质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的从右向左数第２个

孩子的结点编号为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"); }

}

}