二叉树的三种遍历方式java实现-蒲公英云

二叉树的三种遍历方式java实现

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
1．先（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴ 访问根结点；

⑵ 遍历左子树；

⑶ 遍历右子树。

2．中（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵访问根结点；

⑶遍历右子树。

3．后（根）序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵遍历右子树；

⑶访问根结点。

package com.ruicai.test;
/**
 * @author dsx
 */
public class BinaryTree {
    private BinaryTree data;    //父亲节点
    private BinaryTree left;//左孩子
    private BinaryTree right;//右孩子
    public BinaryTree(){
        //无参构造
    }
    public BinaryTree getData() {
        return data;
    }
    public void setData(BinaryTree data) {
        this.data = data;
    }
    public BinaryTree getLeft() {
        return left;
    }
    public void setLeft(BinaryTree left) {
        this.left = left;
    }
    public BinaryTree getRight() {
        return right;
    }
    public void setRight(BinaryTree right) {
        this.right = right;
    }
    public BinaryTree(BinaryTree data,BinaryTree left,BinaryTree right){
        this.data=data;
        this.left=left;
        this.right=right;
    }
    /**
     * 前序遍历 ，递归方式 
     * @param root:给出根节点
     */
    public void preOrder(BinaryTree root){
        if(root!=null){
            System.out.println(root.getData());
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }
    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(BinaryTree root){
        if(root!=null){
            inOrder(root.getLeft());
            System.out.println(root.getData());
            inOrder(root.getLeft());
        }
    }
    /**
     * 后序遍历
     * @param root
     */
    public void postOrder(BinaryTree root){
        if(root!=null){
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.println(root.getData());
        }
    }
}