一.二叉树的性质
1.
若规定根节点的层数为
1
，则一棵非空二叉树的
第
i
层上最多有
个结点
.
2.
若规定根节点的层数为
1
，则
深度为
h
的二叉树的最大结点数是
.
3.
对任何一棵二叉树
,
如果度为
0
其叶结点个数为
,
度为
2
的分支结点个数为
,
则有
＝ ＋
1
4.
若规定根节点的层数为
1
，具有
n
个结点的满二叉树的深度
，
h=
. (ps
：
是
log
以
2
为底，
n+1
为对数
)
5.
对于具有
n
个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从
0
开始编号，则对
于序号为
i
的结点有：
二.有关二叉树的选择题讲解
1.
某二叉树共有
399
个结点，其中有
199
个度为
2
的结点，则该二叉树中的叶子结点数为（
）
A
不存在这样的二叉树
B 200
C 198
D 199
2.
下列数据结构中，不适合采用顺序存储结构的是（
）
A
非完全二叉树
B
堆
C
队列
D
栈
3.
在具有
2n
个结点的完全二叉树中，叶子结点个数为（
）
A n
B n+1
C n-1
D n/2
4.
一棵完全二叉树的节点数位为
531
个，那么这棵树的高度为（
）
A 11
B 10
C 8
D 12
5.
一个具有
767
个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
1.由性质五得度数为0的叶子节点数比度为2的结点数的多一。所以选B。
当二叉树为满二叉树时，是不存在度为1的结点。
当二叉树为完全二叉树时，度为1的结点数小于等于1。
2.选A。
该题如果为单选就选择最错误的那一个，如果是多选还要选择C。队列是用链表实现比较合适，而链表不是顺序存储结构。
顺序存储结构有：顺序表、队列（数组实现）、栈
堆是可以利用数组实现的。
3.选A。
由性质五得度数为0的叶子节点数比度为2的结点数的多一。
当二叉树为满二叉树时，是不存在度为1的结点。
当二叉树为完全二叉树时，度为1的结点数小于等于1。
设度为0的结点数为N0，度为1的结点数为N1，度为2的数为N2。
N0+N1+N2=2n
N0+N1+N0-1=2n
2*N0-1+N1=2n
其中N0、N1、N2是整数，那么这里N1只能为1
N0=n
4.选B
N代表完全二叉树的总结点数
将选项中的数值代入，看531在哪个范围内
2^9=512 2^10=1024
5.选B
计算过程同3
三.二叉树的储存方式
1.顺序存储
2.链表存储
a.二叉链表
?
?b.三叉链表
四.二叉树的三种遍历方式及相关讲解
1.
前序遍历
(Preorder Traversal
亦称先序遍历
)——
访问根结点的操作发生在遍历其左右子树之前。
2.
中序遍历
(Inorder Traversal)——
访问根结点的操作发生在遍历其左右子树之中（间）。
3.
后序遍历
(Postorder Traversal)——
访问根结点的操作发生在遍历其左右子树之后。
以上三种遍历也可称呼为前根遍历、中根遍历、后根遍历。
例子讲解：
?前根遍历顺序：根、左子树、右子树
该图前根遍历顺序为：1 2 3 NULL NULL NULL 4? 5 NULL NULL 6 NULL NULL?
中根遍历顺序：左子树、根、右子树
该图中根遍历顺序为：NULL 3 NULL 2 NUL NULL 5 NULL 1 4 NULL 6 NULL
后根遍历顺序：左子树、右子树、根
该图后根遍历顺序为：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4
五.二叉树三种遍历方式递归代码实现
?
六.其他有关二叉树功能的实现
1.遍历计数
?
?//子问题解决问题
将一棵树不断得划分为根、左子树、右子树。
?2.求二叉树叶子结点的个数
?
3.计算二叉树的高度
?
?//子问题解决
4.计算二叉树的第k层的结点个数?
学习真的是一件好孤独好矛盾的事情。当我躺在宿舍刷着手机，会很焦虑；当我抱着电脑独自在自习室、教室学习，有的时候会感到很享受、有的时候会感到很孤独。当学的东西越来越多，我很疑惑。如果真的再努力些，自己是否有进入这个行业的资格。天地之大，总会有我立身之处。还是在该学习的时候认真学，该玩的时候就认真玩。