`

java 遍历二叉树

阅读更多

import java.util.ArrayDeque;

public class BinaryTree {
    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value){
            this.value=value;
        }
    }

    TreeNode root;

    public BinaryTree(int[] array){
        root=makeBinaryTreeByArray(array,1);
    }

    /**
     * 采用递归的方式创建一颗二叉树
     * 传入的是二叉树的数组表示法
     * 构造后是二叉树的二叉链表表示法
     */
    public static TreeNode makeBinaryTreeByArray(int[] array,int index){
        if(index<array.length){
            int value=array[index];
            if(value!=0){
                TreeNode t=new TreeNode(value);
                array[index]=0;
                t.left=makeBinaryTreeByArray(array,index*2);
                t.right=makeBinaryTreeByArray(array,index*2+1);
                return t;
            }
        }
        return null;
    }

    /**
     * 深度优先遍历,相当于先根遍历
     * 采用非递归实现
     * 需要辅助数据结构:栈
     */
    public void depthOrderTraversal(){
        if(root==null){
            System.out.println("empty tree");
            return;
        }       
        ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
        stack.push(root);       
        while(stack.isEmpty()==false){
            TreeNode node=stack.pop();
            System.out.print(node.value+"    ");
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }           
        }
        System.out.print("\n");
    }

    /**
     * 广度优先遍历
     * 采用非递归实现
     * 需要辅助数据结构:队列
     */
    public void levelOrderTraversal(){
        if(root==null){
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
        queue.add(root);
        while(queue.isEmpty()==false){
            TreeNode node=queue.remove();
            System.out.print(node.value+"    ");
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        System.out.print("\n");
    }

    /**
     *                  13
     *                 /  \
     *               65    5
     *              /  \    \
     *             97  25   37
     *            /    /\   /
     *           22   4 28 32
     */
    public static void main(String[] args) {
        int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};
        BinaryTree tree=new BinaryTree(arr);
        tree.depthOrderTraversal();
        tree.levelOrderTraversal();
    }
}

分享到:
评论

相关推荐

    递归方式遍历二叉树

    java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...

    Java实现二叉树的遍历

    java实现二叉树非递归前序中序后序遍历

    采用欧拉路径遍历二叉树java

    该算法采用欧拉路径遍历二叉树,使用java语言实现的

    java 二叉树遍历

    Java 二叉树遍历 二叉树是一种重要的数据结构,在计算机科学中有广泛的应用。在 Java 语言中,二叉树的遍历是指从根结点开始,按照一定的顺序访问二叉树中的每个结点。下面将详细介绍 Java 二叉树遍历的知识点。 ...

    Java输出中序遍历二叉树代码

    附件是Java输出中序遍历二叉树代码,中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 reeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    Java二叉树中序遍历

    本课程设计将详细介绍如何使用Java编程语言实现二叉树的中序遍历。 首先,我们先构建二叉树的节点类(Node),它包含一个数据字段(data)以及指向左子节点(left)和右子节点(right)的引用: ```java public ...

    Java输出后序遍历二叉树的代码

    附件是Java输出后序遍历二叉树的代码,后序遍历的顺序是:首先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。 TreeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    Java输出中序遍历二叉树的代码

    附件是Java输出中序遍历二叉树的代码,中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 TreeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    遍历二叉树(java实现)

    二叉树遍历是一种访问二叉树所有节点的方法,通常分为三种主要类型:先序遍历、中序遍历和后序遍历。在Java编程语言中,我们可以使用递归或迭代的方式来实现这些遍历方法。 **先序遍历**(根-左-右)是最常见的遍历...

    Java输出先序遍历二叉树的代码

    附件是Java输出先序遍历二叉树的代码,先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 TreeNode 类定义了二叉树的节点,每个节点包含一个整数值 val 和指向左右子节点...

    Java实现二叉树的层次遍历

    * 层次遍历二叉树 */ public void levelOrderTraversal() { if (root == null) { System.out.println("树为空"); return; } Queue&lt;Node&gt; queue = new LinkedList(); queue.add(root); while (!queue....

    Java实现先序遍历二叉树

    在Java中,实现二叉树的先序遍历可以通过递归来完成。先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,包含数据域和指向左右子...

    遍历二叉树java代码

    在Java编程语言中,遍历二叉树是一种常见的操作,用于访问树结构中的所有节点。二叉树有三种主要的遍历方式:前序遍历、中序遍历和后序遍历。以下是对这些遍历方法的详细解释,以及可能在`Tree.java`、`TestTree....

    二叉树递归中序遍历java

    java编程,二叉树的中序遍历,递归实现

    栈遍历二叉树

    java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树。

    先序遍历二叉树的非递归算法程序

    编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。

    java二叉树的前序+中序+后序遍历

    java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的

Global site tag (gtag.js) - Google Analytics