Java数据结构：二叉树

一、为什么需要树这种数据结构

数组存储方式的分析

• 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
• 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低。

链式存储方式的分析

• 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
• 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

树存储方式的分析

• 能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。为了更好的了解树的用法，我们先来看看二叉树是怎么工作的。

1、二叉树的基本概念

• 二叉树是n个有限元素的集合，当集合不为空时，二叉树由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的树组成，他的左子树和右子树同样为一个二叉树；当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

一颗二叉树

• 也就是说二叉树（binary tree）的每个节点不能多于有两个儿子，上面的图就是一颗二叉树。它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树
• 一棵非空树至少会有一个节点(根节点)
• 树由节点组成，每个节点的数据结构是这样的：

• 因此，我们定义树的时候往往是->定义节点->节点连接起来就成了树，而节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)
  二叉树节点的代码实现：

  public class TreeNode{
       int val; //二叉树存放数据的区域
       TreeNode leftNode; //二叉树的左节点指针
       TreeNode rightNode; //二叉树的右节点指针
  }
  

1.满二叉树

• 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。

满二叉树

2.完全二叉树

• 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。通俗一点来讲就是把树的节点按顺序从上到下、从左往右排形成的二叉树

完全二叉树

3、顺序存储二叉树

• 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组:
• 顺序存储二叉树的特点（n表示二叉树中的第几个元素(按0开始编号):
  • 顺序二叉树通常只考虑完全二叉树
  • 第n个元素的左子节点为 2 * n + 1
  • 第n个元素的右子节点为 2 * n + 2
  • 第n个元素的父节点为 (n-1) / 2

顺序存储二叉树在后面的堆排序中也会运用到，所以还是挺重要的

二、创建一颗简单的二叉树

class  BinaryTreeNode{
private int id; //节点序号
private BinaryTreeNode left; //左节点
private BinaryTreeNode right; //右节点
    //构造方法
    public  BinaryTreeNode(int id){this.id = id;}
}

为了在其他类中访问到这些字段，我们还需要get和set方法
然后我们在方法里面创建一颗这样子的树：

  public static void main(String[] args) {
        BinaryTreeNode t1 = new BinaryTreeNode(1);
        BinaryTreeNode t2 = new BinaryTreeNode(2);
        BinaryTreeNode t3 = new BinaryTreeNode(3);
        BinaryTreeNode t4 = new BinaryTreeNode(4);
        BinaryTreeNode t5 = new BinaryTreeNode(5);
        BinaryTreeNode t6 = new BinaryTreeNode(6);
        BinaryTreeNode t7 = new BinaryTreeNode(7);   //先new出7个节点      

        //然后在把他们连接起来
    t1.setLeft(t2);
    t1.setRight(t3);   //表示父节点1的左右节点
    
    t2.setLeft(t4);
    t2.setRight(t5);  //表示2的左右节点

    t3.setLeft(t6);
    t3.setRight(t7);  //表示3的左右节点
    //因为4、5、6、7都是叶子节点，叶子节点的左右节点都为null，所以不需要set
    }

遍历一颗二叉树

遍历二叉树有三种方式：

• 1.前序遍历： 先输出父节点，再遍历左子树和右子树

• 2.中序遍历：先遍历左子树，再输出父节点，再遍历右子树

• 3.后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
  要看是什么遍历，只需要看父节点的输出位置就行了，用这颗树为例子：

• 如果是前序遍历：1 ->2 ->4 ->5 ->3 ->6 ->7
  代码如下（方法写在BinaryTreeNode类中）：

  //前序遍历
  public void pre() {
    //输出父节点
    System.out.println(this.id);
    //往左遍历
    if(this.left != null) {
        this.left.pre();
    }
    //往右遍历
    if(this.right != null) {
        this.right.pre();
    }
  }
  

在main方法中使用t1.pre();遍历结果如下：

• 如果是中序遍历：4 ->2 ->5 ->1 ->6 ->3 ->7
  代码如下：

  //中序遍历
  public void mid() {
    //往左遍历
    if(this.left != null) {
        this.left.mid();
    }
    //输出父节点
    System.out.println(this.id);
    //往右遍历
    if(this.right != null) {
        this.right.mid();
    }
   }
  

在main方法中使用t1.mid();遍历结果如下：

• 如果是后序遍历：4 ->5 ->2 ->6 ->7 ->3 ->1
  代码如下：

  //后序遍历
  public void next() {
    //往左遍历
    if(this.left != null) {
        this.left.next();
    }
    //往右遍历
    if(this.right != null) {
        this.right.next();
    }
    //输出父节点
    System.out.println(this.id);
    }
  

在main方法中使用t1.next();遍历结果如下：

查找二叉树中的值

二叉树的查找也分为前、中、后序，因为大体思想和遍历差不多，我这里也只上前序查找的代码了：

      //前序查找
  public BinaryTreeNode preFind(int id) {
    BinaryTreeNode res = null;
    if(this.id == id) {
        return this;
    }
    if(this.left != null) {
        res = this.left.preFind(id);
    }
    if(res != null) {
        return res;
    }
    if(this.right != null) {
        res = this.right.preFind(id);
    }
    return res;             
}