正文
树编辑距离java代码 java编写树形结构
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
论文翻译 求助
树是最常见和福利组合结构的研究
计算机科学。特别是，问题比较树木发生在几个
不同的领域，如计算生物学，结构化文本的数据库，图像
分析，自动定理证明和编译器优化[ 43 ， 55 ， 22 ， 24 ，
16 ， 35 ， 56 ] 。例如，在计算生物学，计算相似度
树木之间的距离在各种措施中使用的比较
RNA二级结构[ 55 ， 18 ] 。
让我们成为一个根深蒂固的树。我们呼吁Ť如果一标记树的每个节点是一个指定
标志由一个固定的有限字母？ 。我们呼吁Ť有序树如果左向右
为了兄弟姐妹之间的T给出。在本文中，我们考虑匹配问题
基于简单原始业务适用于标记的树木。如果T是一个有序
树这些行动的定义如下：
relabel更改标签的一个节点第五Ť 。
删除删除非根节点第五Ť家长V字，使儿童的V
成为孩子们的V ' 。这些儿童被插入的位置上第五
随后在左向右为了子女的V字。
插入补充删除。插入一个节点第五儿童的V '的T决策
五母公司连续子序列的儿童的V ' 。
图1说明了行动。树木为无序的行动可
同样的定义。在这种情况下，插入和删除操作的工程
子集，而不是子。我们确定三个问题的基础上修改
行动。让T1和T2标示树木（或无序排列） 。
树编辑距离假定我们会得到一个成本函数定义
每个编辑作业。修改脚本县之间的T1和T2是一个序列编辑
业务转向表＃ t1到时刻。成本S是一笔费用
行动由最优编辑脚本之间的T1和T2是一个编辑脚本
T1和T2之间的最低成本，这种成本是树编辑距离。那个
树编辑距离的问题是计算编辑距离和相应的
编辑脚本。
树排列距离假设我们会得到一个成本函数定义
关于对标签。的排列阿的T1和T2得到如下。首先，我们
插入标记节点舱进入T1和T2 ，使它们成为同构
当标签被忽略。由此产生的树木，然后overlayed顶部的每一
其他给予对齐阿，这是一种树的每个节点的标记
对标签。的费用是一笔费用都对对方的标签
答：在优化调整T1和T2是一个调整和最低的成本
这一费用被称为对准距离T1和T2 。对齐距离
问题是计算排列的距离和相应的调整。
树列入表＃ t1包含在T2当且仅当t1处理器可以同时得到
删除节点时刻。树列入问题是，以确定是否是表＃ t1
包括在T2 。
相关问答
Q1: 如何用Java实现树形结构啊？
package tree;
import java.util.LinkedList;
import java.util.List;
/**
* 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历
*
* 参考资料0:数据结构(C语言版)严蔚敏
*
* 参考资料1：
*
* 参考资料2：
*
* @author ocaicai@yeah.net @date: 2011-5-17
*
*/
public class BinTreeTraverse2 {
private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
private static ListNode nodeList = null;
/**
* 内部类：节点
*
* @author ocaicai@yeah.net @date: 2011-5-17
*
*/
private static class Node {
Node leftChild;
Node rightChild;
int data;
Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}
public void createBinTree() {
nodeList = new LinkedListNode();
// 将一个数组的值依次转换为Node节点
for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}
// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {
// 左孩子
nodeList.get(parentIndex).leftChild = nodeList
.get(parentIndex * 2 + 1);
// 右孩子
nodeList.get(parentIndex).rightChild = nodeList
.get(parentIndex * 2 + 2);
}
// 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
int lastParentIndex = array.length / 2 - 1;
// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList
.get(lastParentIndex * 2 + 1);
// 右孩子,如果数组的长度为奇数才建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList
.get(lastParentIndex * 2 + 2);
}
}
/**
* 先序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void preOrderTraverse(Node node) {
if (node == null)
return;
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
/**
* 中序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void inOrderTraverse(Node node) {
if (node == null)
return;
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
/**
* 后序遍历
*
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
*
* @param node
* 遍历的节点
*/
public static void postOrderTraverse(Node node) {
if (node == null)
return;
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}
public static void main(String[] args) {
BinTreeTraverse2 binTree = new BinTreeTraverse2();
binTree.createBinTree();
// nodeList中第0个索引处的值即为根节点
Node root = nodeList.get(0);
System.out.println("先序遍历：");
preOrderTraverse(root);
System.out.println();
System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();
System.out.println("后序遍历：");
postOrderTraverse(root);
}
}
Q2: 用java求最短路径问题，求源程序
import java.util.Vector;
public class Link {
private Vector link = new Vector();
// private Link next = null;
public Link() {
}
public boolean addNode(Node setNode){//增加一个节点
setNode = checkNode(setNode);
if(setNode != null){
this.link.addElement((Node)setNode);
return true;
}
return false;
}
public void delNode(Node setNode){ //删除一个节点
if(!this.link.isEmpty()){
for(int i=0;i this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
this.link.remove(i);
//System.out.println("asdfasdfas:"+this.link.size());
break;
}
}
}
}
public Node checkNode(Node setNode){//判断节点是否在链表里面并取得两者的最佳值
if(!this.link.isEmpty() setNode!=null){
for(int i=0;i this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
if(setNode.getStep() ((Node)this.link.elementAt(i)).getStep()){
setNode = (Node)this.link.elementAt(i);
this.link.remove(i);
}
else
return null;
break;
}
}
}
return setNode;
}
public boolean isEmpty(){
return this.link.isEmpty();
}
public Node getBestNode(){ //得到最好的节点
Node tmpNode = null;
if(!this.link.isEmpty()){
tmpNode = (Node)this.link.elementAt(0);
//System.out.println("tmpNodeStep:"+tmpNode.getStep());
//System.out.print("OpenNode(pos,step):");
for(int i=1;i this.link.size(); i++)
{
//System.out.print("("+((Node)this.link.elementAt(i)).getPos()+","+((Node)this.link.elementAt(i)).getStep()+")");
if(tmpNode.getJudgeNum() = ((Node)this.link.elementAt(i)).getJudgeNum()){
tmpNode = (Node)this.link.elementAt(i);
}
}
}
return tmpNode;
}
}
public class FindBestPath {
private char[][] map = null;//地图
private int maxX,maxY;//最大的地图边界大小
Node startNode = null;//入口
Node endNode = null;//出口
private int endX,endY;
/*初始化
*@param setMap 地图
*@param setX,setY 边界值
//////////*@param startNode 入口
//////////*param endNode 出口
*@param sX,sY:开始点
*@param eX,eY:结束点
*/
public FindBestPath(char[][] setMap,int setX,int setY,int sX,int sY,int eX,int eY) {
this.map = setMap;
this.maxY = setX - 1; //x,y互换
this.maxX = setY - 1; //x,y互换
//this.startNode = sNode;
//this.endNode = eNode;
Node sNode = new Node();
Node eNode = new Node();
sNode.setFarther(null);
sNode.setPos(posToNum(sX,sY));
sNode.setStep(0);
eNode.setPos(posToNum(eX,eY));
this.startNode = sNode;
this.endNode = eNode;
this.endX = eX;//numToX(eNode.getPos());
this.endY = eY;//numToY(eNode.getPos());
}
public int posToNum(int x,int y){//从xy坐标获得编号
return (x+y*(this.maxY+1));
}
public int numToX(int num){//从编号获得x坐标
return (num%(this.maxY+1));
}
public int numToY(int num){//从编号获得y坐标
return (int)(num/(this.maxY+1));
}
public boolean checkVal(int x,int y){//判断是否为障碍
//System.out.println("map["+x+"]["+y+"]="+map[x][y]);
if(this.map[x][y] == 'N')
return false;
else
return true;
}
public int judge(Node nowNode){//一定要比实际距离小
//System.out.println("nowNodePos:"+nowNode.getPos());
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
int distance = Math.abs((nowX-this.endX))+Math.abs((nowY-this.endY));
// System.out.println("distance:"+distance);
return distance;
}
public Node getLeft(Node nowNode){//取得左节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY 0){//判断节点是否到最左
if(checkVal(nowX,nowY-1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY-1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getRight(Node nowNode){//取得右节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY this.maxX){//判断节点是否到最左
if(checkVal(nowX,nowY+1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY+1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getTop(Node nowNode){//取得上节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX 0){//判断节点是否到最左
if(checkVal(nowX-1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX-1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getBottom(Node nowNode){//取得下节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX this.maxY){//判断节点是否到最左
if(checkVal(nowX+1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX+1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Link getBestPath(){//寻找路径
Link openLink = new Link();//没有访问的路径
Link closeLink = new Link();//访问过的路径
Link path = null;//最短路径
Node bestNode = null;
Node tmpNode = null;
openLink.addNode(this.startNode);
while(!openLink.isEmpty())//openLink is not null
{
bestNode = openLink.getBestNode();//取得最好的节点
//System.out.println("bestNode:("+numToX(bestNode.getPos())+","+numToY(bestNode.getPos())+")step:"+bestNode.getJudgeNum());
if(bestNode.getPos()==this.endNode.getPos())
{
/*this.endNode.setStep(bestNode.getStep()+1);
this.endNode.setFarther(bestNode);
this.endNode.setJudgeNum(bestNode.getStep()+1);*/
path = makePath(bestNode);
break;
}
else
{
tmpNode = closeLink.checkNode(getLeft(bestNode));
if(tmpNode != null)
//System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getRight(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getTop(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getBottom(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
openLink.delNode(bestNode);
closeLink.addNode(bestNode);
}
}
return path;
}
public Link makePath(Node lastNode){//制造路径
Link tmpLink = new Link();
Node tmpNode = new Node();
int x,y;
tmpNode = lastNode;
if(tmpNode != null){
do{
x=numToX(tmpNode.getPos());
y=numToY(tmpNode.getPos());
System.out.println("map["+x+"]["+y+"]="+map[x][y]);
tmpLink.addNode(tmpNode);
tmpNode = tmpNode.getFarther();
}while(tmpNode != null);
}else
{
System.out.println("Couldn't find the path!");
}
return tmpLink;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
char[][] map ={
{'Y', 'N', 'z', 'y', 'x', 'w', 'v', 'N', 'N', 'N'},
{'Y', 'N', '1', 'N', 'N', 'N', 'u', 't', 'N', 'N'},
{'N', '1', '2', '1', '1', '1', 'N', 's', 'N', 'N'},
{'N', 'N', '1', 'N', '9', 'N', 'q', 'r', 'N', 'N'},
{'N', 'N', '1', 'N', 'n', 'o', 'p', 'N', 'N', 'N'},
{'N', '4', '5', '6', 'm', 'N', 'N', 'N', 'N', 'N'},
{'N', '3', 'N', '5', 'l', 'k', 'j', 'N', 'N', 'N'},
{'N', 'N', '3', '4', 'N', 'd', 'i', 'd', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'h', 'N', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'g', 'N', 'N', 'N'},
{'N', 'a', 'b', 'c', 'd', 'e', 'f', 'N', 'N', 'N'}
};
/*map[x][y]
*如上所示：maxY=10 maxX=11 横的代表maxY,竖的代表maxX 可以自己替换
*地图的读取是
*for(i=1;i行的最大值;i++)
* for(j=1;j列的最大值;j++)
* map[i][j] = 地图[i][j]
*/
Link bestPath = new Link();
/*startNode.setFarther(null);
startNode.setPos(21);
startNode.setStep(0);
//endNode.setFarther(startNode);
endNode.setPos(79);
//endNode.setStep(0);*/
FindBestPath path = new FindBestPath(map, 11, 10, 10, 1, 0, 2);
//FindBestPath path = new FindBestPath(map, 11, 10, startNode, endNode);
bestPath = path.getBestPath();
//bestPath.printLink();
}
}
public class Node {
private int step;//从入口到该节点经历的步数
private int pos;//位置
private Node farther;//上一个结点
private int judgeNum;
public Node() {
}
public void setStep(int setStep){
this.step = setStep;
}
public int getStep(){
return this.step;
}
public void setPos(int setPos){
this.pos = setPos;
}
public int getPos(){
return this.pos;
}
public void setFarther(Node setNode){
this.farther = setNode;;
}
public Node getFarther(){
return this.farther;
}
public void setJudgeNum (int setInt){
this.judgeNum = setInt;;
}
public int getJudgeNum(){
return this.judgeNum;
}
}
Q3: 2-3-4树的问题
定义
一棵 2-3 树必须符合下列几项定义：
(1) 2-3 tree 中的节点可以存放一笔或两笔资料。
(2) 若节点中存放了一笔资料 Ldata.key ，其必须存在两个子节点-左子节点与中子节点。
假设资料 Ldata 的键值为 Ldata.key ，则：
(a) 左子节点所存放的资料键值必须小於 Ldata.key 。
(b) 中子节点存放的资料键值必须大於 Ldata.key 。
(3) 若节点中存放了两笔资料 Ldata 与 Rdata ，则会存在三个子节点-左子节点、中子节点与右
子节点。
假设资料 Ldata 、Rdata 的键值分别为 Ldata.key 与 Rdata.key，则：
(a) Ldata.key Rdata.key 。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 中子节点所存放的资料键值必须大於 Ldata.key 和小於 Rdata.key 。
(d) 右子节点所存放的资料键值必须大於 Rdata.key 。
(4) 树中的所有树叶节点必须为同一阶度 ( Level ) 。
特性
(1) 有 n 个元素的 2-3 tree 之高度介於 [ log3( n+1 ) ] 和 [ log2( n+1 ) ]。
(2) 在高度为 h 的 2-3 tree 中，元素的个数介於 2h - 1 到 3h - 1 。
(3) 在 n 个元素的 2-3 tree 中，插入和删除需要时间为 O( log n ) 。
2-3 tree 加入的方法
由 2-3 tree 中开始搜寻，假如加入的资料键值在 2-3 tree 中找不到，则加入 2-3 tree 中，假设
加入的节点
1、该节点只有一笔资料，则直接加入。如下例
2、该节点已存在资料，则将此节点一分为二。如下例
2-3 tree 的删除方法
2-3 tree 的删除分为两个部份：一为树叶节点 ( leaf node ) ，另一为非树叶节点 ( non-leaf node
) 。
(1) 若删除的节点是树叶节点
(a) 若节点的键值删除后，还有其它的键值存在，则直接删除。如下例：
(b) 若节点的键值删除后，已经没有其他的键值存在，则须调整。如下例：
(2) 若删除的节点是非树叶节点
假设欲删除的键值 x 为非树叶节点，此时须找一节点 p' ( 当 x 为节点的左边键值，p' 存在
於该节点的中子树 ; 若为右边键值，则 p' 存在於右子树 ) ，此 p' 必需是树叶点，在 p' 中找
一个最小值 y ( y 为 p' 的左边键值 ) ，将 y 值代替 x 值。
2-3-4 树 ( 2-3-4 tree )
定义
2-3-4 tree 为 2-3 tree 的观念扩充，一棵 2-3-4 tree 须符合下列定义：
(1) 2-3-4 tree 中的节点可以存放一笔、两笔或三笔资料。
(2) 若节点中存放了一笔资料 Ldata ，其必须存在两个子节点-左子节点与左中子节点。
假设资料 Ldata 的键值为 Ldata.key 则
(a) 左子节点所存放的资料键值必须小於 Ldata.key 。
(b) 左中子节点所存放的资料键值必须大於 Ldata.key 。
(3) 若节点中存放二笔资料键值 Ldata 和 Mdata ，则会存在三个子节点-左子节点、左中子节
点与右中子节点。
假设资料 Ldata 的键值为 Ldata.key , Mdata 的键值为 Mdata.key 则
(a) Ldata.key Mdata.key。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 左中子节点所存放的资料键值必须大於 Ldata.key , 小於 Mdata.key。
(d) 右中子节点所存放的资料键值必须大於 Mdata.key 。
(4) 若节点中存放三笔资料键值 Ldata 、 Mdata 与 Rdata ，则会存在四个子节点 - 左子节点、
左中子节点、右中子节点与右子节点。
假设资料 Ldata 、Mdata 与 Rdata 的键值分别为 Ldata.key 、Mdata.key 与 Rdata.key 则
(a) Ldata.key Mdata.key Rdata.key 。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 左中子节点所存放的资料键值必须大於 Ldata.key , 小於 Mdata.key。
(d) 右中子节点所存放的资料键值必须大於 Mdata.key ,小於 Rdata.key。
(e) 右子节点所存放的资料键值必须大於 Rdata.key 。
(5) 所有的叶节点必须在同一阶度 ( Level ) 。
特性
(1) 有 n 个元素的 2-3-4 tree ，其高度介於 ┌ log4(n+1) ┐和 ┌ log2(n+1) ┐。
(2) 在 n 个元素的 2-3-4 tree 中，插入和删除需要时间为 O( logn ) 。
红-黑树 ( Red-Black tree )
红-黑树 ( Red-Black tree ) 是 2-3-4 tree 的一种二元树表示法。
定义
(1) 红-黑树为一棵二元搜寻树 ( binary search tree ) 。
(2) 由树根节点到任何一个树叶节点，其所经过的黑色链结数目都是相同的。
(3) 由树根节点到任何一个树叶节点，其所经过的路径不会连续出现两条红色的链结。
特性
(1) 在红-黑树中有一个很重要的特性-子节点分为黑与红两种，黑色代表实际的链结，红色代表
原本不存在的链结。
简而言之，在 Red-Black tree 中，红线链结的节点，在 2-3-4 tree 中为同一节点。如上图所示
。
(2) 每一个有 n 个(内部)节点的红-黑树RB满足下列各式：
(a) hight(RB) = 2┌ log2(n+1) ┐
(b) hight(RB) = 2 rank(RB)
(c) rank(RB) = ┌ log2(n+1) ┐
(3) 资料的插入，其所需的时间复杂度为 O( log n ) 。
如果对您有帮助，请记得采纳为满意答案，谢谢！祝您生活愉快！
vaela
关于树编辑距离java代码和java编写树形结构的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
