java实现按层遍历二叉树

本文实例为大家分享了java实现按层遍历二叉树，按层遍历二叉树可以通过队列来实现。其主要思路如下：

1、先将根节点放入队列中

2、每次都从队列中取出一个结点打印该结点的值

3、若这个结点有子结点，则将它的子结点放入队列尾，知道队列为空。

实现代码如下：

import java.util.LinkedList;
import java.util.Queue;

public class LayerTranverse {

 //按层遍历二叉树
 public static void main(String[] args) {
 BinaryTree1 biTree1=new BinaryTree1();
 int[] data={2,8,7,4,9,3,1,6,5};
 biTree1.buildTree1(data);
 biTree1.layerTranverse();
 }

}
class Node1{
 public int data;
 public Node1 left;
 public Node1 right;
 public Node1(int data){
 this.data=data;
 this.left=null;
 this.right=null;
 }
}
class BinaryTree1{
 private Node1 root;
 public BinaryTree1(){
 root=null;
 }
 //将data数据插入到排序的二叉树中
 public void insert1(int data){
 Node1 newNode1=new Node1(data);
 if(root==null){
  root=newNode1;
 }else{
  Node1 current=root;
  Node1 parent;
  while(true){
  parent=current;
  if(data<current.data){
   current=current.left;
   if(current==null){
   parent.left=newNode1;
   return;
   }
  }else{
   current=current.right;
   if(current==null){
    parent.right=newNode1;
    return;
   }
  }
  }

 }
 }
 public void buildTree1(int[] data){
 for(int i=0;i<data.length;i++){
  insert1(data[i]);
 }
 }
 public void layerTranverse(){
 if(this.root==null){
  return;
 }
 Queue<Node1> q=new LinkedList<Node1>();
 q.add(this.root);
 while(!q.isEmpty()){
  Node1 n=q.poll();
  System.out.print(n.data);
  System.out.print(" ");
  if(n.left!=null){
  q.add(n.left);
  }
  if(n.right!=null){
  q.add(n.right);
  }
 }
 }
}

运行结果为：

2 1 8 7 9 4 3 6 5

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java二叉树的遍历思想及核心代码实现

    Java二叉树的遍历思想及核心代码实现

    二叉树在计算机中的存储方式往往线性结构,线性存储分为顺序存储和链式存储,将二叉树按层序编号. 顺序结构:按编号的顺序进行存储,对于完全二叉树而言,顺序存储可以反映二叉树的逻辑,但是对于大多数的二叉树则无法反映其逻辑关系,不过可以用 ^ 来代替不存在的结点,但是如果这个树是一个右斜树,就非常浪费存储空间.所以二叉树的存储形式一般为链式存储结构. 链式存储:每一个结点都分有一个数据域(data)和两个指针域(lchild和rchild),指针域分别指向左孩子和右孩子,若为空则为null.遍历方式有四

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • 平衡二叉树的左右旋以及双旋转的图文详解

    平衡二叉树的左右旋以及双旋转的图文详解

    高度平衡的搜索二叉树 一棵平衡树,或是空树,或是具有以下性质的二叉搜索树:左子树和右子树都是AVL树,且左右子树的高度之差的绝对值不超过1. 该二叉树,根结点的右子树高度为3,左子树高度为2.结点上方的数字为平衡因子,因为右子树高度比左子树高度大1,所以根结点的平衡因子为1. 一颗平衡二叉树,如果有n个结点,其高度可保持O(log2^n),平均搜索长度也可以保持在O(log2^n) 平衡化旋转  AVL树相较于普通的二叉搜索树,自主要的就是做了平衡化处理,使得二叉树变的平衡,高度降低. 在插入一

  • 平衡二叉树AVL操作模板

    复制代码 代码如下: /*** 目的:实现AVL* 利用数组对左右儿子简化代码,但是对脑力难度反而增大不少,只适合acm模板* 其实avl在acm中基本不用,基本被treap取代* avl一般只要求理解思路,不要求写出代码,因为真心很烦*/ #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <

  • C语言判定一棵二叉树是否为二叉搜索树的方法分析

    本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n

  • C语言数据结构之平衡二叉树（AVL树）实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

  • 平衡二叉树的实现实例

    复制代码 代码如下: /*首先平衡二叉树是一个二叉排序树:其基本思想是:在构建二叉排序树的过程中,当每插入一个节点时,先检查是否因为插入而破坏了树的平衡性,若是,找出最小不平衡树,进行适应的旋转,使之成为新的平衡二叉树.*/#include<cstdio>#include<cstdlib>#define LH 1#define EH 0#define RH -1 using namespace std; typedef struct BTNode{ int data; int BF

  • Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例

    本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作.分享给大家供大家参考,具体如下: 实现一个功能: 输入:一颗二叉树的先序和中序遍历     输出:后续遍历 思想: 先序遍历中,第一个元素是树根     在中序遍历中找到树根,左边的是左子树 右边的是右子树 Python代码: # -*- coding:utf-8 -*- def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取

  • C语言 数据结构平衡二叉树实例详解

    C语言 数据结构平衡二叉树实例详解

    数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

  • python 平衡二叉树实现代码示例

    平衡二叉树: 在上一节二叉树的基础上我们实现,如何将生成平衡的二叉树 所谓平衡二叉树: 我自己定义就是:任何一个节点的左高度和右高度的差的绝对值都小于2 如图所示,此时a的左高度等于3,有高度等于1,差值为2,属于不平衡中的左偏 此时的处理办法就是: 将不平衡的元素的左枝的最右节点变为当前节点, 此时分两种情况: 一.左枝有最右节点 将最右节点的左枝赋予其父节点的右枝 二.左枝没有最右节点, 直接将左枝节点做父级节点,父级节点做其右枝 如图所示,图更清楚些. 可能会有疑问,为什么这样变换? 假定

随机推荐