遍历二叉树(前序/中序/后序)

一:遍历树

遍历树是根据一个特定的顺序访问数的每一个节点,根据顺序的不同又可以分为 前序 , 中序 , 后序

二:前序遍历(可以实现排序)

1.访问根节点
2.前序遍历左子树
3.前序遍历右子树

三:中序遍历

1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

四:后序遍历

1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

五:代码实现

1.创建节点Node

public class Node {

    //数据项
    long data;
    //左子节点
    Node leftChild;
    //右子节点
    Node rightChild;

    //构造
    public Node(long value){
        this.data = value;
    }
}

2.遍历树

//遍历二叉树
public class Tree {
    //根节点
    public Node root;

    //插入节点
    public void insert(long value){
        //1.新建准备插入的节点
        Node newNode = new Node(value);
        //2.当前节点
        Node current = root;
        //3.父节点
        Node parent;

        //首次插入,根节点 = null
        if (root == null){
            root = newNode;
            return;
        }else{
            while (true){
                //非首次插入
                //父节点指向当前节点
                parent = current;
                //比较根节点和value的值大小
                if (current.data > value){
                    //根节点 > value , 向左走
                    current = current.leftChild;
                    //当走到叶子节点的时候
                    if (current == null){
                        //新节点插入 父节点的左子节点
                        parent.leftChild = newNode;
                        return;
                    }
                }else{
                    //向右走
                    current = current.rightChild;
                    //走到叶子节点
                    if (current == null){
                        //新节点插入 父节点的右子节点
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    //前序遍历
    //参数localNode 代表根节点
    public void frontOrder(Node localNode){
        if (localNode != null){
            //1.访问根节点
            System.out.println(localNode.data);
            //2.前序遍历左子树
            frontOrder(localNode.leftChild);
            //3.前序遍历右子树
            frontOrder(localNode.rightChild);
        }
    }

    //中序遍历
    //参数localNode 代表根节点
    public void inOrder(Node localNode){
        if (localNode != null){
            //1.中序遍历左子树
            inOrder(localNode.leftChild);
            //2.访问根节点
            System.out.println(localNode.data);
            //3.中序遍历右子树
            inOrder(localNode.rightChild);

        }
    }

    //后序遍历
    //参数localNode 代表根节点
    public void afterOrder(Node localNode){
        if (localNode != null){
            //1.后序遍历左子树
            afterOrder(localNode.leftChild);
            //2.后续遍历右子树
            afterOrder(localNode.rightChild);
            //3.访问根节点
            System.out.println(localNode.data);
        }
    }

}

3.测试树

public class Test {
    public static void main(String[] args) {

        Tree tree = new Tree();

        //插入数据
        tree.insert(8);
        tree.insert(3);
        tree.insert(6);
        tree.insert(10);
        tree.insert(1);
        tree.insert(9);
        tree.insert(100);

        //前序遍历
        tree.frontOrder(tree.root); // 8 3 1 6 10 9 100

        //中序遍历
        tree.inOrder(tree.root); // 1 3 6 8 9 10 100

        //后序遍历
        tree.afterOrder(tree.root); // 1 6 3 9 100 10 8
    }
}