数据结构—— 树（二叉树）详解

结构示意图：

树的常用术语(结合示意图理解):

1. 节点 ：ABCD这些都是节点
2. 根节点：没有父节点，A就是根节点
3. 父节点：相对而言，A是B和C的父节点
4. 子节点：反之，B和C就是A的子节点
5. 叶子节点(没有子节点的节点) ：EFGH就是叶子结点
6. 节点的风(节点值)
7. 路径(从root节点找到该节点的路线) A到H的路径就是 ABDH
8. 层：一共有4层
9. 子树：DH是A或者B的子树
10. 树的高度(最大层数)

二叉树的概念及知识点

二叉树： 每个节点最多只能有两个子节点的一种形式称为二叉树。

如果该二叉树的所有叶子节点都在最后一层，并且结点总数 = 2^n - 1,n为层数，则我们称为 满二叉树。
如果该二叉树的所有叶子节点都在最后一-层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为 完全二叉树。

二叉树的遍历方式

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树， 再遍历右子树，最后输出父节点

二叉树的遍历思路

1. 前序遍历
   先输出当前节点(初始的时候是roor节点)
   如果左子节点不为空，则递归继续前序遍历
   如果右子节点不为空，则递归继续前序遍历
2. 中序遍历
   如果当前节点的左子节点不为空，则递归中序遍历，
   输出当前节点
   如果当前节点的右子节点不为空，则递归中序遍历
3. 后序遍历
   如果当前节点的左子节点不为空，则递归后序遍历，
   如果当前节点的右子节点不为空，则递归后序遍历
   输出当前节点