道生一，一生二，二生四，四生万物

一张纸对折103次，宇宙就真的放不下它了吗？带着疑问，我们今天来学习 二叉树 的相关知识。

通过本文，你能 get 到以下知识：

• 什么是二叉树？
• 二叉树的种类？
• 二叉树的存储结构？
• 二叉树 java 实现？
• 二叉树模板代码解决折纸问题？
• 二叉树的应用场景

二叉树的概念

定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为 根结点 的左子树和右子树组成。

二叉树特点

• 1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
• 2）左子树和右子树是有顺序的，次序不能任意颠倒。
• 3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树术语

• 节点的度 ：一个节点含有的子树的个数称为该节点的度；
• 树的度 ：一棵树中，最大的节点的度称为树的度；
• 叶节点 或 终端节点 ：度为零的节点；
• 父亲节点 或 父节点 ：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点 ：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点 ：具有相同父节点的节点互称为兄弟节点；
• 节点的 层次 ：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的 高度 或 深度 ：树中节点的最大层次；
• 堂兄弟节点 ：父节点在同一层的节点互为堂兄弟；
• 节点的祖先 ：从根到该节点所经分支上的所有节点；
• 子孙 ：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林 ：由m（m>=0）棵互不相交的树的集合称为森林；

2.二叉树的种类

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

二叉搜索树

二叉搜索树又被称为二叉排序树，那么它本身也是一棵二叉树，那么满足以下性质的二叉树就是二叉搜索树：

• 1、若左子树不为空，则左子树上左右节点的值都小于根节点的值
• 2、若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值
• 3、它的左右子树也要分别是二叉搜索树

平衡二叉树

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵 平衡二叉树 。

满二叉树

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。 满二叉树的特点有：

• 1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
• 2）非叶子结点的度一定是2。
• 3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶结点都向左边靠拢填满。 构造一颗完全二叉树就是【从上到下，从左往右】的放置节点。

满二叉树和 完全二叉树 的区别

• 左侧为满二叉树但不是完全二叉树，要补全的话可以给第二层最左节点下加两个子节点，或删除当前最下层的两个节点。
• 右侧是一颗完全二叉树但并不是满二叉树，因为最下层最后一个节点没有兄弟节点，即其父节点只有一个子节点，不满，补满的话再加一个右子节点即可【满二叉树的节点要么没孩子，要有就一定得是俩】。

3.二叉树的存储结构

二叉树的存储结构有两种，顺序存储结构和 链式存储结构 。

3.1.顺序存储结构

按照 顺序存储结构 的定义，我们可以使用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。如下图所示：

这种存储方式对于满二叉树和完全二叉树是非常合适也是很高效方便的。因为满二叉树和完全二叉树采用顺序存储结构既不浪费空间，也可以根据公式很快地确定结点之间的关系。

但是对于一般的二叉树而言，必须用“虚结点”将一颗二叉树补成一棵完全二叉树来存储，否则无法确定结点之间的关系，这样的话就会造成存储空间的浪费。一种极端的情况是，对于单支二叉树，为了存储k个结点，需要2k-1个存储单元，下图说明了这种情况：

3.2.链式存储结构

设计不同的结点结构可以构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的 链表 中的结点至少包含3个域：数据域和左、右指针域。利用这种结点结构所得的二叉树的存储结构称之为二叉链表，见下图。容易证明，在具有n个结点的二叉链表中有n+1个空链域。

下述代码是最简单的二叉链表的结点结构：

 public class DoubleLinkedNode<T> {
     private  T data;// 数据域
    private DoubleLinkedNode<T> left;
    private DoubleLinkedNode<T> right;
    public T getData() {
        return data;
    }
    public  void  setData(T data) {
        this.data = data;
    }
    public DoubleLinkedNode<T> getLeft() {
        return left;
    }
    public void setLeft(DoubleLinked node <T> left) {
        this.left = left;
    }
    public DoubleLinkedNode<T> getRight() {
        return right;
    }
    public void setRight(DoubleLinkedNode<T> right) {
        this.right = right;
    }
}  

有时，为了便于找到结点的双亲，则还可以在结点结构中增加一个指向其双亲结点的指针域，如下图所示，由这种结点结构所得的二叉树的存储结构称之为三叉链表。

不同的存储结构实现二叉树操作的方法也不同。例如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需要从根结点出发一一查找。在实际应用中，要根据二叉树的实际用途来选择存储结构。

下述代码，我们以三叉链表作为二叉树的存储结构，如下：

 public class TripleLinkedNode<T> {

    private T data;// 数据域

    private TripleLinkedNode<T> parent;// 父结点

    private TripleLinkedNode<T> left;// 左孩子

    private TripleLinkedNode<T> right;// 右孩子

    private int height;// 以该结点为根的子树的高度

    private int size;// 该结点的子孙数（包括结点本身）

    private boolean isVisited; // 访问标记

    public TripleLinkedNode() {

        this(null);

    }

    public TripleLinkedNode(T e) {

        data = e;

        height = 1;// 初始化高度为1，即自己的高度

        size = 1;// 初始化的子孙数为1，即自己

        parent = left = right = null;

        isVisited = false;

    }

    public T getData() {

        return data;

    }

    public void setData(T data) {

        this.data = data;

    }

    public boolean isVisited() {

        return isVisited;

    }

    public void setVisited(boolean isVisited) {

        this.isVisited = isVisited;

    }

// 辅助方法，判断当前结点的位置情况
    /**
     * 是否有父亲
     *
     * @return
     */    public  boolean  hasParent() {
        return parent != null;
    }

    /**
     * 是否有左孩子
     *
     * @return
     */
    public boolean hasLeft() {
        return  left  != null;
    }

    /**
     * 是否有右孩子
     *
     * @return
     */    public boolean hasRight() {
        return right != null;
    }

    /**
     * 是否是叶子结点
     *
     * @return
     */
    public boolean isLeaf() {

// 既没有左孩子也没有右孩子
        return !hasLeft() && !hasRight();
    }

    /**
     * 判断是否是父结点的左孩子
     *
     * @return
     */    public boolean isLeft() {
        return hasParent() &&  parent .left == this;
    }

    /**
     * 判断是否是父结点的右孩子
     *
     * @return
     */    public boolean isRight() {
        return hasParent() && parent.right == this;
    }

// 与height有关的方法
    /**
     * 取结点的高度，即以该结点为根的树的高度
     *
     * @return
     */    public int getHeight() {
        return height;
    }

    /**
     * 更新当前结点及其祖先的高度
     */    public void updateHeight() {
// 新高度初始化为1，高度等于左右子树高度加1中的大者
       int newHeight = 1;
        if (hasLeft()) {
            newHeight = Math.max(newHeight, getLeft().getHeight() + 1);
        }
      
        if (hasRight()) {
            newHeight = Math.max(newHeight, getRight().getHeight() + 1);
        }

        if (newHeight == height) {
            return;// 高度没有发生变化直接返回
        }

        height = newHeight;// 否则更新高度

        if (hasParent()) {
            getParent().updateHeight();// 递归更新祖先的高度
        }
    }

// 与size有关的方法
    /**
     * 获取以该结点为根的树的结点数
     *
     * @return
     */    public int getSize() {
        return size;
    }

    /**
     * 更新当前结点及其祖先的子孙数
     */    public void updateSize() {
        size = 1;// 初始化为1，结点本身

        if (hasLeft()) {
            size += getLeft().getSize();// 加上左子树的规模
        }

        if (hasRight()) {
            size += getRight().getSize();// 加上右子树的规模
        }

        if (hasParent()) {
            getParent().updateSize();// 递归更新祖先的规模
        }
    }

// 与parent有关的方法
    /**
     * 获取父结点
     * @return
     */    public TripleLinkedNode<?> getParent() {
        return parent;
    }

    /**
     * 断绝与父结点的关系
     */    public void sever() {
         if  (!hasParent()) {
            return;
        }

// 更新结点
        if (isLeft()) {
            parent.left = null;
        } else {
            parent.right = null;
        }
// 更新parent的height和size
        parent.updateHeight();
        parent.updateSize();
        parent = null;
    }

// 与left有关的方法
    /**
     * 获取左孩子
     *
     * @return
     */    public TripleLinkedNode<T> getLeft() {
        return left;
    }

    /**
     * 设置当前结点的左孩子，返回原左孩子
     *
     * @param l
     * @return
     */    public TripleLinkedNode<T> setLeft(TripleLinkedNode<T> l) {
        TripleLinkedNode<T> oldLeft = this.left;

// 断开当前左孩子的结点关系
        if (hasLeft()) {
            left.sever();
        }

        if (l != null) {
            l.sever();// 断开l与其父结点的关系
            this.left = l;
            l.parent = this;// 不要忘记parent指针
            this.updateHeight();
            this.updateSize();
        }
        return oldLeft;
    }

// 与right有关的方法
    /**
     * 获取右孩子
     *
     * @return
     */    public TripleLinkedNode<T> getRight() {
        return right;
    }

    /**
     * 设置当前结点右孩子，返回原右孩子
     *
     * @param r
     * @return
     */    public TripleLinkedNode<T> setRight(TripleLinkedNode<T> r) {
        TripleLinkedNode<T> oldRight = this.right;
        if (hasRight()) {
            right.sever();
        }

        if (r != null) {
            r.sever();
            this.right = r;
            r.parent = this;
            this.updateHeight();
            this.updateSize();
        }

        return oldRight;
    }
}  

可以看到，我们为了方便使用，在三叉链表的结点结构加入了一些属性，其中，parent表示指向父结点的指针，height表示以该结点为根的子树的高度，size表示该结点的子孙数（包括自身），另外，还有isVisited访问标记，用于之后的遍历中。

并且，在结点中实现了各个需要用到的方法，其中最重要的是setLeft()和setRight()设置左右孩子的两个方法。

4、二叉树的基本操作

二叉树的实现要比普通树容易，因为其每个节点最多只有两个子节点
其实，二叉树的每个左右子节点仍是一颗二叉树，因此，我们可以使用递归的方式来定义二叉树，二叉树的实现代码如下

 public class BinaryTreeNode {
    
    private int data;  //数据
    private BinaryTreeNode leftChirld;  //左孩子
    private BinaryTreeNode rightChirld; //右孩子
    
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public BinaryTreeNode getLeftChirld() {
        return leftChirld;
    }
    public void setLeftChirld(BinaryTreeNode leftChirld) {
        this.leftChirld = leftChirld;
    }
    public BinaryTreeNode getRightChirld() {
        return rightChirld;
    }
    public void setRightChirld(BinaryTreeNode rightChirld) {
        this.rightChirld = rightChirld;
    }        
}  

这种实现方式称之为二叉树的左右链表表示法，如图所示

到此为止，二叉树的节点已经有了，接下来是对二叉树的操作，比如创建二叉树、添加元素、清空元素、遍历二叉树…
4.1 二叉树的创建
创建二叉树，一般有两种情况：初始化一个根节点或者初始化一棵空二叉树。代码如下：

 public class BinaryTree {
    private BinaryTreeNode  root ;
    
    //初始化二叉树
    public BinaryTree(){}
    
    public BinaryTree(BinaryTreeNode root){
        this.root = root;
    }
    
    public void setRoot(BinaryTreeNode root){
        this.root = root;
    }
    
    public BinaryTreeNode getRoot(){
        return root;
    }
}  

4.2 二叉树的清空
对于二叉树的清空，首先提供一个清空某个节点为根节点的子树的方法，即递归的删除每个节点；接着提供删除一个删除树的方法：

     /**
     * 二叉树的清空：
     * 首先提供一个清空以某个节点为根节点的子树的方法，既递归地删除每个节点；
     * 接着提供一个删除树的方法，直接通过第一种方法删除到根节点即可
     */    //清除某个子树的所有节点
    public void clear(BinaryTreeNode node){
        if(node!=null){
            clear(node.getLeftChirld());
            clear(node.getRightChirld());
            node = null; //删除节点
        }
    }
    //清空树
    public void clear(){
        clear(root);
    }  

4.3 判断二叉树是否为空
只需判断根节点是否存在即可：

     //判断二叉树是否为空
    public boolean isEmpty(){
        return root == null;
    }  

4.4 求二叉树的高度
思路：首先需要一种获取以某个节点为子树的高度方法，使用递归实现。如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；如果不为空，则遍历地比较它的左右子树高度，高的一个为这颗子树的最大高度，然后加上自身的高度即可

     /**
     * 求二叉树的高度：
     * 首先要一种获取以某个节点为子树的高度的方法，使用递归调用。
     * 如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；
     * 如果不为空，那么我们要遍历地比较它的左子树高度和右子树高度，
     *     高的一个为这个子树的最大高度，然后加上自己本身的高度就是了
     * 获取二叉树的高度，只需要调用第一种方法，即传入根节点
     */    
    //获取二叉树的高度
    public int heigh(){
        return heigh(root);
    }
    
    //获取以某节点为子树的高度
    public int heigh(BinaryTreeNode node){
        if(node==null){
            return 0; //递归结束，空子树高度为0
        }else{
            //递归获取左子树高度
            int l = heigh(node.getLeftChirld());
            //递归获取右子树高度
            int r = heigh(node.getRightChirld());
            //高度应该算更高的一边，（+1是因为要算上自身这一层）
            return l>r? (l+1):(r+1);
        }
    }  

4.5 求二叉树的节点数
思路：获取二叉树节点数，需要获取以某个节点为根的子树的节点数实现。
如果节点为空，则个数肯定为0；如果不为空，则算上这个节点之后，继续递归计算所有子树的节点数，全部相加即可

     /**
    * 获取二叉树的节点数
    */    public int size(){
        return size(root);
    }
    /**
     * 求二叉树的节点数：
     * 求节点数时，我们看看获取某个节点为子树的节点数的实现。
     * 首先节点为空，则个数肯定为0；
     * 如果不为空，那就算上这个节点之后继续递归所有左右子树的子节点数，
     *    全部相加就是以所给节点为根的子树的节点数
     * 如果求二叉树的节点数，则输入根节点即可
     */    
    public int size(BinaryTreeNode node){
        if(node==null){
            return 0;  //如果节点为空，则返回节点数为0
        }else{
            //计算本节点 所以要+1
            //递归获取左子树节点数和右子树节点数，最终相加
            return 1+size(node.getLeftChirld())+size(node.getRightChirld());
        }
    }  

4.6 返回某节点的父亲节点
思路：首先，同样需要通过一种方法来获取某个节点在某个子树中的父节点，这里使用递归实现，接着通过这种方法获取这个节点在二叉树中的父节点
事实上，以现有的这种二叉树的形式，我们并没有办法直接获取一个节点的父节点， 这里只能通过从根节点遍历来比较获取

     //node节点在subTree子树中的父节点
    public BinaryTreeNode getParent(BinaryTreeNode subTree,BinaryTreeNode node){
        if(subTree==null){
            return null;   //如果是空子树，则没有父节点
        }
        if(subTree.getLeftChirld()==node || subTree.getRightChirld() == node){
            return subTree;   //如果子树的根节点的左右孩子之一是待查节点，则返回子树的根节点
        }
        BinaryTreeNode parent = null;
        if(getParent(subTree.getLeftChirld(),node)!=null){
            parent = getParent(subTree.getLeftChirld(),node);
            return parent;
        }else{
            //递归左右子树
            return getParent(subTree.getRightChirld(),node);
        }
    }
    
    //查找node节点在二叉树中的父节点
    public BinaryTreeNode getParent(BinaryTreeNode node){
        return (root==null||root==node)? null:getParent(root,node);
    }  

4.7 返回左右子树
这个操作很简单，直接用节点的方法来获取即可

     //获取某个节点的左子树
    public BinaryTreeNode getleftTree(BinaryTreeNode node){
        return node.getLeftChirld();
    }
    
    //获取某个节点的右子树
    public BinaryTreeNode getrightTree(BinaryTreeNode node){
        return node.getRightChirld();
    }  

4.8 二叉树的插入
二叉树的插入分析：

  * 分两种情况：插入某个节点的左子节点；插入某个节点的右子节点
 * 值得指出的是，当这个节点本身有子节点时，这样的插入也会覆盖原来在这个位置上的节点。
 * 另外，虽然插入的是子节点，但是子节点也可以代表一颗子树。
 * 因为但从这个节点来看并不知道这个节点是否有左右子树存在，所以虽然插入的是一个节点，但有可能
 * 插入可很多节点（插入的是一颗子树）  

     //给某个节点插入左节点
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setLeftChirld(newnode);
    }
    //给某个节点插入右节点
    public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setRightChirld(newnode);
    }  

5、二叉树的遍历

二叉树的遍历是按照一定的规律来顺序遍历各二叉树节点，使得每个节点都会被访问且仅访问一次。通常二叉树的遍历根据根节点的遍历次序分为：先根遍历、中根遍历、后根遍历。

5.1 先根遍历(PreOrder)
若二叉树为空，则退出，否则进行下面操作

• 访问根节点
• 先根遍历左子树
• 先根遍历右子树
• 退出

按照先根遍历地方式，遍历如下二叉树，则访问顺序为：A、B、D、H、I、E、J、C、F、G

 public void PreOrder(BinaryTreeNode node){
if(node!=null){
          System.out.println(node.getData()); //先访问根节点
          PreOrder(node.getLeftChirld()); //先根遍历左子树
          PreOrder(node.getRightChirld()); //先根遍历右子树
}
}  

5.2 中根遍历(InOrder)
若二叉树为空，则退出，否则进行下面操作

• 中根遍历左子树
• 访问根节点
• 中根遍历右子树
• 退出

按照中根遍历地方式，遍历如下二叉树，则访问顺序为：H、D、I、B、J、E、A、F、C、G

 public void InOrder(BinaryTreeNode node){
if(node!=null){
InOrder(node.getLeftChirld()); //中根遍历左子树
              System.out.println(node); //访问根节点
              InOrder(node.getRightChirld()); //中根遍历右子树
       }
}  

5.3 后根遍历(PostOrder)
若二叉树为空，则退出，否则进行下面操作

• 后根遍历左子树
• 后根遍历右子树
• 访问根节点
• 退出

按照后根遍历地方式，遍历如下二叉树，则访问顺序为：H、I、D、J、E、B、F、G、C、A

 public void PostOrder(BinaryTreeNode node){
      if(node!=null){
      PostOrder(node.getLeftChirld()); //后根遍历左子树
      PostOrder(node.getRightChirld()); //后根遍历右子树
      System.out.println(node); //访问根节点
      }
}  

6.二叉树模板代码解决折纸问题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。 此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。

如果从纸条的下边向上方对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕，下折痕和上折痕。

给定一个输入参数N,代表纸条都从下边向上方连续对折N次。请从上到下打印所有的折痕的方向。

例如：N=1时，打印: down 。N=2时，打印：down down up

规律，大于一次后，每次折痕出现的位置都是在上次折痕的上方出现 凹 折痕，下方出现 凸 折痕。所以我们没必要构建这颗树，就可以用递归思维解决（即 ：参考二叉树递归遍历模板）

 对应的树结构按层输出为：
            1凹
    2凹             2凸
3凹     3凸     3凹     3凸  

  public static void printAllFolds(int N) {
        // 先从头结点出发，i初始值为1，切第一次的头结点折痕为凹折痕
printProcess(1, N, true);
}

// 递归过程，来到了某一个节点，
// i是节点的层数，N一共的层数，down == true  凹    down == false 凸
public static void printProcess(int i, int N, boolean down) {
if (i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "凹 " : "凸 ");
printProcess(i + 1, N, false);
}

public static void main(String[] args) {
int N = 3;
printAllFolds(N);
}  

7.常见的一些二叉树的应用场景

海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处， 在处理大批量的动态的数据是比较有用。

C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。

B-Tree，B+-Tree在文件系统中的目录应用。

路由器中的路由搜索引擎。