二叉树简介和存储结构

二叉树的定义

一个有穷节点的集合，这个集合可以为空，但如果不为空，则它是由根节点和称为其左子树和右子树的两个不想交的二叉树组成。

特殊的二叉树

• 斜二叉树（实际上就是个链表）

• 完美二叉树（满二叉树）：除了叶节点的每个结点都有两个子树

• 完全二叉树
  有n个节点的二叉树，对书中节点按从上到下、从左到右顺序进行编号编号为i的节点与满二叉树中编号为i的节点在二叉树中位置相同

二叉树的几个重要性质

• 一个二叉树的第i层的最大节点数为：

• 深度为k的二叉树有最大节点总数是：

  
  
• 若n0代表业绩点的个数，n2代表度为2的节点个数，两者满足关系n0 = n2 + 1。证明如下：

边的总数 =

最后化简就是上面的公式。

二叉树的存储结构

1. 顺序存储结构：先把这颗树补齐成完全二叉树，然后按照从行到下，从左到右的顺序来给一个树编号，编号就是数组的下标。

按照这种存储结构，如何找节点的父节点、左节点、右节点呢？

• 非根节点的父节点的序号是：i / 2
• 节点的左孩子节点的序号是 2 * i (如果2i <= n 则说明没有左孩子)
• 节点的右孩子结点的序号是：2 * i +1(如果2i +1<= n 则说明没有右孩子)

这种存储结构有什么缺点呢？

如果遇到这种树则会在数组中出现很多空位，是以空间为代价的

2. 链表存储结构
如果用链表实现就很简单了
我们定义一个结构，结构里有两个指针（引用），来指向左节点，右节点。如果没有的话就为null