复习二叉树 层序遍历,前序遍历,中序遍历,后序遍历 java版本

摘要: 最近偶尔看看算法方面的东西,最基础的就是二叉树,因此自己心血来潮先构建一颗二叉树,然后按各种方式进行遍历

最近偶尔看看算法方面的东西,最基础的就是二叉树,因此自己心血来潮先构建一颗二叉树,然后按各种方式进行遍历。构造的二叉树样子如下:

public class MyNode {

   private String data;
   private MyNode left;
   private MyNode right;

   public MyNode() {

   }

   public MyNode(String data) {
       this.data = data;
   }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public MyNode getLeft() {
        return left;
    }

    public void setLeft(MyNode left) {
        this.left = left;
    }

    public MyNode getRight() {
        return right;
    }

    public void setRight(MyNode right) {
        this.right = right;
    }

    public static void main(String[] args) {
        MyNode rootNode = new MyNode("A");
        buildTree(rootNode);
        // 按层处理
        System.out.println("层序遍历");
        processNodeLayer(rootNode);
        System.out.println("\n");
        // 前序遍历
        System.out.println("前序遍历");
        preTraversal(rootNode);
        System.out.println("\n");

        System.out.println("中序遍历");
        middleTraversal(rootNode);
        System.out.println("\n");
    }

    /**
     *         A
     *       /   \
     *     B      C
     *    / \    / \
     *   D   E  X   Y
     *      / \
     *     F   G
     * 构造一个上面图形的树.
     *
     * @param node
     */
    public static void buildTree(MyNode node) {

        MyNode b = new MyNode("B");
        MyNode c = new MyNode("C");
        addChild(node, b, c);

        MyNode c1 = new MyNode("X");
        MyNode c2 = new MyNode("Y");
        addChild(c, c1, c2);

        MyNode d = new MyNode("D");
        MyNode e = new MyNode("E");
        addChild(b, d, e);

        MyNode f = new MyNode("F");
        MyNode g = new MyNode("G");
        addChild(e, f, g);
    }

    public static void addChild(MyNode node, MyNode left, MyNode right) {
        node.setLeft(left);
        node.setRight(right);
    }

    // 前序
    public static void preTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getData());
        preTraversal(node.getLeft());
        preTraversal(node.getRight());

    }

    // 中序
    public static void middleTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        middleTraversal(node.getLeft());
        System.out.print(node.getData());
        middleTraversal(node.getRight());


    }

    // 后序
    public static void postTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        postTraversal(node.getLeft());
        postTraversal(node.getRight());
        System.out.println(node.getData());

    }



    // 按层遍历二叉树.
    public static void processNodeLayer(MyNode node) {
        if (null == node) {
            return;
        }

        LinkedList s = new LinkedList();
        s.add(node);

        while(!s.isEmpty()) {
            MyNode tmpNode = (MyNode) s.poll();
            System.out.print(tmpNode.getData());

            MyNode left = tmpNode.getLeft();
            MyNode right = tmpNode.getRight();

            if (null != left) {
                s.add(left);
            }

            if (null != right) {
                s.add(right);
            }
        }
    }

}


运行结果如下,实现了各种遍历:

上一篇: 用原生js获取queryString里面的参数的值.
下一篇: 没有了

Avatar

yur 评论于: 2021-10-25

您想远离瘟疫和灾难吗?三退吧!
 评论 ( What Do You Think )
名称
邮箱
网址
评论
验证
   
 

 


  • 微信公众号

  • 我的微信

站点声明:

1、一号门博客CMS,由Python, MySQL, Nginx, Wsgi 强力驱动

2、部分文章或者资源来源于互联网, 有时候很难判断是否侵权, 若有侵权, 请联系邮箱:summer@yihaomen.com, 同时欢迎大家注册用户,主动发布无版权争议的 文章/资源.

3、鄂ICP备14001754号-3, 鄂公网安备 42280202422812号