package com.data.struct.tree.binaryTree;
public class ArrayBinTree<T extends Comparable<T>> {
/* 树高度 */
private int deepth = 0;
/* 存储树结构数据 */
private Object[] arr ;
/* 数组大小 */
private int size = 0;
public ArrayBinTree(int dpth,T data){
this.deepth = dpth;
init(data);
}
private void init(T data){
this.size = (int)Math.pow(2, this.deepth)-1;
this.arr = new Object[this.size];
this.arr[0]=data;
}
public int[] getNodeIndexBydepth(int h){
int len=(int)Math.pow(2, h-1);
int[] tmparr = new int[len];
int start=0;
if(h>1){
start =(int)Math.pow(2, h-1)-1;
}
for(int i=0;i<len;i++){
tmparr[i]=start;
start++;
}
//for(int i=0;i<len;i++){
//System.out.print(tmparr[i]);System.out.print(",");
//}
//System.out.println("-----------");
//
return tmparr;
}
/**
* 在父节点添加子节点
* @param parentIndex
* @param data
* @param isLeft
*/
public int addNode(int parentIndex,T data,boolean isLeft){
int index=0;
if(parentIndex<0){
throw new IllegalArgumentException("不合法的父节点");
}
if(((parentIndex)*2+2)>=arr.length){
throw new IndexOutOfBoundsException("数组越界!");
}
if(isLeft){
index=parentIndex*2+1;
this.arr[parentIndex*2+1]=data;
}else{
index=parentIndex*2+2;
this.arr[(parentIndex)*2+2]=data;
}
return index;
}
/**
* 判断书是否为空
* @return
*/
public boolean isEmpty(){
if(arr[0]==null){
return true;
}else{
return false;
}
}
/**
* 根据父节点去取子节点信息
* @param parentIndex
* @param isLeft
* @return
*/
@SuppressWarnings({"unchecked"})
public T getSubNode(int parentIndex,boolean isLeft){
if(parentIndex<0){
throw new IllegalArgumentException("不合法的父节点");
}
if(((parentIndex)*2+2)>=arr.length){
throw new IndexOutOfBoundsException("数组越界!");
}
if(isLeft){
parentIndex = parentIndex*2+1;
}else{
parentIndex = parentIndex*2+2;
}
return (T)this.arr[parentIndex];
}
/**
* 返回根节点
*/
@SuppressWarnings( { "unchecked" })
public T getRootNode(){
return (T)this.arr[0];
}
/**
* 根据子节点获取父节点信息
* @param index
* @return
*/
@SuppressWarnings({"unchecked"})
public T getParentNode(int index){
if(index>=this.arr.length){
throw new IndexOutOfBoundsException("数组越界!");
}
index = index/2;
return (T)this.arr[index];
}
/**
* 树的大小
* @return
*/
public int getTreeSize(){
return this.arr.length;
}
/**
* 根据名称查找节点索引
* @param obj
* @return
*/
public int getNodeIndex(T obj){
for(int i=0;i<arr.length;i++){
if(this.arr[i]!=null && this.arr[i].equals(obj)){
return i;
}
}
return -1;
}
public Object[] getNodesByDpth(int h){
int tmparr[]=getNodeIndexBydepth(h);
Object[] arr2=new Object[tmparr.length];
int j=0;
for(int i:tmparr){
arr2[j]=this.arr[i];
j++;
}
return arr2;
}
/**
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayBinTree<String> tree = new ArrayBinTree<String>(20, "家庭");
int index=0;
int index2=0;
index=tree.addNode(0, "男", true);
index2=tree.addNode(0, "女", false);
tree.addNode(index, "爷爷他弟", false);
index=tree.addNode(index, "爷爷", true);
tree.addNode(index, "爸爸他弟", false);
index=tree.addNode(index, "爸爸", true);
tree.addNode(index, "儿子", true);
tree.addNode(tree.getNodeIndex("女"), "奶奶他妹", false);
index2=tree.addNode(index2, "奶奶", true);
tree.addNode(tree.getNodeIndex("奶奶"), "妈妈他妹", false);
index2=tree.addNode(index2, "妈妈", true);
index2=tree.addNode(index2, "女儿", true);
for(int d=0;d<5;d++){
System.out.print("第"+(d+1)+"层:");
Object[] arr2=tree.getNodesByDpth(d+1);
for(Object obj:arr2){
if(obj==null){
continue;
}
System.out.print((String)obj+",");
}
System.out.println();
}
}
}
相关推荐
java动态数组java动态数组java动态数组java动态数组java动态数组java动态数组java动态数组java动态数组java动态数组java动态数组
现在运用很广的JAV,目前针对第四课的常用包和数组有关的东西进行介绍
二叉树是我们常见的数据结构之一,在学习二叉树之前我们需要知道什么是树,什么是二叉树,本篇主要讲述了二叉树,以及二叉树的遍历。 你能get到的知识点? 1、树的介绍 2、二叉树的介绍 3、二叉树遍历的四种方法 4、...
先说说这个实例的要求:写一个方法实现数组的去重。(要求:执行方法,传递一个数组,返回去重后的新数组,原数组不变,实现过程中只能用一层循环,双层嵌套循环也可写,只做参考); 先给初学者解释一下什么叫数组...
一些关于java程序的小练习。小型的程序。
JAVBus.ipa
1、什么是数组 数组就是一组数据的集合 其表现形式就是内存中的一段连续的内存地址 数组名称其实就是连续内存地址的首地址 2、关于js中的数组特点 数组定义时无需指定数据类型 数组定义时可以无需指定数组长度 数组...
yrtos_ MULTITASKING RTOS,.
图书管理系统,可以查询 图书管理系统,可以查询
练习作品DVD定制系统 使用JAVA语言 正在学习JAVA
hello , very basic android java source code for set ringtone.
数组去重是一个比较常见的算法考察点,实现去重的方式无非就是唯一性或者非唯一性,简而言之,就是选出唯一的或者去掉不唯一的,下面总结了几种方法。 方法一:利用双层for循环通过原数组去重,就是遍历数组,把数组...
JAV Torrent 掲示板.URL
jav 读取本地文件列表 FileBrowser_demojav 读取本地文件列表 FileBrowser_demo
JAV LED32HD320 LAD.MV59S.B MT3151A04-1-XC-9 7J JAV LED32HD320 LAD.MV59S.B MT3151A04-1-XC-9 7J
基于JAV技术的医院管理住院系统的研究与实现毕业设计论文资料+软件源码+视频说明,本系统主要分为六大模块,分别是医生管理模块、病人管理模块、病床管理模块、收费管理模块、统计分析模块和系统功能模块 ...
显示数据库中的表用java(完整)- - *该程序代码用到了前面说的database.java的数据库连接池的类
JAV独立升级程序,用于给系统的JDK JAV、jre进行安装和升级。本程序从JAV6.0原版而来。
用java实现了一个一维数组类。包括加和、最值、归并排序等
下面小编就为大家带来一篇Java创建数组的几种方式总结。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧