精华内容
下载资源
问答
  • 树的层次遍历

    2019-10-02 17:19:24
    说到树的层次遍历,就应该提到... 可以说树层次遍历是广度优先遍历的一种直接应用吧,比较广度优先搜索是图形的一种搜索算法,图形是一种比较大的概念,但这个和深度优先齐名的算法,在树的层次遍历引用中,并没有...

           说到树的层次遍历,就应该提到广度优先搜索算法------广度优先搜索算法(Breadth-First-Search),又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索算法。

             可以说树层次遍历是广度优先遍历的一种直接应用吧,比较广度优先搜索是图形的一种搜索算法,图形是一种比较大的概念,但这个和深度优先齐名的算法,在树的层次遍历引用中,并没有那么复杂,或许是因为用在树的遍历,而非图吧。

           树的层次遍历,故名思议,在一棵树中,把节点从左往右,一层一层的,从上往下,遍历输出,这里要用到一种很重要的数据结构,队列,一提到队列,我们就要想到先进先进先,即为先进入队列元素,先接受处理,我们在日常生活中排队时,就是先到的人,先接受服务。

     

              理解好队列,可以很容易的解决树的层此遍历,步骤如下:

           1.首先将根节点放入队列中。
           2.当队列为非空时,循环执行步骤3到步骤5,否则执行6;
           3.出队列取得一个结点,访问该结点;
           4.若该结点的左子树为非空,则将该结点的左子树入队列;
           5.若该结点的右子树为非空,则将该结点的右子树入队列;
           6.结束。

    代码:

    /***************************************
    * 时间:2013年12月2日
    * author:lm
    * 内容:二叉树的层次遍历
    ***************************************/

    import java.util.ArrayDeque;
    import java.util.Queue;

    public class BinTree {
        private char date;
        private BinTree lchild;   //左孩子
        private BinTree rchild;   //右孩子
        
        private BinTree(char c ){
            date = c;
        }
       public static void BFSOrder(BinTree t)
        {
            if(t==null) return ;
            Queue<BinTree> queue = new ArrayDeque<BinTree>();    
            //队列小知识:使用offer和poll优于add和remove之处在于它们返回值可以判断成功与否,而不抛出异常
            queue.offer(t);              //进入队列
            while(!queue.isEmpty())
            {
                t=queue.poll();           //当前节点出队列
                System.out.print(t.date);
                if(t.lchild!=null)              //当前节点左孩子去排队,在前面哦
                    queue.offer(t.lchild);
                if(t.rchild!=null)            //右孩子排第二
                    queue.offer(t.rchild);    
            }
        }
        public static void main(String[] args) {
             BinTree b1 = new BinTree('a');
             BinTree b2 = new BinTree('b');
             BinTree b3 = new BinTree('c');
             BinTree b4 = new BinTree('d');
             BinTree b5 = new BinTree('e');
             BinTree b6 = new BinTree('f');
             BinTree b7 = new BinTree('g');
        
            /**
             *      a 
             *    /   \
             *   b     c
             *  / \   / \
             * d   e f   g
             */
            b1.lchild = b2;
            b1.rchild = b3;
            b2.lchild = b4;
            b2.rchild = b5;
            b3.lchild = b6;
            b3.rchild = b7;
    
            BinTree.BFSOrder(b1);
            System.out.println();    
            }
    }

    另外还写了树的三种深度优先遍历的递归与非递归算法:

    http://www.cnblogs.com/LZYY/p/3454778.html

    转载于:https://www.cnblogs.com/LZYY/p/3459718.html

    展开全文
  • 树的层次遍历【队列的应用

    千次阅读 2017-03-14 14:39:16
    树的层次遍历【队列的应用

    树的层次遍历【队列的应用】

    思想:将不空的根节点入队列,队列不空的时候出队列,访问该节点,然后分别将左右孩子入队列,正好先出左,再出右,跟队列契合。


    java实现代码;

    package com.mytest.mymain;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    class BTree{
    	public int value;  //public static int value;  那么最终输出都为8个8
    	public BTree left;  
    	public BTree right;  
    	BTree(int x) { value = x; }  
    }
    public class TraversalTree {
    	public static void main(String[] args) {
    		BTree root=new BTree(1);
    		BTree Node2=new BTree(2);
    		BTree Node3=new BTree(3);
    		BTree Node4=new BTree(4);
    		BTree Node5=new BTree(5);
    		BTree Node6=new BTree(6);
    		BTree Node7=new BTree(7);
    		BTree Node8=new BTree(8);
    	
    		root.left=Node2;
    		root.right=Node3;
    		
    		Node2.left=Node4;
    		Node2.right=Node5;
    		
    		Node3.left=Node6;
    		Node3.right=Node7;
    		
    		Node4.left=Node8;
    		
    		System.out.println("层次遍历");
    		levelorder(root);
    	}
    	//层次遍历
    	public static void levelorder(BTree root){
    		Queue<BTree> queue=new LinkedList<BTree>();
    		BTree bTree=null;
    		
    		if(root != null){
    			queue.add(root);
    		}
    		
    		while(!queue.isEmpty()){
    			bTree=queue.poll();
    			System.out.print(bTree.value+"  ");
    			if(bTree.left != null){
    				queue.add(bTree.left);
    			}
    			if(bTree.right !=null ){
    				queue.add(bTree.right);
    				
    			}
    		}
    		
    	}
    }


    展开全文
  • 栈的应用树的层次遍历、图的广度优先遍历、OS的FCFS策略树的层次遍历:图的广度优先遍历OS的FCFS策略: 树的层次遍历: 算法思想: 1、先遍历头节点1,头节点1入队 2、在遍历头节点的孩子节点23,让孩子节点23入队...

    栈的应用:树的层次遍历、图的广度优先遍历、OS的FCFS策略

    树的层次遍历:

    在这里插入图片描述算法思想:
    1、先遍历头节点1,头节点1入队
    2、在遍历头节点的孩子节点23,让孩子节点23入队,1节点出队
    3、在以2节点为父节点,让2节点的孩子节点45入队,2节点出队
    4、以此类推,直到遍历完整颗树为止
    在这里插入图片描述

    图的广度优先遍历

    在这里插入图片描述
    算法思想:
    1、1节点入队
    2、遍历与1相连节点,让其相邻节点入队,1节点出队
    3、在遍历此时队列的第一个节点,让其相邻且未扫描的节点入队,第一个节点出队
    4、以此类推,直到遍历完整个图为止

    在这里插入图片描述

    OS的FCFS策略:

    当多个进程抢占cpu资源时,先来先服务策略是常用策略
    在这里插入图片描述原理:
    1、多个进程要使用一个cpu时,采用一个等待队列
    2、当队头进程时间片到时,将队头进程出队插入队尾
    3、执行下一个队头进程
    4、重复23步骤

    展开全文
  • 树的遍历是一个基础问题,也有很多的实际应用,可以用来找到匹配的字符串、文本分词和文件路径等问题。 数的遍历有两个基本的方法:深度优先遍历和 广度优先遍历 。 深度优先遍历又根据处理节点的顺序不同,可以...

    --------转自 每日一道算法题  公众号

     

    树的遍历是一个基础问题,也有很多的实际应用,可以用来找到匹配的字符串、文本分词和文件路径等问题。

    数的遍历有两个基本的方法:深度优先遍历 和 广度优先遍历 。

     

    深度优先遍历又根据处理节点的顺序不同,可以分为:中序遍历、前序遍历和后序遍历。这些知识点也是深度优先遍历经常考察的。

    广度优先遍历的考察在于层次遍历,比如需要我们按照层次输出一棵树的所有节点的组合(LeetCode 107),比如求一棵树的最左节点(LeetCode 513).这些

    问题本质上都是考察的广度优先遍历。

     

    如下代码是经典的广度优先遍历实现的方式,使用了队列的FIFO的方式,将所有暂未访问的节点存入一个队列,依次遍历。

    queue = [node]  // 新建一个队列,并将根节点放入队列
    while queue.length != 0
        item = queue.shift   // 弹出队列的头部元素
        do_someting(item)  // 操作该节点:比如存入一个数组或者打印
        queue.push(item.left)  if item.left    // 将左子节点存入队列
        queue.push(item.right) if item.right  // 将右子节点存入队列

    但是只掌握了上面的遍历方法是不够的,层次遍历的难点在于 层次的比较 。也就是说,我们需要对不同层次的节点做 隔离 

     

    --------------------------------------------正文---------------------------------------------------------------------------------------------------------------------------------------------

    遍历技巧一: 数组长度做隔离

    思路:

    获取当前的队列的长度length,一次只遍历length个节点,后续加入的元素在下一次循环遍历。

    伪代码如下:

    1 queue =  [node]  // 新建一个队列,并将根节点放入队列
    2 while queue.lengh != 0
    3     length = queue.length //  获取当前队列的长度
    4     while length > 0        // 只弹出length 个节点
    5         item = queue.shift // 弹出队列的头部元素
    6         do_something(item)    //  操作该节点:比如存入一个数组或者打印
    7         queue.push(item.left)  if item.left  // 将左子节点存入队列
    8         queue.push(item.right) if item.right  // 将右子节点存入队列
    9         length--

    遍历技巧二:使用分隔符

    思路

    在不同的节点中间加入一个分隔符,遍历发哦分割几点的时候,停止当前遍历。

    伪代码如下:

    1 queue = [node]     // 新建一个队列,并将根节点放入到队列
    2 while queue.lengh != 0
    3     queue.push "$"    // 将分割符放入队列
    4     while(true)           // 做一个无限循环
    5            item = queue.shift   // 弹出队列的头部元素
    6            break if item == '$'   // 如果当前的节点等于分隔符,说明该层已经遍历到了最右边
    7            do_something(item)  //操作该节点
    8            queue.push(item.left)  if item.left // 将左子节点存入队列
    9            queue.push(item.right)  if item.right // 将右子节点存入队列

    遍历技巧三:使用深度优先搜索

    思路:

    用一个level字段来保存深度,在深度优先遍历的时候,判断一下当前结点的深度即可

    伪代码如下:

     1 ans = []  // 用一个数组来保存值
     2 level = 0 // 根节点的level 是0
     3 visit(node,ans,level)
     4 
     5 
     6 def visit(node,ans,level):
     7       return if node is null  // 如果节点为空,则返回
     8     //逻辑处理部分
     9     if ans.lengh > level   //说明之前访问过该层的节点
    10            ans.[level].push node.val
    11      else               //说明之前level没有访问过
    12            ans.[level] = [node.val]
    13 visit (node.left, level +,ans)
    14 visit (node.right, level +,ans)

    逻辑处理部分的代码还有一个需要注意的地方,比如LeetCode 107 需要求reverse后的结果,所以处理这一部分逻辑代码时,需要找到当前level对应的数组的position。

     

    总结

    树的难点在于树的构造,需要将一般性问题抽象成一棵树,需要定义好节点和路径。当我们构造好一棵树后,一般只需要遍历这棵树就能得到结果。所以树的遍历是一个基础问题。

    其中分层遍历的技巧比dfs/bfs更难点,需要有更强的逻辑思维能力。

     

    转载于:https://www.cnblogs.com/simplepaul/p/6721687.html

    展开全文
  • 解题思路:首先要根据输入字符串构建二叉树,然后利用BFS层次遍历二叉树,注意sscanf和BFS在二叉树遍历中的应用,尤其关注代码中注释!该代码并不完全,没有对非法二叉树输入进行处理。仅仅作为层次遍历的参考...
  • [树层次遍历的应用] 116. 117. 填充每个节点下一个右侧节点指针 I II (队列层次遍历、迭代) 116.填充每个节点下一个右侧节点指针(完美二叉树)思路1:队列层次遍历 + 找出每一层最后一个节点思路2:迭代 + ...
  • 数据结构-二叉树的非层次遍历以及应用(输出叶子结点,求树的高度)树的定义以树节点的堆栈和队列的结构堆栈的操作前序,中序,和后序的非递归遍历使用堆栈可以对二叉树进行层次遍历输出树的叶子结点求树的高度前序...
  • 是否可以把上结点编号,然后把二叉树存储在数组中呢?很遗憾如果结点在一条链上,那将是2^256个结点 所以需要采用动态结构 首先要读取结点,建立二叉树addnode()+read_input()承担这样工作 然后遍历...
  • 队列应用——树的层次遍历 1)根结点入队 2)若队空(所有结点都已处理完毕),则结束遍历;否则重复3操作 3)队列中第一个结点出队,并访问之。若其有左孩子,则将左孩子入队;若其有右孩子,则将右孩子入队,返回...
  • 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], ...树的遍历方法一般分为两种:一种是广度优先遍历(BFS),一种...
  • //***************************************层次遍历的举例********************************************begin //创建二叉树利用先序创建 /* / \ 3 / \ / 5 6 / \ \ / \ 8 9 10 11 / \ 13 */ void...
  • 112. 路径总和 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 ...返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->...利用树的层次遍历(BFS),运用两个队列,一个放节点,一
  • 是经典的树的层次遍历的问题,但与之不同的是,需要记录一下每一层的节点个数,因为要分别用vector来存储 //这里用的是pair来存储节点和层数 class Solution { public: vector<vector<int>> levelOrder...
  • 层次遍历(level):借助队列实现 ,队列里面元素存放二叉树结点地址,队列需要用到... 二叉头文件:用于创建二叉树,层次遍历的实现 主函数中实现 控制应用平台效果 二叉树原型
  • 创建二叉树,遍历二叉树.详细介绍了层次遍历和后序遍历的应用. 层次遍历:树的高度,树的宽度,每一层节点个数等 后序遍历:根节点到某节点的路径,两个节点的最近公共祖先等.
  • 队列1前言1、 二叉树的层序遍历(102)2、二叉树的锯齿形层次遍历(103)3、二叉树的层次遍历II(107)4、二叉树的右视图(199) 前言 队列的基本知识 \quad \quad队列的基本应用: 1、广度优先遍历 :层序遍历 图...
  • 0.树结构 typedef struct BTNode { int data; struct BTNode *lchild;...1.层次遍历 void level(BTNode *p) { if(!p)//空树直接返回 return; BTNode *q;//遍历树的指针 BTNode *que[maxSize];//...
  •  第一类型的题目:树的层次遍历及拓展应用。  基础题:从上往下打印出二叉树的每个节点,同层节点从左至右打印。  public ArrayList PrintFromTopToBottom(TreeNode root) { // 所有结点的list ArrayList ...
  • 两个方法:①递归②层次遍历 2、解题分析 递归 如果左子树为空就直接遍历右子 如果右子为空就直接遍历左子树 如果都不为空,比较两个取最小值+1即可 遍历 BFS模板 使用一个临时变量去记录深度 ...
  • 问题描述:现有jstree包含左图中所有结点信息(包含区域结点和站点结点),需要做到输入站点名称模糊查询,显示查询子树结果如右图 解决策略:  1、先模糊查询所得站点所在区域结点A5,A6,A4,根据这些从下往上...
  • 层次遍历树的第四种遍历方式,使用队列,可以认为是广度优先搜索在树的应用。 目录 1.生成本文例子中的树 2.层次遍历方式-使用队列 3.完整代码 1.生成本文例子中的树 本文中创建的树如下: 其层次遍历...
  • 6-4 队列的典型应用 Binary Tree ... 二叉树的层次遍历 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / ...
  • 树的遍历

    2019-09-23 07:14:35
    应用树结构解决问题时,往往要求按照某种次序获得树中全部结点的信息,这种操作叫作树的遍历遍历的方法有多种,常用的有: A、先序(根)遍历:先访问根结点,再从左到右按照先序思想遍历 各棵子树。 ...
  • 006数据结构与算法Python树与树算法树的概念树的术语树的种类树的存储与表示常见的一些树的应用场景二叉树二叉树的基本概念二叉树的性质(特性)二叉树的节点表示以及树的创建二叉树的遍历深度优先遍历(先中后序遍历)...
  • 层次遍历: 先序遍历:根—>左—>右 中序遍历:左—>根—>右 后序遍历:左—>右—>根 完全二叉树的代码实现 树 树的定义 是一种抽象类型,或是实作这种抽象数据类型的数据结构,用来模拟...
  • luke_lin   博客园 首页 ...直观地,树型结构是以分支关系定义的层次结构。 在计算机领域中也有着广泛的应用,例如在编译程序中,用来表示源程序的语法结构;在数据库系统中,可用...
  • 二叉树的层次遍历: UVA - 122 Trees on the level 函数的应用: 指针代码: 数组代码: 动态二叉树结构体定义与生成新结构点: 指针: struct node{ bool have_value; int v; node *left,*right; ...
  • 树的层次遍历、前序遍历、中序遍历、后序遍历方式都需要我们非常熟悉的掌握,而对于像我这样的人来说,以前总是觉得树的遍历很简单,使用递归的方式几行代码就写完了,然后当要求使用非递归的方式进行前序中序后序遍...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 362
精华内容 144
关键字:

树的层次遍历应用