一、二叉树的遍历

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。

二叉树的遍历包括深度优先遍历和广度优先遍历。

二、深度优先遍历

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。

1、前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

步骤如下：

1、首先输出的是根节点1；

2、由于根节点1存在左孩子，输出左孩子节点2；

3、由于节点2也存在左孩子，输出左孩子节点4；

4、节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5；

5、节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的右孩子节点3；

6、节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6；

到此为止，所有的节点都遍历输出完毕。

2、中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

步骤如下：

1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不 再有左孩子 的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4；

2、依照中序遍历的次序，接下来输出节点4的父节点2；

3、再输出节点2的右孩子节点5；

4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1；

5、由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3；

6、最后输出节点3的右孩子节点6 到此为止，所有的节点都遍历输出完毕。

3、后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

步骤如下：

1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不 再有左孩子 的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4；

2、输出右节点5；

3、输出节点4的父节点2；

4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的右子树；

5、访问根节点的右孩子，如果这个右孩子拥有左孩子，则继续深入访问下去，一直找到不再有左 孩子 的节点，如果没有左孩子则找右孩子，并输出该节点6；

6、输出节点6的父节点3 到此为止，所有的节点都遍历输出完毕。

三、代码实现

public class TreeNode {    int data; //数据    TreeNode leftChild; //左孩子    TreeNode rightChild; //右孩子    TreeNode(int data) {        this.data = data;    }}

public class BinaryTree {    TreeNode root;    public void insertNode(int data){        root=insert(root,data);    }    private TreeNode insert(TreeNode node,int data){        //如果是空则插入第一个节点        if(node==null){            return new TreeNode(data);        }        //插左边        if(data<node.data){            node.leftChild=insert(node.leftChild,data);        }        //插右边        else if(data>node.data){            node.rightChild=insert(node.rightChild,data);        }        else{            node.data=data;        }        return node;    }    /*     * 前序遍历     */    public void preOrderTraveral(TreeNode node){        if(node == null){            return;        }        System.out.println(node.data);        preOrderTraveral(node.leftChild);        preOrderTraveral(node.rightChild);    }    /*     * 中序遍历     */    public void inOrderTraveral(TreeNode node){        if(node == null){            return;        }        inOrderTraveral(node.leftChild);        System.out.println(node.data);        inOrderTraveral(node.rightChild);    }    /*     * 后序遍历     */    public void postOrderTraveral(TreeNode node){        if(node == null){            return;        }        postOrderTraveral(node.leftChild);        postOrderTraveral(node.rightChild);        System.out.println(node.data);    }    public static void main(String[] args) {        BinaryTree btt=new BinaryTree();        btt.insertNode(10);        btt.insertNode(8);        btt.insertNode(11);        btt.insertNode(7);        btt.insertNode(9);        btt.insertNode(12);        btt.preOrderTraveral(btt.root);        System.out.println("========================");        btt.inOrderTraveral(btt.root);        System.out.println("========================");        btt.postOrderTraveral(btt.root);    }}