数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

二叉树的定义

二叉树T：一个有穷的节点集合。

这个集合可以为空；若不为空，则它是由根节点和称为其左子树 和右子树 的两个不相交的二叉树组成。

二叉树具体的五种基本形态

1.空树

2.只有一个节点

3.有左子树，但右子树为空

4.有右子树，但左子树为空

5.左右两子树都不为空

要注意，二叉树与普通的度为二的树不同的一点是：二叉树的子树有左右顺序之分。

特殊二叉树

斜二叉树

斜二叉树都只有左儿子或者都只有右儿子，这样的二叉树，实际上相当于一个链表，形成了一个线性结构。

满二叉树

又叫完美二叉树

这样的二叉树是除了最底层的叶节点没有节点，其它每一个节点都有两个儿子；且叶节点都在同一层。

完全二叉树

有n个节点的二叉树，对树中节点按从上至下、从左到右顺序进行编号，编号为i（1<= i <= n）节点与满二叉树中编号为i节点在二叉树中位置相同。

简单地来说，完全二叉树的节点编号要与它满二叉树形态下的节点编号相一致，如下图：

二叉树的几个重要性质

• 一个二叉树第i层的最大节点数为 ，i >=1。
  

这个性质很好理解，像满二叉树这种树每一层都达到了最大节点数，节点数满足首项为1，公比为2的等比数列。

• 深度为K的二叉树有最大节点总数为： -1，k >=1。
  

能达到最大节点数的树是怎样的呢？

当然就是完美二叉树啦，其节点数：

第一层：1

第二层：2

第三层：4

......

第k层：

用等比数列求和公式

就可以求和最大节点数为： -1。

• 对任何非空二叉树T，若n0表示叶节点的个数，n2是度为2的非叶节点个数，那么两者满足关系n0 = n2 +1。
  

我们从边的角度来推导出这个性质：

初识二叉树的几个操作函数

• Boolean IsEmpty(BinTree BT)：判别BT是否为空
• void Traversal(BinTree BT)：遍历，按某个顺序访问每个节点
• BinTree CreatBinTree()：创建一个二叉树

常用的遍历方法有：

1. void PreOrderTrversal(BinTree BT)：先序——根、左子树、右子树
2. void InorderTraversal(BinTree BT)：中序——左子树、根、右子树
3. void PostOrderTraversal(BinTree BT)：后序——左子树、右子树、根
4. void LevelOrderTraversal(BinTree BT):层次遍历，从上到下、从左到右

end