数据结构（树）：二叉树

概述

　　二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 。二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树性质

• 二叉树的第i层上至多有2（i≥1）个节点。
• 深度为h的二叉树中至多含有2-1个节点。
• 若在任意一棵二叉树中，有n个叶子节点，有n个度为2的节点，则必有n=n+1。

二叉树特殊类型

• 满二叉树

　　如果一棵二叉树只有度为0的结点（叶子节点）和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。满二叉树又是特殊的完全二叉树。

　　满二叉树除了具备普通二叉树的性质，还具备以下性质：

1. 满二叉树中第 i 层的节点数为 2 个。
2. 深度为 h 的满二叉树必有 2-1 个节点 ，叶子数为 2。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log(n+1)（与第2点对应）。

• 完全二叉树

　　深度为h，有n个结点的二叉树当且仅当其每一个结点都与深度为h的满二叉树中编号从1到n的结点一一对应时；简单来说就是二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

　　二叉树除了满足普通二叉树的性质，还具备以下性质：

1. 具有n个节点的完全二叉树的深度为(int)logn+1。
2. 若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

　　　　当i=1时，该节点为根，它无双亲节点；

　　　　当i>1时，该节点的双亲节点的编号为i/2；

　　　　若2i≤n，则有编号为2i的左节点，否则没有左节点；

　　　　若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

二叉树存储

• 顺序存储

　　顺序存储适用于完全二叉树，因为完全二叉树从根节点往下排，可以看成是连续的节点。

　　

• 链式存储

　　

二叉树遍历

• 前序遍历：根节点-->左子节点-->右子节点

 1     public void preorderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         print(root);
 6         if (root.getLeft() != null){
 7             preorderTraversal(root.getLeft());
 8         }
 9         if (root.getRight() != null){
10             preorderTraversal(root.getRight());
11         }
12     }

• 中序遍历

 1     public void inOrderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         if (root.getLeft() != null){
 6             inOrderTraversal(root.getLeft());
 7         }
 8         print(root);
 9         if (root.getRight() != null){
10             inOrderTraversal(root.getRight());
11         }
12     }

• 后序遍历

 1     public void postOrderTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         if (root.getLeft() != null){
 6             postOrderTraversal(root.getLeft());
 7         }
 8         if (root.getRight() != null){
 9             postOrderTraversal(root.getRight());
10         }
11         print(root);
12     }

• 层次遍历

 1     public void levelTraversal(BinaryTreeNode root){
 2         if (root == null){
 3             return;
 4         }
 5         LinkedList<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
 6         queue.offer(root);
 7         while (!queue.isEmpty()){
 8             BinaryTreeNode node = queue.poll();
 9             print(node);
10             if (node.getLeft() != null){
11                 queue.offer(node.getLeft());
12             }
13             if (node.getRight() != null){
14                 queue.offer(node.getRight());
15             }
16         }
17
18     }