JAVA递归、非递归遍历二叉树

本贴最后更新于 3243 天前,其中的信息可能已经时过境迁
import java.util.Stack;  
import java.util.HashMap;  
  
public class BinTree {  
    private char date;  
    private BinTree lchild;  
    private BinTree rchild;  
  
    public BinTree(char c) {  
        date = c;  
    }  
  
    // 先序遍历递归   
    public static void preOrder(BinTree t) {  
        if (t == null) {  
            return;  
        }  
        System.out.print(t.date);  
        preOrder(t.lchild);  
        preOrder(t.rchild);  
    }  
  
    // 中序遍历递归   
    public static void InOrder(BinTree t) {  
        if (t == null) {  
            return;  
        }  
        InOrder(t.lchild);  
        System.out.print(t.date);  
        InOrder(t.rchild);  
    }  
  
    // 后序遍历递归   
    public static void PostOrder(BinTree t) {  
        if (t == null) {  
            return;  
        }  
        PostOrder(t.lchild);  
        PostOrder(t.rchild);  
        System.out.print(t.date);  
    }  
  
    // 先序遍历非递归   
    public static void preOrder2(BinTree t) {  
        Stack<BinTree> s = new Stack<BinTree>();  
        while (t != null || !s.empty()) {  
            while (t != null) {  
                System.out.print(t.date);  
                s.push(t);  
                t = t.lchild;  
            }  
            if (!s.empty()) {  
                t = s.pop();  
                t = t.rchild;  
            }  
        }  
    }  
  
    // 中序遍历非递归   
    public static void InOrder2(BinTree t) {  
        Stack<BinTree> s = new Stack<BinTree>();  
        while (t != null || !s.empty()) {  
            while (t != null) {  
                s.push(t);  
                t = t.lchild;  
            }  
            if (!s.empty()) {  
                t = s.pop();  
                System.out.print(t.date);  
                t = t.rchild;  
            }  
        }  
    }  
  
    // 后序遍历非递归   
    public static void PostOrder2(BinTree t) {  
        Stack<BinTree> s = new Stack<BinTree>();  
        Stack<Integer> s2 = new Stack<Integer>();  
        Integer i = new Integer(1);  
        while (t != null || !s.empty()) {  
            while (t != null) {  
                s.push(t);  
                s2.push(new Integer(0));  
                t = t.lchild;  
            }  
            while (!s.empty() && s2.peek().equals(i)) {  
                s2.pop();  
                System.out.print(s.pop().date);  
            }  
  
            if (!s.empty()) {  
                s2.pop();  
                s2.push(new Integer(1));  
                t = s.peek();  
                t = t.rchild;  
            }  
        }  
    }  
  
    public static void main(String[] args) {  
        BinTree b1 = new BinTree('a');  
        BinTree b2 = new BinTree('b');  
        BinTree b3 = new BinTree('c');  
        BinTree b4 = new BinTree('d');  
        BinTree b5 = new BinTree('e');  
  
        /** 
         *      a  
         *     / / 
         *    b   c 
         *   / / 
         *  d   e 
         */  
        b1.lchild = b2;  
        b1.rchild = b3;  
        b2.lchild = b4;  
        b2.rchild = b5;  
  
        BinTree.preOrder(b1);  
        System.out.println();  
        BinTree.preOrder2(b1);  
        System.out.println();  
        BinTree.InOrder(b1);  
        System.out.println();  
        BinTree.InOrder2(b1);  
        System.out.println();  
        BinTree.PostOrder(b1);  
        System.out.println();  
        BinTree.PostOrder2(b1);  
    }  
}  
 
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3194 引用 • 8214 回帖
  • bintree
    1 引用
  • null
    8 引用 • 37 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    57 引用 • 25 回帖 • 8 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 79 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    9416 引用 • 42896 回帖 • 110 关注
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖
  • 自由行
    2 关注
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 157 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖 • 1 关注
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1063 引用 • 3455 回帖 • 165 关注
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 441 关注
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖 • 2 关注
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    132 引用 • 796 回帖
  • Access
    1 引用 • 3 回帖 • 4 关注
  • OneNote
    1 引用 • 3 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    729 引用 • 1278 回帖
  • Visio
    1 引用 • 2 回帖
  • Docker

    Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的操作系统上。容器完全使用沙箱机制,几乎没有性能开销,可以很容易地在机器和数据中心中运行。

    494 引用 • 928 回帖
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    31 引用 • 108 回帖
  • 音乐

    你听到信仰的声音了么?

    62 引用 • 512 回帖
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 494 关注
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 382 关注
  • WordPress

    WordPress 是一个使用 PHP 语言开发的博客平台,用户可以在支持 PHP 和 MySQL 数据库的服务器上架设自己的博客。也可以把 WordPress 当作一个内容管理系统(CMS)来使用。WordPress 是一个免费的开源项目,在 GNU 通用公共许可证(GPLv2)下授权发布。

    66 引用 • 114 回帖 • 200 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 638 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    171 引用 • 3842 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    586 引用 • 3538 回帖