二叉树

树

每个元素代表一个结点，相邻节点之间的连线关系，称为父子关系。
父节点
子节点
兄弟节点：节点的父节点是同一个节点
根节点：没有父节点的节点
叶子节点/叶节点：没有子节点的节点

节点的高度=节点到叶子节点的最长路径(边数)。起点是0，从下往上
节点的深度=根节点到这个所经历的边的个数。起点是0，从上往下
节点的层数=节点的深度+1。起点是1，从上往下
树的高度=根节点的高度

二叉树

每个节点最多有两个叉-两个子节点，分别是左子节点和右子节点。但不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
满二叉树：叶子节点全部在最底层，除叶子节点之外，每个节点都有左右两个子节点。
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其它层的节点个数都要达到最大。

存储/表示一棵二叉树

1. 基于指针或者引用的二叉链式存储法
   每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。
2. 基于数组的顺序存储法
   把根节点存储在下标i=1的位置，左子节点存储在下标2i=2的位置，右子节点存储在2i+1=3的位置。以此类推。
   如果节点X存储在数据中下标为i的位置，下标为i2的位置存储的就是左子节点，下标为2i+1的位置存储的就是右子节点。反过来，下标为i/2的位置存储的是它的父节点。只要知道根节点存储的位置(一般为下标为1的位置，便于计算)，可以通过下标计算，把整棵树都串起来。
   完全二叉树，仅仅浪费了一个下标为0的存储位置，如果是非完全二叉树，会浪费比较多的数组存储空间。如果某棵二叉树是完全二叉树，那用数组存储无疑是最节省内存的一种方式。(堆-完全二叉树)

遍历二叉树-递归¹

1. 前序遍历
   对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

2. 中序遍历
   对于树中的任意节点来说，先打印它的左子树，再打印它本身，最后打印它的右子树。

3. 后序遍历
   对于树中的任意节点来说，先打印它的左子树，再打印它的右子树，最后打印这个节点本身。

   递推公式：

   前序遍历  
   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

   伪代码：

   //前序遍历
   void preOrder(Node* root) {
       if(root == null) return;
       print root;
       preOrder(root -> left);
       preOrder(root -> right);
   }
   //中序遍历
   void inOrder(Node* root) {
       if(root == null) return;
       inOrder(root -> left);
       print root;
       inOrder(root -> right);
   }
   //后序遍历
   void postOrder(Node* root) {
       if(root == null) return;
       postOrder(root -> left);
       postOrder(root -> right);
       print root;
   }

4. 按层遍历
   借助队列辅助：根节点先入队列，队列不为空，取出对头元素，如果左子存在就入队列，否则什么也不做，如果右子同理，直到队列为空，表示树层次遍历结束。

   按层遍历

   public class TreeNode<T> {
       T val;
       TreeNode left;
       TreeNode right;
       TreeNode(T x) {
           val = x;
       }
   }
   private List<TreeNode> floorlevelOrder(TreeNode root) {
       List<TreeNode> result = new ArrayList<>();
       //利用队列先进先出的特点实现按层遍历
       Queue<TreeNode> queue = new LinkedList<>();
       //根节点入队
       queue.add(root);
       //从队列中弹出各结点数据，直到队列为空，遍历完毕
       while(!queue.isEmpty()) {
           //弹出队首元素，放入结果集。并依次将其左右子节点入队(如果存在的话)，进行下一轮循环
           TreeNode node = queue.poll();
           result.add(node);
           if(node.left != null) {
               queue.add(node.left);
           }
           if(node.right != null) {
               queue.add(node.right);
           }
       }
       return result;
   }

二叉树遍历时间复杂度

每个节点最多会被访问两次，遍历操作的时间复杂度跟节点的个数n成正比，时间复杂度为O(n)。

参考&扩展

• [1] 一篇总结二叉树的4种遍历方式（含模板）