前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树的非递归遍历

二叉树的非递归遍历

作者头像
晚上没宵夜
发布2020-05-08 15:00:03
6350
发布2020-05-08 15:00:03
举报
文章被收录于专栏:Howl同学的学习笔记

1. 递归实现

先序

代码语言:javascript
复制
public void preOrder(){
    preOrder(root);
}
private void preOrder(Node node){
    if(node != null){
        System.out.println(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }
}

中序

代码语言:javascript
复制
public void midOrder(){
    midOrder(root);
}
private void midOrder(Node node){
    if(node != null){
        midOrder(node.left);
        System.out.println(node.value);
        midOrder(node.right);
    }
}

后序

代码语言:javascript
复制
public void postOrder(){
    postOrder(root);
}
private void postOrder(Node node){
    if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.value);
    }
}

2. 非递归

前序

代码语言:javascript
复制
public void preOrderNew(){
    preOrderNew(root);
}
private void preOrderNew(Node node){
    if(node != null){
        LinkedList<Node> list = new LinkedList();
        list.addFirst(node);

        while(!list.isEmpty()){
            Node temp = (Node) list.removeFirst();
            if(temp.right != null){
                list.addFirst(temp.right);
            }
            if(temp.left != null){
                list.addFirst(temp.left);
            }
            System.out.println(temp.value);
        }
    }
}

中序

代码语言:javascript
复制
public void midOrderNew(){
    midOrderNew(root);
}
private void midOrderNew(Node node){
    LinkedList<Node> list = new LinkedList();
    while(!list.isEmpty() || node != null){
        if(node != null){
            list.addFirst(node);
            node = node.left;
        }else{
            node = list.removeFirst();
            System.out.println(node.value);
            node = node.right;
        }
    }
}

后序

代码语言:javascript
复制
public void postOrderNew(){
    postOrderNew(root);
}
private void postOrderNew(Node node){
    if(node != null){
        LinkedList<Node> list1 = new LinkedList();
        LinkedList<Node> list2 = new LinkedList();
        list1.addFirst(node);

        while(!list1.isEmpty()){
            Node temp = list1.removeFirst();
            list2.addFirst(temp);
            if(temp.left != null){
                list1.addFirst(temp.left);
            }
            if(temp.right != null){
                list1.addFirst(temp.right);
            }
        }
        while(!list2.isEmpty()){
            Node temp = list2.removeFirst();
            System.out.println(temp.value);
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-05-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 递归实现
    • 先序
      • 中序
        • 后序
        • 2. 非递归
          • 前序
            • 中序
              • 后序
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档