文档章节

树的深度优先与广度优先遍历

s
 sunsyu
发布于 2017/04/13 16:06
字数 389
阅读 13
收藏 0

原题出自百度的笔试:

简述树的深度优先及广度优先遍历算法,并说明非递归实现。
 

当时我看到这个题目的时候,已经完全记不得非递归算法该怎么实现了,后来查阅了一下,要用到两个辅助的数据结构:

深度优先遍历--->栈;

广度优先遍历--->队列;

这里以二叉树为例来实现。

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();  
    }  
}

© 著作权归作者所有

s
粉丝 0
博文 109
码字总数 135924
作品 0
深圳
私信 提问
数据结构-树以及深度、广度优先遍历(递归和非递归,python实现)

前面我们介绍了队列、堆栈、链表,你亲自动手实践了吗?今天我们来到了树的部分,树在数据结构中是非常重要的一部分,树的应用有很多很多,树的种类也有很多很多,今天我们就先来创建一个普通...

浩然haoran
07/18
0
0
python分布式爬虫搜索引擎实战-2-深度优先和广度优先

深度优先和广度优先 目录: 网站的树结构 深度优先算法和实现 广度优先算法和实现 网站url树结构: 分层设计 子域名: bogbole.com 环路链接: 从首页到下面节点。 但是下面的链接节点又会有链...

天涯明月笙
2017/03/26
0
0
PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

陈小龙哈
2018/06/26
0
0
Node中的两种遍历方式-深度优先和广度优先(附Node删除文件例子进行详解)

树的基本概念 树(Tree)是 个结点的有限集, 为 时,称为空树,在任意一棵非空树中有且仅有一个特定的被称为根(Root)的结点,当 大于 时,其余结点可分为 个互不相交的有限集 、、、,其中...

2018/09/14
0
0
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
13
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
38
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
40
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
61
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部