java数据结构之树基本概念解析及代码示例
java中树的存储结构实现 一、树 树与线性表、栈、队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点
树是一种抽象数据类型（adt）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把 它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树定义和基本术语
定义
树(tree)是n(n≥0)个结点的有限集t，并且当n＞0时满足下列条件：
（1）有且仅有一个特定的称为根(root)的结点；
（2）当n＞1时，其余结点可以划分为m(m＞0)个互不相交的有限集t1、t2、…、tm，每个集ti(1≤i≤m)均为树，且称为树t的子树(subtree)。
特别地，不含任何结点(即n＝0)的树，称为空树。
如下就是一棵树的结构：
基本术语
结点：存储数据元素和指向子树的链接，由数据元素和构造数据元素之间关系的引用组成。
孩子结点：树中一个结点的子树的根结点称为这个结点的孩子结点，如图1中的a的孩子结点有b、c、d
双亲结点：树中某个结点有孩子结点(即该结点的度不为0)，该结点称为它孩子结点的双亲结点，也叫前驱结点。双亲结点和孩子结点是相互的，如图1中，a的孩子结点是b、c、d，b、c、d的双亲结点是a。
兄弟结点：具有相同双亲结点(即同一个前驱)的结点称为兄弟结点，如图1中b、b、d为兄弟结点。
结点的度：结点所有子树的个数称为该结点的度，如图1，a的度为3，b的度为2.
树的度：树中所有结点的度的最大值称为树的度，如图1的度为3.
叶子结点：度为0的结点称为叶子结点，也叫终端结点。如图1的k、l、f、g、m、i、j
分支结点：度不为0的结点称为分支结点，也叫非终端结点。如图1的a、b、c、d、e、h
结点的层次：从根结点到树中某结点所经路径的分支数称为该结点的层次。根结点的层次一般为1(也可以自己定义为0)，这样，其它结点的层次是其双亲结点的层次加1.
树的深度：树中所有结点的层次的最大值称为该树的深度(也就是最下面那个结点的层次)。
有序树和无序树：树中任意一个结点的各子树按从左到右是有序的，称为有序树，否则称为无序树。
树的抽象数据类型描述
数据元素：具有相同特性的数据元素的集合。
结构关系：树中数据元素间的结构关系由树的定义确定。
基本操作：树的主要操作有
（1）创建树inttree(&t)
创建1个空树t。
（2）销毁树destroytree(&t)
（3）构造树creattree(&t，deinition)
（4）置空树cleartree(&t)
将树t置为空树。
（5）判空树treeempty(t)
（6）求树的深度treedepth(t)
（7）获得树根root(t)
（8）获取结点value(t，cur_e，&e)
将树中结点cur_e存入e单元中。
（9）数据赋值assign(t，cur_e，value)
将结点value，赋值于树t的结点cur_e中。
（10）获得双亲parent(t，cur_e)
返回树t中结点cur_e的双亲结点。
（11）获得最左孩子leftchild(t，cur_e)
返回树t中结点cur_e的最左孩子。
（12）获得右兄弟rightsibling(t，cur_e)
返回树t中结点cur_e的右兄弟。
（13）插入子树insertchild(&t，&p，i，c)
将树c插入到树t中p指向结点的第i个子树之前。
（14）删除子树deletechild(&t，&p，i)
删除树t中p指向结点的第i个子树。
（15）遍历树traversetree(t，visit())
树的实现
树是一种递归结构，表示方式一般有孩子表示法和孩子兄弟表示法两种。树实现方式有很多种、有可以由广义表的递归实现，也可以有二叉树实现，其中最常见的是将树用孩子兄弟表示法转化成二叉树来实现。
下面以孩子表示法为例讲一下树的实现：
树的定义和实现
package datastructure.tree;
import java.util.arraylist;
import java.util.arrays;
import java.util.linkedlist;
import java.util.list;
/**
* 树的定义和实现
* @author administrator
*
*/
public class tree {
private object data;
private list<tree> childs;
public tree(){
data = null;
childs = new arraylist();
childs.clear();
}
public tree(object data) {
this.data = data;
childs = new arraylist();
childs.clear();
}
/**
* 添加子树
* @param tree 子树
*/
public void addnode(tree tree) {
childs.add(tree);
}
/**
* 置空树
*/
public void cleartree() {
data = null;
childs.clear();
}
/**
* 求树的深度
* 这方法还有点问题，有待完善
* @return 树的深度
*/
public int dept() {
return dept(this);
}
/**
* 求树的深度
* 这方法还有点问题，有待完善
* @param tree
* @return
*/
private int dept(tree tree) {
if(tree.isempty()) {
return 0;
} else if(tree.isleaf()) {
return 1;
} else {
int n = childs.size();
int[] a = new int[n];
for (int i=0; i<n; i++) {
if(childs.get(i).isempty()) {
a[i] = 0+1;
} else {
a[i] = dept(childs.get(i)) + 1;
}
}
arrays.sort(a);
return a[n-1];
}
}
/**
* 返回递i个子树
* @param i
* @return
*/
public tree getchild(int i) {
return childs.get(i);
}
/**
* 求第一个孩子 结点
* @return
*/
public tree getfirstchild() {
return childs.get(0);
}
/**
* 求最后 一个孩子结点
* @return
*/
public tree getlastchild() {
return childs.get(childs.size()-1);
}
public list<tree> getchilds() {
return childs;
}
/**
* 获得根结点的数据
* @return
*/
public object getrootdata() {
return data;
}
/**
* 判断是否为空树
* @return 如果为空，返回true,否则返回false
*/
public boolean isempty() {
if(childs.isempty() && data == null)
return true;
return false;
}
/**
* 判断是否为叶子结点
* @return
*/
public boolean isleaf() {
if(childs.isempty())
return true;
return false;
}
/**
* 获得树根
* @return 树的根
*/
public tree root() {
return this;
}
/**
* 设置根结点的数据
*/
public void setrootdata(object data) {
this.data = data;
}
/**
* 求结点数
* 这方法还有点问题，有待完善
* @return 结点的个数
*/
public int size() {
return size(this);
}
/**
* 求结点数
* 这方法还有点问题，有待完善
* @param tree
* @return
*/
private int size(tree tree) {
if(tree.isempty()) {
return 0;
} else if(tree.isleaf()) {
return 1;
} else {
int count = 1;
int n = childs.size();
for (int i=0; i<n; i++) {
if(!childs.get(i).isempty()) {
count += size(childs.get(i));
}
}
return count;
}
}
}
树的遍历
树的遍历有两种
前根遍历
（1）.访问根结点；
（2）.按照从左到右的次序行根遍历根结点的第一棵子树；
后根遍历
（1）.按照从左到右的次序行根遍历根结点的第一棵子树；
（2）.访问根结点；
visit.java
package datastructure.tree;
import datastructure.tree.btree.btree;
/**
* 对结点进行操作的接口,规定树的遍历的类必须实现这个接口
* @author administrator
*
*/
public interface visit {
/**
* 对结点进行某种操作
* @param btree 树的结点
*/
public void visit(btree btree);
}
order.java
package datastructure.tree;
import java.util.list;
/**
* 树的遍历
* @author administrator
*
*/
public class order {
/**
* 先根遍历
* @param root 要的根结点
*/
public void preorder(tree root) {
if(!root.isempty()) {
visit(root);
for (tree child : root.getchilds()) {
if(child != null) {
preorder(child);
}
}
}
}
/**
* 后根遍历
* @param root 树的根结点
*/
public void postorder(tree root) {
if(!root.isempty()) {
for (tree child : root.getchilds()) {
if(child != null) {
preorder(child);
}
}
visit(root);
}
}
public void visit(tree tree) {
system.out.print("\t" + tree.getrootdata());
}
}
测试：
要遍历的树如下：
package datastructure.tree;
import java.util.iterator;
import java.util.scanner;
public class treetest {
/**
* @param args
*/
public static void main(string[] args) {
tree root = new tree("a");
root.addnode(new tree("b"));
root.addnode(new tree("c"));
root.addnode(new tree("d"));
tree t = null;
t = root.getchild(0);
t.addnode(new tree("l"));
t.addnode(new tree("e"));
t = root.getchild(1);
t.addnode(new tree("f"));
t = root.getchild(2);
t.addnode(new tree("i"));
t.addnode(new tree("h"));
t = t.getfirstchild();
t.addnode(new tree("l"));
system.out.println("first node:" + root.getrootdata());
//system.out.println("size:" + root.size());
//system.out.println("dept:" + root.dept());
system.out.println("is left:" + root.isleaf());
system.out.println("data:" + root.getrootdata());
order order = new order();
system.out.println("前根遍历：");
order.preorder(root);
system.out.println("\n后根遍历：");
order.postorder(root);
}
}
结果：
first node:a
is left:false
data:a
前根遍历：
a bl e c f di l h
后根遍历：
b le c f d il h a
结束语：
以上就是本文关于java数据结构之树基本概念解析及代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：
如有不足之处，欢迎留言指出。
上一篇： Java多线程Atomic包操作原子变量与原子类详解
下一篇： PHP简单实现冒泡排序的方法