一，什么是二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作”左子树”（left subtree）和”右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

• 分为链式和顺序储存结构

• 顺序储存结构
  

• 链式结点
  

二，递归实现

2.1 结点类描述

package com.lovely.binarytree; /**  *   * @author echo lovely  *  * 2020年6月13日下午4:20:41  *   * 二叉链式存储结构的结点类描述  */ public class BiTreeNode { public Object data; // 存放结点的数据值 public BiTreeNode lchild, rchild; // 存放节点的左右孩子地址 public BiTreeNode() { this(null, null, null); } public BiTreeNode(Object data) { this(data, null, null); } public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) { this.data = data; this.lchild = lchild; this.rchild = rchild; } } 

2.2 三种递归

package com.lovely.binarytree; import java.util.LinkedList; /**  *   * @author echo lovely  *   * 2020年6月13日下午4:34:53  *   * 二叉树的三种遍历方式  *   * 1. 层次遍历  *  自上而下，自左至右  *   * 2. 先序遍历  *  先访问根节点，在先序遍历左子树，最后先序遍历右子树  *   * 3. 中序遍历  *  先中序遍历左子树，再访问根结点，最后中序遍历右子树  *    * 4. 后序遍历  *  先后遍历左子树，再后遍历右子树，最后访问根结点  */ public class EachTree { // 层次遍历 public void order(BiTreeNode root) { if (root == null) return;      LinkedList<BiTreeNode> queue = new LinkedList<BiTreeNode>();   BiTreeNode current = null; // 根结点入队   queue.offer(root); while (!queue.isEmpty()) { // 出队     current = queue.poll();           System.out.println(current.data); if (current.lchild != null) // 如果当前节点的左节点不为空 入队     queue.offer(current.lchild); if (current.rchild != null)     queue.offer(current.rchild); } } // 先序遍历 public void preOrder(BiTreeNode root) { if (root != null) {    System.out.println(root.data); // 根 preOrder(root.lchild); // 左子树 preOrder(root.rchild); // 右子树 } } // 中序遍历 public void inOrder(BiTreeNode root) { if (root != null) { inOrder(root.lchild); // 左子树    System.out.println(root.data); // 根 inOrder(root.rchild); // 右子树   } } // 后序遍历 public void postOrder(BiTreeNode root) { if (root != null) { postOrder(root.lchild); // 左子树 postOrder(root.rchild); // 有子树    System.out.println(root.data); // 根结点 } } } 

2.2 测试

package com.lovely.binarytree; /**  *   * @author echo lovely  * 2020年6月13日下午5:54:26  *   * 测试  */ public class TestEachTree { public static void main(String[] args) {      EachTree et = new EachTree(); // 左子树   BiTreeNode lchild = new BiTreeNode("lchild", new BiTreeNode("1", null, null), new BiTreeNode("2", null, null)); // 右子树   BiTreeNode rchild = new BiTreeNode("rchild", new BiTreeNode("3", null, null), new BiTreeNode("4", null, null)); // 根结点   BiTreeNode root = new BiTreeNode("data", lchild, rchild);   System.out.println("先序遍历=====");   et.preOrder(root);      System.out.println("中序遍历=====");   et.inOrder(root);      System.out.println("后序遍历=====");   et.postOrder(root);      System.out.println("层次遍历=====");   et.order(root); } } /** 先序遍历===== data lchild 1 2 rchild 3 4 中序遍历===== 1 lchild 2 data 3 rchild 4 后序遍历===== 1 2 lchild 3 4 rchild data 层次遍历===== data lchild rchild 1 2 3 4  */