`
jaczhao
  • 浏览: 86806 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

java 二叉树遍历

阅读更多
package edu.cumt.jnotnull;  
  
import java.util.Stack;  
  
public class BinaryTree {  
    protected Node root;  
  
    public BinaryTree(Node root) {  
        this.root = root;  
    }  
  
    public Node getRoot() {  
        return root;  
    }  
  
    /** 构造树 */  
    public static Node init() {  
        Node a = new Node('A');  
        Node b = new Node('B', null, a);  
        Node c = new Node('C');  
        Node d = new Node('D', b, c);  
        Node e = new Node('E');  
        Node f = new Node('F', e, null);  
        Node g = new Node('G', null, f);  
        Node h = new Node('H', d, g);  
        return h;// root  
    }  
  
    /** 访问节点 */  
    public static void visit(Node p) {  
        System.out.print(p.getKey() + " ");  
    }  
  
    /** 递归实现前序遍历 */  
    protected static void preorder(Node p) {  
        if (p != null) {  
            visit(p);  
            preorder(p.getLeft());  
            preorder(p.getRight());  
        }  
    }  
  
    /** 递归实现中序遍历 */  
    protected static void inorder(Node p) {  
        if (p != null) {  
            inorder(p.getLeft());  
            visit(p);  
            inorder(p.getRight());  
        }  
    }  
  
    /** 递归实现后序遍历 */  
    protected static void postorder(Node p) {  
        if (p != null) {  
            postorder(p.getLeft());  
            postorder(p.getRight());  
            visit(p);  
        }  
    }  
  
    /** 非递归实现前序遍历 */  
    protected static void iterativePreorder(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        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());  
            }  
        }  
    }  
  
    /** 非递归实现前序遍历2 */  
    protected static void iterativePreorder2(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {//压入所有的左节点,压入前访问它  
                visit(node);  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {//  
                node = stack.pop();  
                node = node.getRight();  
            }  
        }  
    }  
  
    /** 非递归实现后序遍历 */  
    protected static void iterativePostorder(Node p) {  
        Node q = p;  
        Stack<Node> stack = new Stack<Node>();  
        while (p != null) {  
            // 左子树入栈  
            for (; p.getLeft() != null; p = p.getLeft())  
                stack.push(p);  
            // 当前节点无右子或右子已经输出  
            while (p != null && (p.getRight() == null || p.getRight() == q)) {  
                visit(p);  
                q = p;// 记录上一个已输出节点  
                if (stack.empty())  
                    return;  
                p = stack.pop();  
            }  
            // 处理右子  
            stack.push(p);  
            p = p.getRight();  
        }  
    }  
  
    /** 非递归实现后序遍历 双栈法 */  
    protected static void iterativePostorder2(Node p) {  
        Stack<Node> lstack = new Stack<Node>();  
        Stack<Node> rstack = new Stack<Node>();  
        Node node = p, right;  
        do {  
            while (node != null) {  
                right = node.getRight();  
                lstack.push(node);  
                rstack.push(right);  
                node = node.getLeft();  
            }  
            node = lstack.pop();  
            right = rstack.pop();  
            if (right == null) {  
                visit(node);  
            } else {  
                lstack.push(node);  
                rstack.push(null);  
            }  
            node = right;  
        } while (lstack.size() > 0 || rstack.size() > 0);  
    }  
  
    /** 非递归实现后序遍历 单栈法*/  
    protected static void iterativePostorder3(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p, prev = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {  
                Node temp = stack.peek().getRight();  
                if (temp == null || temp == prev) {  
                    node = stack.pop();  
                    visit(node);  
                    prev = node;  
                    node = null;  
                } else {  
                    node = temp;  
                }  
            }  
  
        }  
    }  
  
    /** 非递归实现后序遍历4 双栈法*/  
    protected static void iterativePostorder4(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Stack<Node> temp = new Stack<Node>();  
        Node node = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {  
                temp.push(node);  
                stack.push(node);  
                node = node.getRight();  
            }  
            if (stack.size() > 0) {  
                node = stack.pop();  
                node = node.getLeft();  
            }  
        }  
        while (temp.size() > 0) {  
            node = temp.pop();  
            visit(node);  
        }  
    }  
  
    /** 非递归实现中序遍历 */  
    protected static void iterativeInorder(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        while (p != null) {  
            while (p != null) {  
                if (p.getRight() != null)  
                    stack.push(p.getRight());// 当前节点右子入栈  
                stack.push(p);// 当前节点入栈  
                p = p.getLeft();  
            }  
            p = stack.pop();  
            while (!stack.empty() && p.getRight() == null) {  
                visit(p);  
                p = stack.pop();  
            }  
            visit(p);  
            if (!stack.empty())  
                p = stack.pop();  
            else  
                p = null;  
        }  
    }  
  
    /** 非递归实现中序遍历2 */  
    protected static void iterativeInorder2(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {  
                node = stack.pop();  
                visit(node);  
                node = node.getRight();  
            }  
        }  
    }  
  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        BinaryTree tree = new BinaryTree(init());  
        System.out.print(" Pre-Order:");  
        preorder(tree.getRoot());  
        System.out.println();  
        System.out.print("  In-Order:");  
        inorder(tree.getRoot());  
        System.out.println();  
        System.out.print("Post-Order:");  
        postorder(tree.getRoot());  
        System.out.println();  
        System.out.print(" Pre-Order:");  
        iterativePreorder(tree.getRoot());  
        System.out.println();  
        System.out.print("Pre-Order2:");  
        iterativePreorder2(tree.getRoot());  
        System.out.println();  
        System.out.print("  In-Order:");  
        iterativeInorder(tree.getRoot());  
        System.out.println();  
        System.out.print(" In-Order2:");  
        iterativeInorder2(tree.getRoot());  
        System.out.println();  
        System.out.print(" Post-Order:");  
        iterativePostorder(tree.getRoot());  
        System.out.println();  
        System.out.print("Post-Order2:");  
        iterativePostorder2(tree.getRoot());  
        System.out.println();  
        System.out.print("Post-Order3:");  
        iterativePostorder3(tree.getRoot());  
        System.out.println();  
        System.out.print("Post-Order4:");  
        iterativePostorder4(tree.getRoot());  
        System.out.println();  
  
    }  
  
}  

转自:http://robinsoncrusoe.iteye.com/blog/808526
分享到:
评论

相关推荐

    java二叉树遍历笔试题-InterviewBit-Solutions:Java中InterviewBit问题的解决方案

    java二叉树遍历笔试题 Java中InterviewBit问题的解决方案 编程 种类 递归 二叉搜索树 广度优先搜索 深度优先搜索 动态规划 贪婪的 图形 几何学 模拟 设计 大批 ID 标题 解决方案 时间 空间 困难 笔记 1 O(n*m) O(1) ...

    二叉树的遍历 java语言实现

    二叉树遍历是访问二叉树中所有节点的过程,通常有三种主要方法:前序遍历、中序遍历和后序遍历。这些遍历方式对于理解和操作二叉树数据结构至关重要。 1. **前序遍历**(Preorder Traversal): - 访问根节点。 -...

    二叉树的遍历-java

    在计算机科学中,二叉树遍历是访问树中所有节点的一种基本操作,通常有三种主要的遍历方式:前序遍历、中序遍历和后序遍历。这些遍历方法在数据结构和算法领域中有着广泛的应用,特别是在编译器设计、搜索算法和数据...

    Java二叉树中序遍历

    中序遍历是二叉树遍历的一种方法,它按照“左-根-右”的顺序访问树中的所有节点,对于理解树的性质和执行某些操作非常有用。本课程设计将详细介绍如何使用Java编程语言实现二叉树的中序遍历。 首先,我们先构建...

    二叉树遍历的算24程序

    java 写的算24程序。用两种二叉树遍历,并规整输出字符串

    java实现二叉树遍历demo

    本示例"java实现二叉树遍历demo"将通过一个简单的实例来演示这三种遍历方式。 1. **前序遍历**: 前序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。在代码实现中,通常采用递归的方法。首先访问根节点,然后递归地...

    Java版二叉树遍历非递归程序

    ### Java版二叉树遍历非递归程序详解 #### 一、引言 在计算机科学领域中,二叉树是一种常见的数据结构,其在算法设计、数据存储以及搜索等方面有着广泛的应用。对于二叉树的操作,遍历是其中非常重要的一项技术。...

    JAVA/Python实现二叉树遍历

    二叉树的遍历方式主要有四种:前序遍历、中序遍历、后序遍历和层次遍历。 前序遍历的顺序是:先访问根节点,然后访问左子树,最后访问右子树。前序遍历、中序遍历和后序...JAVA实现二叉树遍历 Python实现二叉树遍历

    二叉树遍历

    二叉树遍历的文档和代码示例(如`二叉树的遍历算法.doc`和`java二叉树遍历.doc`)通常会包含这些详细信息,帮助读者理解和实现这些遍历方法。 在实际应用中,二叉树遍历还可以结合其他算法,如深度优先搜索(DFS)...

    二叉树遍历 单步演示

    二叉树遍历是指按照特定顺序访问二叉树的所有节点,这一过程对于理解二叉树的结构和数据至关重要。在Java编程中,有三种主要的遍历方法:前序遍历、中序遍历和后序遍历。 1. **前序遍历**(根-左-右): - 首先...

    二叉树的非递归遍历方式(Java).md

    详细介绍了JAVA中二叉树的非递归遍历方式,三种方式都是采用栈来辅助完成,其中前序遍历采用的是先入右子节点再入左子节点的方法,这样弹出栈时左在前,右在后。中序遍历的话则是要先一直到达最左的子节点,然后才弹...

    二叉树遍历(c语言、python、java的实现).rar

    二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、...

    二叉树遍历.rar

    二叉树遍历是计算机科学中一种重要的数据结构操作,主要应用于处理和分析二叉树结构的数据。在数据结构第六章大作业中,你可能被要求深入理解和实现二叉树的遍历方法,这通常包括前序遍历、中序遍历和后序遍历。以下...

    队列实现二叉树遍历.rar

    在计算机科学中,二叉树是一种非常基础且重要的数据结构,它由节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。...理解并掌握二叉树遍历及其队列实现,对于提升算法能力和解决实际问题具有重要意义。

    java算法二叉树遍历源码文档.doc

    二叉树遍历在实际应用中有着广泛的应用,例如在文件系统中组织目录结构,搜索引擎的倒排索引,以及计算机科学中的许多算法实现,如二分查找、AVL树、红黑树等。理解并能够灵活运用这些遍历方法对于掌握数据结构和...

    java实现二叉树遍历算法(源代码)

    ### Java实现二叉树遍历算法详解 #### 一、引言 在计算机科学中,二叉树是一种常用的数据结构,广泛应用于各种算法和数据处理场景。为了更好地理解和操作二叉树,掌握其遍历算法至关重要。本文将详细介绍如何使用...

    二叉树遍历java代码.zip

    以上就是二叉树遍历的基本概念和Java实现,这些方法在处理二叉树数据结构时非常有用,例如在构建解析树、编译器设计、文件系统结构表示等方面都有应用。了解并熟练掌握这些遍历方法对于学习和解决与二叉树相关的编程...

    二叉树 层序遍历 java实现 课程设计

    除了代码实现,课程设计文档可能包含了二叉树的概念解释、层序遍历的算法描述、以及如何使用Java语言实现这一算法的详细步骤。同时,`课程设计.doc`可能包含项目报告,详细阐述了设计目的、实现方法、遇到的问题及...

Global site tag (gtag.js) - Google Analytics