返回顶部

收藏

树的深度优先遍历和广度优先遍历的原理和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

收藏

0人收藏

支持

1

反对

0

相关聚客文章
  1. 博主 发表 2013-01-23 07:22:22 快速排序算法——引自java编程思想
  2. 赵 伊凡 发表 2016-10-29 08:08:06 Java中生成随机数Random、ThreadLocalRandom、SecureRandom
  3. 博主 发表 2016-08-19 04:16:14 RSA 加密解密算法 Java 实现
  4. 0X55AA 发表 2016-10-31 10:49:17 使用druid解析sql
  5. 博主 发表 2014-11-26 10:08:46 Morris二叉树遍历算法
  6. 荔枝壳 发表 2013-12-11 14:48:38 Huffman 编码算法之 Java 实现
  7. 赵 伊凡 发表 2016-09-02 10:16:18 《轻松学算法——互联网算法面试宝典》你问问题我送书
  8. 0X55AA 发表 2014-12-31 03:33:26 osx上安装Android开发环境
  9. Eric 发表 2015-10-01 01:56:30 Java程序员必知的8大排序算法
  10. 春春 发表 2016-05-05 15:44:03 协同过滤算法-Java
  11. Chen Zhidong 发表 2012-03-04 15:38:05 Android手机短信SMSC算法
  12. 博主 发表 2016-12-02 17:27:36 最大子序列问题

评论

  • {0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0}二叉树的数组表示法为什么前面有个0

    回复   |   有痣 发表于 2017-11-04 14:19:43

发表评论