基本概念

树，一种非线性表数据结构：

• 节点
  “树”里面的每个元素
• 父子关系
  连线相邻节点之间的关系
• 兄弟节点
  节点的父节点是同一个节点
• 根节点
  没有父节点的节点
• 叶（子）节点
  没有子节点的节点
• 节点的高度
  节点到叶节点的最长路径(边数)
• 树的高度
  根节点的高度
• 节点的深度
  根节点到该节点所经历的边的个数
• 节点的层数
  节点的深度+1
  

二叉树（Binary Tree）

最常用的树结构。

每个节点最多有两个子节点：左子节点，右子节点。

• 满二叉树
  叶节点全在最底层，除叶节点外，每个节点都有左右两个子节点
• 
• 完全二叉树
  叶节点都在最底下两层，最后一层的叶节点都靠左排列，且除最后一层，其他层节点个数都达到最大

为啥就把最后一层的叶子节点靠左排列的叫完全二叉树？靠右排列为啥就不行？

要搞清楚完全二叉树为啥这么定义，先学习

如何存储二叉树？

基于指针或者引用的二叉链式存储法

每个节点有三个字段：

• 一个存储数据
• 另两个指向左右子节点的指针

大部分二叉树代码都是通过这种结构实现的。