数据结构与算法Java（七）：二叉树基础（上）

一、树

相关节点关系：A是B的父节点；B是A的子节点；BCD是兄弟节点；E是根节点；没有子节点的节点叫做叶子节点或叶节点，如GHIJKL

节点的高度（从下往上） = 节点到叶子节点的最长路径（边数）

节点的深度（从上往下） = 根节点到这个节点所经历的边的个数

节点的层数 = 节点的深度 + 1

树的高度 = 根节点的高度

二、二叉树

1、满二叉树：叶子节点全都在最底层，除叶子结点外，每个节点都有左右两个子节点

     完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其它层的结点个数都要达到最大

2、二叉树的存储方式：

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

2）基于数组的顺序存储法，其中左子结点的下标为2*i；右子节点为2*i+1

3、二叉树的遍历：

1. 前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树
2. 中序遍历：对于书中的任意节点来说，先打印左子树，然后再打印它本身，最后打印它的右子树。（终须遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(N))
3. 后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印右子树，最后再打印节点本身

//个人的记忆方式是：三种顺序对应节点本身，都按照先左后右

三种遍历方法都是递归过程，时间复杂度是O（n）

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

 

 

参考资料：极客时间的《数据结构与算法之美》王争