树及二叉树（选择题）

树

在树中，总结点数为所有结点的度和再加一

5、设一棵度为3的树，其中度为2，1.0的结点数分别为3，1，6。该树中度为3
的结点数为_。

二叉树 

设二叉树的所有节点个数为N，度为零的结点（叶子结点）个数为n0，度为一的结点个数为n1，度为二的结点个数为n2。有如下性质

二叉树的性质

1、N = n1 + n2 + n0

2、n0 = n2 + 1

满二叉树

定义：除最后一层外，所有结点都有两个子结点

堆：属于满二叉树结构，但是要满足出最后一行外，每个节点和其两个子结点要有一定的关系

（1，2，3，4，5，6，7，8）是（8，7，6，5，4，3，2，1）是

（2，1，3，6，5，4，8，7）不是

性质：

1、满二叉树在第 i 层 上有2 ^ ( i - 1 )个结点，即满二叉树叶子结点数为2 ^ ( i - 1 )

2、深度为m的满二叉树有 2 ^ m - 1 个结点

完全二叉树

定义：除最后一层外，每层的节点数达到最大，最后一层只缺少右边的若干节点（从右往左依次缺几个都可以，但是不能间接缺少）。

二叉树的遍历

前序遍历

在二叉树的前面画点，再一次来连接即可

中序遍历

在二叉树的中间画点，再一次来连接即可

后序遍历

在二叉树的后面画点，再一次来连接即可