满足以下两个条件的性质叫做二叉树

1.每个结点的度都不大于2

2.每个结点的孩子次序不能颠倒

性质

在二叉树的第i层上至多有2^(i-1)个结点

深度为k的二叉树上至多有2^k-1个结点

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。

具有n个结点的完全二叉树的深度为log2n+1。

如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1=i=n),有：

（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i1，则其双亲的编号是

i/2(整除）。

（2）如果2in，无左孩子；否则，其左孩子是结点2i。

（3）如果2i＋1n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

满二叉树与完全二叉树的概念

满二叉树：深度为k且有个2^k-1结点的二叉树。

完全二叉树：深度为k，节点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应，则为完全二叉树。其中，度为1的结点数目要么为1，要么为0

常见题目

已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是？个

最多：第六层满,前六层共有2^6-1=63个，第七层有：2*(2^(6-1)-10)=44，共有107个。

最少：第六层只有10个，前五层满共有2^5-1=31个，则共有41个结点。

一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是？

度为2的结点个数：m-1,则度为1的结点个数为：n-m-(m-1)，即n-2m+1

已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是？

30（度为0）+29（度为2）+0（度为1）=59

一棵深度为6的满二叉树有？个分支结点和？个叶子

分支结点即度为1和度为2的结点

n0=2^(6-1)=2^5=32

满二叉树中，n0=0,n2=n0-1=31

所以分支结点数目为n1+n2=0+31=31,叶子结点数=32

含有11个结点的不相似的二叉树有?棵

含n个结点的不相似的二叉树有[C(2n,n)]/(n+1)棵,即[22!/(11!*11!)]/12=58786种（卡特兰数的概念）

一个包含n个结点的四叉树，每个结点都有4个指向孩子结点的指针，这4个指针中有？个空指针

共有4n个指针，其中仅有n-1个指针被使用，因为没有指针指向根结点，其余结点都有一个指针指向它，所以共有4n-(n-1)=3n-1个指针。