快速业务通道

Java实现二叉树的递归与非递归遍历 - 编程入门网

作者 佚名技术 来源 NET编程 浏览 发布时间 2012-06-17

Java实现二叉树的递归与非递归遍历

时间:2011-04-13 zhangjunhd

构造树如下:

Java实现二叉树的递归与非递归遍历 - 编程入门网

其中二叉树节点类

/** 二叉树节点 */ public class BTNode {    private char key;    private BTNode left, right;    public BTNode(char key) {      this(key, null, null);    }    public BTNode(char key, BTNode left, BTNode right) {      this.key = key;      this.left = left;      this.right = right;    }    public char getKey() {      return key;    }    public void setKey(char key) {      this.key = key;    }    public BTNode getLeft() {      return left;    }    public void setLeft(BTNode left) {      this.left = left;    }    public BTNode getRight() {      return right;    }    public void setRight(BTNode right) {      this.right = right;    } }

Java实现二叉树的递归与非递归遍历(2)

时间:2011-04-13 zhangjunhd

遍历二叉树

/** 二叉树遍历 */ public class BinTree {    protected BTNode root;    public BinTree(BTNode root) {      this.root = root;    }    public BTNode getRoot() {      return root;    }    /** 构造树 */    public static BTNode init() {      BTNode a = new BTNode(''A'');      BTNode b = new BTNode(''B'', null, a);      BTNode c = new BTNode(''C'');      BTNode d = new BTNode(''D'', b, c);      BTNode e = new BTNode(''E'');      BTNode f = new BTNode(''F'', e, null);      BTNode g = new BTNode(''G'', null, f);      BTNode h = new BTNode(''H'', d, g);      return h;// root    }    /** 访问节点 */    public static void visit(BTNode p) {      System.out.print(p.getKey() + " ");    }    /** 递归实现前序遍历 */    protected static void preorder(BTNode p) {      if (p != null) {        visit(p);        preorder(p.getLeft());        preorder(p.getRight());      }    }    /** 递归实现中序遍历 */    protected static void inorder(BTNode p) {      if (p != null) {        inorder(p.getLeft());        visit(p);        inorder(p.getRight());      }    }    /** 递归实现后序遍历 */    protected static void postorder(BTNode p) {      if (p != null) {        postorder(p.getLeft());        postorder(p.getRight());        visit(p);      }    }    /** 非递归实现前序遍历 */    protected static void iterativePreorder(BTNode p) {      Stack<BTNode> stack = new Stack<BTNode>();      if (p != null) {        stack.push(p);        while (!stack.empty()) {          p = stack.pop();          visit(p);          if (p.getRight() != null)            stack.push(p.getRight());          if (p.getLeft() != null)            stack.push(p.getLeft());        }      }    }    /** 非递归实现后序遍历 */    protected static void iterativePostorder(BTNode p) {      BTNode q = p;      Stack<BTNode> stack = new Stack<BTNod

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务,公司网站:http://www.lingzhong.cn 为了给广大客户了解更多的技术信息,本技术文章收集来源于网络,凌众科技尊重文章作者的版权,如果有涉及你的版权有必要删除你的文章,请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号