二叉树的定义，性质及常见题 二叉树的基本性质

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

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无双亲，是二叉树的根；如果i>1，则其双亲的编号是

i/2(整除）。

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

（3）如果2i＋1>n，则结点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个指针。

将会后续推出二叉树的创建初始化（c语言），希望大家多多关注，多多支持！