精华内容
下载资源
问答
  • 实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。   二,算法分析 层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要用到栈。 因此,先、中、后序遍历...

    一,问题描述

    实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。

     

    二,算法分析

    层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要用到栈。

    因此,先、中、后序遍历 可以 采用递归方式来实现,而层序遍历则没有递归方式。

    算法步骤:

    初始时,根结点入队列

    然后,while循环判断队列不空时,弹出一个结点,访问它,并把它的所有孩子结点入队列。

     

    三,代码实现

    复制代码
     1     public void levelTraverse(BinarySearchTree<T> tree){
     2         levelTraverse(tree.root);
     3     }
     4     private void levelTraverse(BinaryNode<T> root){
     5         if(root == null)
     6             return;
     7         
     8         Queue<BinaryNode<T>> queue = new LinkedList<>();//层序遍历时保存结点的队列
     9         queue.offer(root);//初始化
    10         while(!queue.isEmpty()){
    11             BinaryNode<T> node = queue.poll();
    12             System.out.print(node.element + " ");//访问节点
    13             if(node.left != null)
    14                 queue.offer(node.left);
    15             if(node.right != null)
    16                 queue.offer(node.right);
    17         }
    18     }
    复制代码
    展开全文
  • 二叉树的层序遍历算法 + 打印二叉树所有最左边的元素(算法) 层序遍历 /** * 树结构定义 */ private static class BinaryNode&amp;lt;T&amp;gt; { BinaryNode(T theElement) { this(theElement...

    二叉树的层序遍历算法 + 打印二叉树所有最左边的元素(算法)

    二叉树举例

    层序遍历

    /**
    * 树结构定义
    */
    private static class BinaryNode<T> {
    	BinaryNode(T theElement) {
    		this(theElement, null, null);
    	}
    
    	BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
    		element = theElement;
    		left = lt;
    		right = rt;
    	}
    
    	T element;
    	BinaryNode<T> left;
    	BinaryNode<T> right;
    }
    
    //层序遍历方法
    public static void levelRead(BinaryNode node) {
    	if (node == null) {
    		return;
    	}
    	//计算深度
    	int depth = calcDepth(node);
    	
    	for (int i = 0; i < depth; i++) {
    		//打印每个深度上的所有节点
    		readLevel(node,i);
    	}
    	
    	
    	
    	
    }
    
    private static void readLevel(BinaryNode node, int i) {
    	if (node == null||i<1) {
    		return;
    	}
    	//递归打印,如果层级为1,则打印当前节点,如果不为1,则说明还在比较高的等级,需要递归从头往下继续找当前层。
    	if (i == 1) {
    		System.out.print(node.element+"  ");
    	}
    	
    	readLevel(node.left, i-1);
    	readLevel(node.right, i-1);
    	
    	
    	
    	
    }
    
    private static int calcDepth(BinaryNode node) {
    	if (node ==null) {
    		return 0;
    	}
    	int ld = calcDepth(node.left);
    	int rd = calcDepth(node.right);
    	if (ld>rd) {
    		return ld+1;
    	}else{
    		return rd+1;
    	}
    }
    

    打印二叉树所有最左边的元素

    在层序遍历的基础上,我们可以借此实现打印二叉树上所有最左边的元素,代码如下:

    public static void levelReadLeft(BinaryNode node) {
    	if (node == null) {
    		return;
    	}
    	int depth = calcDepth(node);
    	
    	for (int i = 1; i <= depth; i++) {
    		String string = readLevelLeft(node,i);
    		System.out.println(string);
    	}
    }
    
    private static String readLevelLeft(BinaryNode node, int i) {
    	String reString = "";
    	if (node == null||i<1) {
    		return reString;
    	}
    	if (i == 1) {
    		return reString + (node.element+"  ");
    	}
    	
    	reString += readLevelLeft(node.left, i-1);
    	if (reString.equals ("")) {
    		reString += readLevelLeft(node.right, i-1);
    	}
    	return reString;
    }
    
    
    
    
    private static int calcDepth(BinaryNode node) {
    	if (node ==null) {
    		return 0;
    	}
    	int ld = calcDepth(node.left);
    	int rd = calcDepth(node.right);
    	if (ld>rd) {
    		return ld+1;
    	}else{
    		return rd+1;
    	}
    }
    

    从顶层遍历最右边节点

    代码如下:

     public static void levelReadRight(BinaryNode node) {
    	if (node == null) {
    		return;
    	}
    	int depth = calcDepth(node);
    	
    	for (int i = 1; i <= depth; i++) {
    		String string = readLevelRight(node,i);
    		System.out.println(string);
    	}
    }
    
    private static String readLevelRight(BinaryNode node, int i) {
    	String reString = "";
    	if (node == null||i<1) {
    		return reString;
    	}
    	if (i == 1) {
    		return reString + (node.element+"  ");
    	}
    	
    	reString += readLevelRight(node.right, i-1);
    	if (reString.equals ("")) {
    		reString += readLevelRight(node.left, i-1);
    	}
    	return reString;
    }
    
    
    
    
    private static int calcDepth(BinaryNode node) {
    	if (node ==null) {
    		return 0;
    	}
    	int ld = calcDepth(node.left);
    	int rd = calcDepth(node.right);
    	if (ld>rd) {
    		return ld+1;
    	}else{
    		return rd+1;
    	}
    }
    
    展开全文
  • 实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。 二,算法分析 层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要用到栈。 因此,先、中、后序遍历 可以 采用递归...

    一,问题描述

    实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。

     

    二,算法分析

    层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要用到栈。

    因此,先、中、后序遍历 可以 采用递归方式来实现,而层序遍历则没有递归方式。

    算法步骤:

    初始时,根结点入队列

    然后,while循环判断队列不空时,弹出一个结点,访问它,并把它的所有孩子结点入队列。

     

    三,代码实现

    复制代码
     1     public void levelTraverse(BinarySearchTree<T> tree){
     2         levelTraverse(tree.root);
     3     }
     4     private void levelTraverse(BinaryNode<T> root){
     5         if(root == null)
     6             return;
     7         
     8         Queue<BinaryNode<T>> queue = new LinkedList<>();//层序遍历时保存结点的队列
     9         queue.offer(root);//初始化
    10         while(!queue.isEmpty()){
    11             BinaryNode<T> node = queue.poll();
    12             System.out.print(node.element + " ");//访问节点
    13             if(node.left != null)
    14                 queue.offer(node.left);
    15             if(node.right != null)
    16                 queue.offer(node.right);
    17         }
    18     }
    复制代码

    二叉搜索树的完整实现代码参考:

    二叉查找树的递归实现及递归分析中的完整代码实现部分

    或者参考:

    二叉树的操作之统计二叉树中节点的个数中的完整代码实现部分

    本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5409921.html,如需转载请自行联系原作者


    展开全文
  • 我们来看看下图二叉链表 如何实现层序遍历层序遍历顺序:ABECDG A为B、E双亲结点,遍历顺序是 根-&gt;左-&gt;右 是不是。 而且每个结点都是这样遍历顺序 有木有。那么我们完全可以采用队列...

    实现思路

    我们来看看下图的二叉链表 如何实现层序遍历

    层序遍历顺序:ABECDG
    A为B、E的双亲结点,遍历顺序是 根->左->右 是不是。
    而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。
    A->出队
    队列:E、B
    B->出队
    队列:D、C、E
    E->出队
    队列:G、D、C
    C->出队
    队列:G、D
    D->出队
    队列:G
    G->出队
    队列为空,层序遍历完毕

    二叉树层序遍历算法代码

    层序遍历函数

    层序遍历核心代码,利用了一个自己底层封装的顺序队列如果想知道怎么实现的呢,请看线性表:顺序队列算法实现

    //一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }

    完整代码

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    typedef char ElemType;
    typedef struct BiNode
    {
    	ElemType data;
    	struct BiNode* lchild;
    	struct BiNode* rchild;
    }BiNode, *BiTree;
    
    //创建二叉链表
    void CreateBiTree(BiTree* tree) 
    {
    	char c;
    	scanf("%c", &c);
    	if (c == ' ')
    	{
    		*tree = NULL;
    		return;
    	}
    	*tree = malloc(sizeof(BiNode));
    	(*tree)->data = c;
    	CreateBiTree(&(*tree)->lchild);
    	CreateBiTree(&(*tree)->rchild);
    	return;
    }
    //二叉链表 递归前序遍历
    void PreTraverse(BiTree tree)
    {
    	if (tree == NULL)
    	{
    		return;
    	}
    	printf("%c ", tree->data);
    	PreTraverse(tree->lchild);
    	PreTraverse(tree->rchild);
    }
    
    //一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请前序遍历输入结点:");
    	CreateBiTree(&tree);
    	printf("前序遍历:");
    	PreTraverse(tree);
    	printf("\n层序遍历:");
    	SeqTraverse(tree);
    	
    	return 0;
    }
    

    代码运行检测

    我们构建如下图的二叉树,注意创建二叉树输入序列为:ABC__D__E_G__,_代表一个空格哟。

    运行结果

     

    展开全文
  • 层序遍历: 从二叉树根节点开始,按自上而下、从左到右顺序进行遍历。 1. **基本思路**:用队列实现 2. **大致过程**:遍历从根结点开始,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右...
  • 层序遍历的定义是从根结点开始,按照从上到下,从左到右的顺序访问二叉树的每个结点。 那么具体到某个结点——根结点与它的左、右孩子,根A->左孩子B->右孩子C,下一遍是结点B->左孩子->右孩子->结点...
  • public List<Integer> levelOrder(TreeNode root) { List<Integer> list = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); ... node = qu.
  • 二叉树的层序遍历

    2019-05-07 09:48:36
    二叉树的层序遍历算法实现 一,问题描述 实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。 二,算法分析 层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要...
  • @Leetcode二叉树的层序遍历Ⅱ 当笔者对各种二叉树的题目有点小小自信的时候,就又被这道简单题给打败了,脑袋一片空白开始看题:
  • 二叉树的层序遍历
  • 前端算法 二叉树的层序遍历通过DFS或BFS遍历,依次遍历二叉树遍历的结果值。队列满足先进先出的要求,出列就,新的层进来,旧的层出来
  • 微信搜一搜:bigsai 大家都在关注的刷题、学习数据...二叉树的层序遍历 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,null,15,7], 3 .
  • 一、二叉树的层序遍历 二、代码实现 三、总结 一、二叉树的层序遍历 算法思想: ①初始化一个辅助队列 ②根结点入队 ③若队列非空,则队头结点出队,访问该结点,将其左右孩子插入队尾(如果有的话) ④...
  • 二叉树的层序遍历(详细注释,慎点)
  • 【数据结构与算法二叉树的层序遍历

    万次阅读 多人点赞 2013-10-27 14:51:06
    前面有篇博客详细分析了二叉树三种遍历(前序、中序、后序)方式的递归与非递归实现,参见:http://blog.csdn.net/ns_code/article/details/12977901,但把二叉树的层序遍历算法给漏掉了,实际上也不能说漏掉了,...
  • Java二叉树的层序遍历

    2021-02-23 14:25:23
    牛客网,求二叉树的层序遍历 LeetCode,求二叉树的层序遍历 思想 1.根结点先入队 2.出队访然后问其左右孩子结点并入队 3.重复2的步骤直到队列为空 算法 public ArrayList<ArrayList<Integer>> level...
  •  前面有篇博客详细分析了二叉树三种遍历(前序、中序、后序)方式的递归与非递归实现,参见:http://blog.csdn.net/ns_code/article/details/12977901,但把二叉树的层序遍历算法给漏掉了,实际上也不能说漏掉了
  • 前面有篇博客详细分析了二叉树三种遍历(前序、中序、后序)方式的递归与非递归实现,参见:http://blog.csdn.net/u012426327/article/details/77418101,但把二叉树的层序遍历算法给漏掉了,实际上也不能说漏掉了,...
  • 二叉树的层序遍历: 给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历) 例如: 给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树层序遍历的结果是 [ [3], [9,20], [15,7] ] 算法思想:使用队列...
  • [力扣] 二叉树的层序遍历 广度优先算法,遍历每一层的节点 例题: 102. 二叉树的层序遍历 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # ...
  • 队列1前言1、 二叉树的层序遍历(102)2、二叉树的锯齿形层次遍历(103)3、二叉树的层次遍历II(107)4、二叉树的右视图(199) 前言 队列的基本知识 \quad \quad队列的基本应用: 1、广度优先遍历 树:层序遍历 图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,045
精华内容 418
关键字:

二叉树的层序遍历算法