二叉树的概念和意义（二叉树的定义性质及常见题）

二叉树的概念和意义（二叉树的定义性质及常见题）如果对一棵有n个结点的完全二叉树的结点按层序编号 则对任一结点i（1<=i<=n) 有：具有n个结点的完全二叉树的深度为log2n 1。在二叉树的第i层上至多有2^(i-1)个结点深度为k的二叉树上至多有2^k-1个结点对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2 1。

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

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语言），希望大家多多关注，多多支持！