本文共 6401 字，大约阅读时间需要 21 分钟。

什么是二叉树？

定义：二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。 那什么是遍历？ 遍历:所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 二叉树的遍历方式有以下几种： 1.前序遍历：先访问根节点——左子树——右子树。 2.中序遍历：先访问左子树——根节点——右子树，按照这个顺序。 3.后序遍历：和前面差不多，先访问树的左子树——右子树——根节点。按层遍历：把一棵树从上到下，从左到右依次写出来。 4.层序遍历：将二叉树的每一层分别遍历，直到最后的叶子节点被全部遍历完 现有二叉树如下，其通过各种遍历方式得到的遍历结果如下： 前序：0137849256 中序：7381940526 后序：7839415620 层序：0123456789 这里先介绍前，中，后三种遍历方式，最基本的实现方式就是通过递归实现： 首先编写一个TreeNode类，并添加一个构造二叉树的方法

package study.main.tree.binarytree;/** * @author : xiayj@jiedaibao.com * @date : 2019/10/31 20:47 */public class TreeNode{
       private int data;    private TreeNode leftNode;    private TreeNode rightNode;    public TreeNode(int data){
           this.data = data;    }    public void setData(int data){
           this.data = data;    }    public int getData(){
           return this.data;    }    public void setLeftNode(TreeNode node){
           this.leftNode = node;    }    public TreeNode getLeftNode(){
           return this.leftNode;    }    public void setRightNode(TreeNode node){
           this.rightNode = node;    }    public TreeNode getRightNode(){
           return this.rightNode;    }    /**     * 构造二叉树     * @return TreeNode     */    public TreeNode getTree(){
           TreeNode[] nodes = new TreeNode[10];        for (int i = 0;i < nodes.length;i++){
               nodes[i] = new TreeNode(i);        }        nodes[0].leftNode = nodes[1];        nodes[0].rightNode = nodes[2];        nodes[1].leftNode = nodes[3];        nodes[1].rightNode = nodes[4];        nodes[2].leftNode = nodes[5];        nodes[2].rightNode = nodes[6];        nodes[3].leftNode = nodes[7];        nodes[3].rightNode = nodes[8];        nodes[4].leftNode = nodes[9];        return nodes[0];    }}

编写实现类

package study.main.tree.binarytree;/** * @author : xiayj@jiedaibao.com * @date : 2019/10/31 20:47 */public class BinaryTree{
       public static void main(String[] args){
           TreeNode treeNode = new TreeNode(10);        //生成初始二叉树        TreeNode node = treeNode.getTree();        BinaryTree binaryTree = new BinaryTree();        binaryTree.qianxu(node);        System.out.println("");        binaryTree.zhongxu(node);        System.out.println("");        binaryTree.houxu(node);        System.out.println(" ");    }    private void qianxu(TreeNode node){
           if (null == node){
               return;        }        System.out.print(node.getData()+" ");        qianxu(node.getLeftNode());        qianxu(node.getRightNode());    }    private void zhongxu(TreeNode node){
           if (null == node){
               return;        }        zhongxu(node.getLeftNode());        System.out.print(node.getData()+" ");        zhongxu(node.getRightNode());    }    private void houxu(TreeNode node){
           if (null == node){
               return;        }        houxu(node.getLeftNode());        houxu(node.getRightNode());        System.out.print(node.getData()+" ");    }}

除了使用递归，还可以用java的栈stack来实现三种遍历方式

什么是栈？ 栈是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。特点：后进先出

package study.main.tree.binarytree;import java.util.Stack;/** * @author : xiayj@jiedaibao.com * @date : 2019/11/3 17:54 */public class BinaryTreeByStack {
       public static void main(String[] args){
           TreeNode treeNode = new TreeNode(10);        TreeNode node = treeNode.getTree();        BinaryTreeByStack binaryTreeByStack = new BinaryTreeByStack();        binaryTreeByStack.qianxu(node);        System.out.println(" ");        binaryTreeByStack.zhongxu(node);        System.out.println(" ");        binaryTreeByStack.houxu(node);    }    private void qianxu(TreeNode node){
           Stack
   
     stack = new Stack<>();        TreeNode root = node;        while (null != root || !stack.isEmpty()){
               if (null != root){
                   System.out.print(root.getData()+" ");                stack.push(root);                root = root.getLeftNode();            } else {
                   root = stack.pop().getRightNode();            }        }    }    private void zhongxu(TreeNode node){
           Stack
    
      stack = new Stack<>();        TreeNode root = node;        while (null != root || !stack.isEmpty()){
               if (null != root){
                   stack.push(root);                root = root.getLeftNode();            } else {
                   root = stack.pop();                System.out.print(root.getData()+" ");                root = root.getRightNode();            }        }    }    private void houxu(TreeNode node){
           if (null == node) {
               return;        }        TreeNode root = node;        Stack
     
       stack = new Stack<>();        stack.push(root);        stack.push(root);        while (!stack.isEmpty()){
               root = stack.pop();            if (!stack.isEmpty() && root == stack.peek()){
                   if (null != root.getRightNode()){
                       stack.push(root.getRightNode());                    stack.push(root.getRightNode());                }                if (null != root.getLeftNode()){
                       stack.push(root.getLeftNode());                    stack.push(root.getLeftNode());                }            } else{
                   System.out.print(root.getData()+" ");            }        }    }}
     
    
   

讲完前，中，后三种遍历方式，这里再说一下层序遍历，它是最接近我们思维的一种遍历方式，这里用java的队列Queue来实现它

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。 LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

package study.main.tree.binarytree;import java.util.LinkedList;import java.util.Queue;/** * @author : xiayj@jiedaibao.com * @date : 2019/11/10 23:33 */public class BinaryTreeByQueue {
       public static void main(String[] args){
           TreeNode treeNode = new TreeNode(10);        //生成初始二叉树        TreeNode node = treeNode.getTree();        BinaryTreeByQueue binaryTree = new BinaryTreeByQueue();        binaryTree.cengxu(node);    }    private void cengxu(TreeNode node){
           if (null == node){
               return;        }        Queue
   
     queue = new LinkedList<>();        queue.offer(node);        while (!queue.isEmpty()){
               node = queue.poll();            if (null != node.getLeftNode()){
                   queue.offer(node.getLeftNode());            }            if (null != node.getRightNode()){
                   queue.offer(node.getRightNode());            }            System.out.print(node.getData()+" ");        }    }}
   

转载地址：http://lbpvn.baihongyu.com/