精华内容
下载资源
问答
  • 层序遍历二叉树

    2013-04-01 22:49:44
    采用二叉链表存储结构,Visit是对数据元素操作的应用函数。*/ /* 层序遍历二叉树T算法(利用队列),对每个数据元素调用函数Visi
  • 此题即是层序遍历二叉树,引入队列,先将根节点入队,接着循环执行出队操作,每出队一个节点,就将其放入列表,同时将该节点的左孩子和右孩子入队。直到队列为空为止。 代码 import java.util.ArrayList; /** public...

    题目

    从上往下打印出二叉树的每个节点,同层节点从左至右打印。

    分析

    此题即是层序遍历二叉树,引入队列,先将根节点入队,接着循环执行出队操作,每出队一个节点,就将其放入列表,同时将该节点的左孩子和右孩子入队。直到队列为空为止。

    代码

    import java.util.ArrayList;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            //层序遍历,引入队列(这里的队列用ArrayList实现)
            ArrayList<Integer> list = new ArrayList<>();
            if(root == null){
                return list;
            }
            ArrayList<TreeNode> queue = new ArrayList<>();
            queue.add(root); //先把根节点放入队列
            while(!queue.isEmpty()){
                TreeNode tree = queue.remove(0);  //出队
                list.add(tree.val);
                if(tree.left != null){
                    queue.add(tree.left);  //左孩子入队
                }
                if(tree.right != null){
                    queue.add(tree.right);  //右孩子入队
                }
            }
            return list;
        }
    }
    

    运行结果

    在这里插入图片描述

    展开全文
  • 经典算法学习——层序遍历二叉树

    千次阅读 2016-10-01 17:16:44
    今天我们来对二叉树进行层序遍历层序遍历的时候需要借助另一种数据结构——队列。本篇的示例代码上传至 https://github.com/chenyufeng1991/LevelOrderBinaryTree 。 层序遍历的基本思路是,当访问到一个节点的...

           我们可以用很多方式去遍历一颗二叉树,比如先序遍历,中序遍历,后序遍历,其实都是通过递归的来实现。今天我们来对二叉树进行层序遍历,层序遍历的时候需要借助另一种数据结构——队列。本篇的示例代码上传至 https://github.com/chenyufeng1991/LevelOrderBinaryTree 。

           层序遍历的基本思路是,当访问到一个节点的时候,把它放入队列,然后访问该值,同时把该节点的左右孩子节点放入队列,出队列该节点。其中需要注意的是,如果某个节点已经是叶子节点了,则不需要把它的左右孩子节点(虽然它没有左右孩子)放入队列。因为把一个空的节点push进队列会造成bug。同样的,如果它只有左孩子或者只有右孩子,也是同样的处理。递归结束的条件是当队列为空时结束。

    核心代码如下:

    //层序遍历
    void LevelOrder(queue<Node *> &nodeQueue)
    {
        if (nodeQueue.empty())
        {
            return;
        }
    
        Node *frontNode = nodeQueue.front();
        cout << frontNode->element << " ";
        nodeQueue.pop();
        if (frontNode->lChild != NULL)
        {
            nodeQueue.push(frontNode->lChild);
        }
        if (frontNode->rChild != NULL)
        {
            nodeQueue.push(frontNode->rChild);
        }
    
        LevelOrder(nodeQueue);
    }


    展开全文
  • 剑指offer32-1 从上到下打印二叉树(层序遍历二叉树

    问题描述

    从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

    思路

    使用一个队列。

    代码

    class Solution {
        public int[] levelOrder(TreeNode root) {
            if(root == null) return new int[0];
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            ArrayList<Integer> list = new ArrayList<>();
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                list.add(node.val);
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < res.length; ++i) {
                res[i] = list.get(i);
            }
            return res;
        }
    }
    
    展开全文
  • 算法思想:使用队列来实现二叉树的层序遍历。先将根结点放入队列中,然后每次都从队列中取出一个结点打印该结点值,若这个结点有子结点,则将它的子结点放入队列尾... * 如何层序遍历二叉树? */ //定义结点结构 cl...

    算法思想:使用队列来实现二叉树的层序遍历。先将根结点放入队列中,然后每次都从队列中取出一个结点打印该结点值,若这个结点有子结点,则将它的子结点放入队列尾,直到队列为空。

    代码如下:

    package com.haobi;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /*
     * 如何层序遍历二叉树?
     */
    //定义结点结构
    class Node{
    	public int data;
    	public Node left;
    	public Node right;
    	public Node(int data) {
    		this.data = data;
    		this.left = null;
    		this.right = null;
    	}
    }
    
    public class Test2 {
    	//定义根结点
    	private Node root;
    	//构造方法
    	public Test2() {
    		root = null;
    	}
    		
    	/**
    	 * 将data插入到二叉排序树中
    	 * @param data
    	 */
    	public void insert(int data) {
    		//创建新的结点
    		Node newNode = new Node(data);
    		//如果树为空
    		if(root==null) {
    			//则新结点即根结点
    			root = newNode;
    		}else {//如果树不为空
    			//定义current指向root结点(current表示当前结点)
    			Node current = root;
    			//定义parent结点(即要插入结点的父结点)
    			Node parent;
    			//寻找插入位置
    			while(true) {
    				//current指向root再赋给parent,表示从根结点开始查找
    				parent = current;
    				if(data<current.data) {//要插入的数据小于current(当前指向)的数据
    					current = current.left;
    					if(current == null) {
    						//找到插入位置并插入新结点
    						parent.left = newNode;
    						return;
    					}	
    				}else {//要插入的数据大于current(当前指向)的数据
    					current = current.right;
    					if(current == null) {
    						//找到插入位置并插入新结点
    						parent.right = newNode;
    						return;
    					}
    				}
    			}
    		}	
    	}
    		
    	/**
    	 * 输入数据构建二叉树
    	 * @param data
    	 */
    	public void buildTree(int[] data) {
    		for(int i=0;i<data.length;i++) {
    			insert(data[i]);
    		}
    	}
    	
    	/**
    	 * 层序遍历二叉树
    	 */
    	public void layerTranverse(Node root) {
    		//判断树是否为空
    		if(root == null) {
    			return;
    		}
    		Queue<Node> q = new LinkedList<Node>();
    		q.add(root);
    		//如果q不为空
    		System.out.print("二叉树的层序遍历:");
    		while(!q.isEmpty()) {
    			Node n = q.poll();
    			System.out.print(n.data + " ");
    			if(n.left != null) {
    				q.add(n.left);
    			}
    			if(n.right != null) {
    				q.add(n.right);
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		Test2 tree = new Test2();
    		int[] data = {2,8,7,4,9,3,1,6,7,5};
    		//构建二叉树
    		tree.buildTree(data);
    		tree.layerTranverse(tree.root);
    	}
    }
    

    程序输出结果如下:

    二叉树的层序遍历:2 1 8 7 9 4 7 3 6 5 

    展开全文
  • 层序遍历意思就是按照从上往下,从左往右的顺序遍历二叉树的元素。 实现二叉树的层序遍历需要用到二叉树和队列。 总体思路: 判断当前队列是否为空 队列为空:结束。队列非空:取出队列第一个元素 将取出的元素的两...
  • 给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替) 例如: 给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树之字形层序遍历的结果是 [ [3], [20,9], [15,7] ] 输入:{1,...
  • 实验题目一:层序遍历二叉树 【实验步骤】 1 已知二叉树以二叉链表作为存储结构,写一个算法按层序遍历它,通过程序在终端屏幕上打印出它的层序序列。 2 先建立二叉树的二叉链表存储结构,再遍历它。
  • 在之前的多篇文章中,已经探讨过层序遍历二叉树了,本文稍作补充,讲述了借助循环队列来实现的情况。 具体实现如下:#include using namespace std; #define MAXSIZE 50typedef struct node { char data; struct...
  • 题目 输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。例如下面的二叉树,打印的结果是:8,6,10,5,7,9,11 ... * 层序遍历二叉树层数从上到小,同一层从左到右
  • 1.完全二叉树的概念是在层序遍历的基础上建立的,层序遍历就是从上而下一层层遍历,每层是从左到右遍历。 2.如果有一个节点的左孩子不存在,右孩子却存在,那么必定不是完全二叉树 3.当出现某一个节点的左右孩子不是...
  • 说起二叉树遍历,大家并不陌生,先序遍历、中序遍历、后序遍历、层序遍历等等,在面试过程中,二叉树是许多面试官喜欢问的一个考点,大家需要将二叉树的上述遍历牢记于心。   今天,我们将重点讨论二叉树层序...
  • 层序遍历,顾名思义就是按照每一层的顺序从左至右打印二叉树。 有二种算法实现此功能,我们重点讲如何用队列实现 void FloorOrderTraverse(Sequeue &S,BinTree &B) { BinTree e; if (B != NULL) { ...
  • 经典算法层序遍历二叉树

    千次阅读 2017-12-23 12:51:59
    cout 层序遍历:"; levelOrderBTree(pTree); return 0; } BTree creatTree() {//创建一颗二叉树 BTree pA = (BTNode *)malloc(sizeof(BTNode)); BTree pB = (BTNode *)malloc(sizeof(BTNode)); BTree ...
  • 题目名:从上往下打印二叉树(层序遍历二叉树) 编程语言 Java 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 初次思路 非常经典的广度优先遍历BFS 层序遍历,使用队列 解题代码 public class ...
  • 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 解题思路 将二叉树层序遍历结果装入二维数组 利用队列保存每一层的节点,遍历每一层节点,保存值,并将下一层入队列 ...
  • 题面 Given a binary tree, return thelevel ordertraversal of its nodes' values....层序遍历二叉树,要求从上到下,从左到右,输出结果为二维vector。 样例 Given binary tree[3,9,20,null,null...
  • 1 已知二叉树以二叉链表作为存储结构,写一个算法层序遍历它,通过程序在终端屏幕上打印出它的层序序列。 2 先建立二叉树的二叉链表存储结构,再遍历它。 3 利用队列完成算法
  • 01 如何实现二叉树 首先定义树的结点 public class Node { public int data; public Node left; public Node right; public Node (int data){ this.data=data; this.left=null; this.right...
  • 比较简单,直接上代码 ... import java.util.LinkedList; /** * 层序遍历数组 * Author : BlueSky 2019.11.15 * 思路:利用队列实现 */ public class LayerTree { public void foreach(Tr...
  • 二叉树层序遍历有点类似于图的广度优先遍历算法(DFS)的思想。迭代方法:使用一个辅助优先级队列,出队列一个节点时,遍历它的左右孩子,然后左右孩子入队列,当优先级队列为空时,迭代完成。 DFS-BINARYTREE...
  • 迭代遍历二叉树 中序遍历 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] cur = root # 中序,模板:先用指针找到每颗子树的最左下角,然后进行进出栈...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,820
精华内容 4,728
关键字:

层序遍历二叉树算法