Java中树的存储结构实现示例代码

2023-09-24 08:28:05 58
一、树
树与线性表、栈、队列等线性结构不同，树是一种非线性结构。
一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。
二、树的父节点表示法
树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。
packagecom.ietree.basic.datastructure.tree;

importjava.util.ArrayList;
importjava.util.List;

/**
*Createdbyietree
*2017/4/30
*/
publicclassTreeParent{

publicstaticclassNode{

Tdata;
//保存其父节点的位置
intparent;

publicNode(){

}

publicNode(Tdata){
this.data=data;
}

publicNode(Tdata,intparent){
this.data=data;
this.parent=parent;
}

publicStringtoString(){
return"TreeParent$Node[data="+data+",parent="+parent+"]";
}

}

privatefinalintDEFAULT_TREE_SIZE=100;
privateinttreeSize=0;
//使用一个Node[]数组来记录该树里的所有节点
privateNode[]nodes;
//记录树的节点数
privateintnodeNums;

//以指定节点创建树
publicTreeParent(Edata){
treeSize=DEFAULT_TREE_SIZE;
nodes=newNode[treeSize];
nodes[0]=newNode(data,-1);
nodeNums++;
}

//以指定根节点、指定treeSize创建树
publicTreeParent(Edata,inttreeSize){
this.treeSize=treeSize;
nodes=newNode[treeSize];
nodes[0]=newNode(data,-1);
nodeNums++;
}

//为指定节点添加子节点
publicvoidaddNode(Edata,Nodeparent){
for(inti=0;iroot(){
//返回根节点
returnnodes[0];
}

//返回指定节点（非根结点）的父节点
publicNodeparent(Nodenode){
//每个节点的parent记录了其父节点的位置
returnnodes[node.parent];
}

//返回指定节点（非叶子节点）的所有子节点
publicList>children(Nodeparent){
List>list=newArrayList>();
for(inti=0;i
测试类：
packagecom.ietree.basic.datastructure.tree;

importjava.util.List;

/**
*Createdbyietree
*2017/4/30
*/
publicclasstreeParentTest{

publicstaticvoidmain(String[]args){

TreeParenttp=newTreeParent("root");
TreeParent.Noderoot=tp.root();
System.out.println(root);
tp.addNode("节点1",root);
System.out.println("此树的深度："+tp.deep());
tp.addNode("节点2",root);
//获取根节点的所有子节点
List>nodes=tp.children(root);
System.out.println("根节点的第一个子节点："+nodes.get(0));
//为根节点的第一个子节点新增一个子节点
tp.addNode("节点3",nodes.get(0));
System.out.println("此树的深度："+tp.deep());

}
}


程序输出：
TreeParent$Node[data=root,parent=-1]

此树的深度：2

根节点的第一个子节点：TreeParent$Node[data=节点1,parent=0]

此树的深度：3
三、子节点链表示法
让父节点记住它的所有子节点。


packagecom.ietree.basic.datastructure.tree;

importjava.util.ArrayList;
importjava.util.List;

/**
*Createdbyietree
*2017/4/30
*/
publicclassTreeChild{

privatestaticclassSonNode{
//记录当前节点的位置
privateintpos;
privateSonNodenext;

publicSonNode(intpos,SonNodenext){
this.pos=pos;
this.next=next;
}
}

publicstaticclassNode{
Tdata;
//记录第一个子节点
SonNodefirst;

publicNode(Tdata){
this.data=data;
this.first=null;
}

publicStringtoString(){
if(first!=null){
return"TreeChild$Node[data="+data+",first="+first.pos+"]";
}else{
return"TreeChild$Node[data="+data+",first=-1]";
}
}
}

privatefinalintDEFAULT_TREE_SIZE=100;
privateinttreeSize=0;
//使用一个Node[]数组来记录该树里的所有节点
privateNode[]nodes;
//记录节点数
privateintnodeNums;

//以指定根节点创建树
publicTreeChild(Edata){
treeSize=DEFAULT_TREE_SIZE;
nodes=newNode[treeSize];
nodes[0]=newNode(data);
nodeNums++;
}

//以指定根节点、指定treeSize创建树
publicTreeChild(Edata,inttreeSize){
this.treeSize=treeSize;
nodes=newNode[treeSize];
nodes[0]=newNode(data);
nodeNums++;
}

//为指定节点添加子节点
publicvoidaddNode(Edata,Nodeparent){
for(inti=0;iroot(){
//返回根节点
returnnodes[0];
}

//返回指定节点（非叶子节点）的所有子节点
publicList>children(Nodeparent){

List>list=newArrayList>();
//获取parent节点的第一个子节点
SonNodenext=parent.first;
//沿着孩子链不断搜索下一个孩子节点
while(next!=null){
//添加孩子链中的节点
list.add(nodes[next.pos]);
next=next.next;
}
returnlist;

}

//返回指定节点（非叶子节点）的第index个子节点
publicNodechild(Nodeparent,intindex){
//获取parent节点的第一个子节点
SonNodenext=parent.first;
//沿着孩子链不断搜索下一个孩子节点
for(inti=0;next!=null;i++){
if(index==i){
returnnodes[next.pos];
}
next=next.next;
}
returnnull;
}

//返回该树的深度
publicintdeep(){
//获取该树的深度
returndeep(root());
}

//这是一个递归方法：每棵子树的深度为其所有子树的最大深度+1
privateintdeep(Nodenode){
if(node.first==null){
return1;
}else{
//记录其所有子树的最大深度
intmax=0;
SonNodenext=node.first;
//沿着孩子链不断搜索下一个孩子节点
while(next!=null){
//获取以其子节点为根的子树的深度
inttmp=deep(nodes[next.pos]);
if(tmp>max){
max=tmp;
}
next=next.next;
}
//最后，返回其所有子树的最大深度+1
returnmax+1;
}
}

//返回包含指定值得节点
publicintpos(Nodenode){
for(inti=0;i
测试类：


packagecom.ietree.basic.datastructure.tree;

importjava.util.List;

/**
*Createdbyietree
*2017/4/30
*/
publicclassTreeChildTest{

publicstaticvoidmain(String[]args){

TreeChildtp=newTreeChild("root");
TreeChild.Noderoot=tp.root();
System.out.println(root);
tp.addNode("节点1",root);
tp.addNode("节点2",root);
tp.addNode("节点3",root);
System.out.println("添加子节点后的根结点："+root);
System.out.println("此树的深度："+tp.deep());
//获取根节点的所有子节点
List>nodes=tp.children(root);
System.out.println("根节点的第一个子节点："+nodes.get(0));
//为根节点的第一个子节点新增一个子节点
tp.addNode("节点4",nodes.get(0));
System.out.println("此树第一个子节点："+nodes.get(0));
System.out.println("此树的深度："+tp.deep());

}

}


程序输出：
TreeChild$Node[data=root,first=-1]

添加子节点后的根结点：TreeChild$Node[data=root,first=1]

此树的深度：2

根节点的第一个子节点：TreeChild$Node[data=节点1,first=-1]

此树第一个子节点：TreeChild$Node[data=节点1,first=4]

此树的深度：3
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
Java中树的存储结构实现示例代码

热门推荐

随机推荐
