水平遍历二叉树 代码中包含前序、中序、后序和水平遍历四种

水平遍历二叉树要求一层一层从上往下从左往右遍历，例如：

上面二叉树的遍历顺序为：2、4、5、1、3

思路：利用队列先进先出的性质

1、将根节点放入队列

2、while循环队列，只要队列不为空，就取出第一个节点。获取数据

3、将第二步取出的节点的左子节点和右子节点分别放入队列

代码：

1、创建node节点

public class TreeNode {
    private double date;// 数据
    private TreeNode lNode;// 左子树
    private TreeNode rNode;// 右子树
    public TreeNode() {
        
    }
    public TreeNode(double data) {
        this.date = data;
    }
    public double getDate() {
        return date;
    }
    public void setDate(double date) {
        this.date = date;
    }
    public TreeNode getlNode() {
        return lNode;
    }
    public void setlNode(TreeNode lNode) {
        this.lNode = lNode;
    }
    public TreeNode getrNode() {
        return rNode;
    }
    public void setrNode(TreeNode rNode) {
        this.rNode = rNode;
    }
    
}

2、构造二叉树，并遍历，这里包含了，前序，中序，后序已经水平遍历

import java.util.LinkedList;
import java.util.List;

public class BinTree {
    private TreeNode rootNode;

    public void insertNode(double data) {
        TreeNode newNode = new TreeNode(data);
        if (rootNode == null) {
            rootNode = new TreeNode();
            rootNode.setDate(data);
        } else {
            TreeNode currentNode = rootNode;
            TreeNode parentNode = null;
            while (true) {
                parentNode = currentNode;
                if (data > currentNode.getDate()) {
                    currentNode = currentNode.getrNode();
                    if (currentNode == null) {
                        parentNode.setrNode(newNode);
                        return;
                    }
                } else {
                    currentNode = currentNode.getlNode();
                    if (currentNode == null) {
                        parentNode.setlNode(newNode);
                        return;
                    }
                }

            }

        }
    }

    /**
     * 前序遍历
     * 
     * @param treeNode
     */
    public void preErgodic(TreeNode treeNode) {
        System.out.println(treeNode.getDate());
        if (treeNode.getlNode() != null) {
            preErgodic(treeNode.getlNode());
        }
        if (treeNode.getrNode() != null) {
            preErgodic(treeNode.getrNode());
        }
    }

    /**
     * 中序遍历
     * 
     * @param treeNode
     */
    public void inErgodic(TreeNode treeNode) {
        if (treeNode.getlNode() != null) {
            inErgodic(treeNode.getlNode());
        }
        System.out.println(treeNode.getDate());
        if (treeNode.getrNode() != null) {
            inErgodic(treeNode.getrNode());
        }
    }

    /**
     * 后序遍历
     * 
     * @param treeNode
     */
    public void aftErgodis(TreeNode treeNode) {
        if (treeNode.getlNode() != null) {
            aftErgodis(treeNode.getlNode());
        }
        if (treeNode.getrNode() != null) {
            aftErgodis(treeNode.getrNode());
        }
        System.out.println(treeNode.getDate());
    }

    public TreeNode getRootNode() {
        return rootNode;
    }

    public void setRootNode(TreeNode rootNode) {
        this.rootNode = rootNode;
    }
    /**
     * 水平遍历
     * @param treeNode
     */
    public void horenzital(TreeNode treeNode) {
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(treeNode);
        while (list.size() > 0) {
            TreeNode currentNode = list.removeFirst();
            if (currentNode != null) {
                System.out.println(currentNode.getDate());
            }
            if (currentNode.getlNode() != null) {
                list.addLast(currentNode.getlNode());
            }
            if (currentNode.getrNode() != null) {
                list.addLast(currentNode.getrNode());
            }
        }
    }

}

 

测试代码：

public static void main(String[] args) {
        BinTree binTree = new BinTree();
        binTree.insertNode(23);
        binTree.insertNode(1);
        binTree.insertNode(29);
        binTree.insertNode(34);
        binTree.insertNode(22);
        binTree.insertNode(56);
        binTree.insertNode(15);
        binTree.insertNode(18);
        binTree.insertNode(46);
        binTree.insertNode(78);
        binTree.insertNode(26);
        binTree.horenzital(binTree.getRootNode());
    }

结果：