在Java中切片树 [英] slicing tree in java
问题描述
你好，
我想问一下能否给我一些帮助.
我必须实现代表切片平面图的切片树.
(切片平面图将水平和垂直切口划分为一个矩形，并且可以用称为切片树的二叉树表示.其内部节点是切口，外部节点是通过切口将平面图分解成的基本矩形. )
我应该解决压实问题，即为切片平面图的每个矩形找到与基本矩形的最小尺寸兼容的最小可能的高度和宽度.
此问题与Goodrich和Tamassia数据结构和算法手册，第4版，第444-445页类似.
w(v)= w-如果v是外部节点，其基本矩形的权重为w.
w(v)= max(w(w)，w(z))如果v是与带有左子级w和右子级z的水平切割关联的内部节点.
w(v)= w(w)+ w(z)-如果v是与具有左子级w和右子级z的垂直切割关联的内部节点.
h(v)= h-如果v是其基本矩形的最小高度为h的外部节点.
h(v)= h(w)+ h(z)-如果v是与具有左子级w和右子级z的水平切割关联的内部节点.
h(v)= max(h(w)，h(z))，如果v是与带有左子级w和右子级z的垂直切割关联的内部节点.
因此，我编写了一个驱动程序(FileRead.java)，该程序创建SlicingTree类的实例，并按如下所示逐步构造树.
它从文件test.txt中读取指令，并且每一行都指示要在树上执行的操作.每行只有一个指令.
每个指令均由指令名称组成，后跟0个或多个参数，并用Tab分隔.以下是可能的指令及其含义
create-root L//创建树的根并将其标记为L
cut-h L LC LR//通过水平切割将标记为L的节点分为两部分，
//将下(left)子项标记为LC，将下(right)子项标记为LR
cut-v L LC LR//用竖线将标记为L的节点一分为二
//剪切，将左子项标记为LC，将右子项标记为LR
Assign-w L x//将标记为L的节点的宽度设置为x
Assign-h L x//将标记为L的节点的高度设置为x compact
//在树形显示器上执行压缩算法，如上所述显示树
退出//这是最后一条指令
另外，我编写了SlicingTree.java，在其中定义了切片树的类.它编译没有错误.
当我编译FileRead.java时，出现如下错误:无法找到符号；符号类STNode，位置类FileRead和"FileRead中的cut_horizontal(STNode)无法应用于()cut_horizontal();"
================================================== ========
Hello,
I would like to ask if you can give me some help.
I have to implement a slicing tree that represent a slicing floorplan.
(A slicing floorplan divides a rectangle with horizontal and vertical cuts, and can be represented by a binary tree, called slicing tree. Its internal nodes are the cuts, and external nodes are the basic rectangles into which the floorplan is decomposed by the cuts.)
I should solve the compaction problem, i.e. to find the smallest possible height and width for each rectangle of the slicing floorplan that is compatible with the minimum dimensions of the basic rectangles.
This problem is similar with Goodrich and Tamassia Data Structures and algorithmts book, 4th edition, page 444-445.
w(v) = w -if v is an external node whose basic rectangle has minimum weight w.
w(v)= max(w(w),w(z)) if v is an internal node associated with a horizontal cut with left child w and right child z.
w(v) = w(w) + w(z) -if v is an internal node associated with a vertical cut with left child w and right child z.
h(v) = h -if v is an external node whose basic rectangle has minimum height h.
h(v) =h(w) + h(z) -if v is an internal node associated with a horizontal cut with left child w and right child z.
h(v) = max(h(w), h(z)) if v is an internal node associated with a vertical cut with left child w and right child z.
So, I have written a driver program (FileRead.java), which creates an instance of a SlicingTree class, and gradually constructs the tree as follows.
It reads directives from the file test.txt, and each line indicate an operation to be performed on the tree. There is one directive per line.
Each directive consists of the name of the directive followed by 0 or more arguments, separated by tab. Here are the possible directives and their meanings
create-root L //create the root of the tree and label it as L
cut-h L LC LR //divide the node labeled L into two by a horizontal cut,
//label bottom(left) child as LC, label top(right) child as LR
cut-v L LC LR //divide the node labeled L into two by a vertical
//cut, label the left child as LC, label the right child as LR
assign-w L x //set the width of the node labeled as L to x
assign-h L x //set the height of the node labeled as L to x compact
//Perform the compaction algorithm on the tree display Display the tree as described above
quit //this is the last directive
Also, I have written the SlicingTree.java, where I defined the class for slicing tree. It compiles without errors.
When I compile FileRead.java, I have errors like: cannot find symbol; symbol class STNode, location class FileRead and "cut_horizontal (STNode) in FileRead cannot be applied to () cut_horizontal();"
==========================================================
//FileRead.java for slicing tree
import java.io.*;
import java.util.*;
class FileRead
{
public static int create_root()
{
return 0;
}
public static int cut_horizontal(STNode v)
{
return 0;
}
public static int cut_vertical(STNode v)
{
return 0;
}
public static int assign_width(STNode v, int width)
{
return 0;
}
public static int assign_height(STNode v, int height)
{
return 0;
}
public static int assign_label(STNode v, char label)
{
return 0;
}
public static int compact()
{
return 0;
}
public static int display()
{
return 0;
}
public static void main(String[] args)
{
//Open the file that is the first command line parameter
FileInputStream fstream = new FileInputStream("test.txt");
//get the object of DataInpjutStream
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
//read file line by line
while((strLine = br.readLine()) != null)
{
//print the content on the console
System.out.println(strLine);
if(strLine == "create-root L ")
{
create_root();
}
if(strLine == "create-root L ")
{
create_root();
}
if(strLine == "cut-h L LC LR ")
{
cut_horizontal();
}
if(strLine == "cut-v L LC LR")
{
cut_vertical();
}
if(strLine == "assign-w L X")
{
assign_width();
}
if(strLine == "assign-h L X")
{
assign_height();
}
if(strLine == "compact")
{
compact();
}
if(strLine == "display")
{
display();
}
if(strLine == "quit")
{
quit();
}
//close the input stream
in.close();
}
}
}
=========================================
<code></code>
//SlicingTree.java
import java.io.IOException;
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
//Class for a slicing tree that stores Object objects.
public class SlicingTree
{
/** Class to encapsulate a tree node. */
protected static class STNode
{
// Data Fields
/** The information stored in this node. */
protected Object data;
/** Reference to the left child. */
protected STNode left;
/** Reference to the right child. */
protected STNode right;
// Constructors
//Construct a node with given data and no children.
//param data The data to store in this node
public STNode(Object data)
{
this.data = data;
left = null;
right = null;
}
// Methods
/** Return a string representation of the node.
@return A string representation of the data fields
*/
public String toString()
{
return data.toString();
}
}
// Data Field
/** The root of the slicing tree */
protected STNode root;
public SlicingTree()
{
root = null;
}
protected SlicingTree(STNode root)
{
this.root = root;
}
/** Constructs a new slicing tree with data in its root,
leftTree as its left subtree and rightTree as its
right subtree.
*/
public SlicingTree(Object data, SlicingTree leftTree, SlicingTree rightTree)
{
root = new STNode(data);
if (leftTree != null) {
root.left = leftTree.root;
}
else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
}
else {
root.right = null;
}
}
//Return the left subtree.
//return The left subtree or
// null if either the root or the
// left subtree is null
public SlicingTree getLeftSubtree()
{
if (root != null && root.left != null)
{
return new SlicingTree(root.left);
}
else
{
return null;
}
}
//Return the right sub-tree
//return the right sub-tree or
// null if either the root or the
// right subtree is null.
public SlicingTree getRightSubtree()
{
if (root != null && root.right != null)
{
return new SlicingTree(root.right);
}
else {
return null;
}
}
//Determine whether this tree is a leaf.
//return true if the root has no children
boolean isLeaf()
{
return (root.left == null && root.right == null);
}
public String toString()
{
StringBuffer sb = new StringBuffer();
preOrderTraverse(root, 0, sb);
return sb.toString();
}
//Perform a preorder traversal.
// @param node The local root
// @param depth The depth
// @param sb The string buffer to save the output
private void preOrderTraverse(STNode node, int depth, StringBuffer sb)
{
for (int i = 0; i < depth; i++)
{
sb.append(" ");
}
if (node == null)
{
sb.append("null\n");
}
else
{
sb.append(node.toString());
sb.append("\n");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}
//Method to read a slicing tree.
//pre: The input consists of a preorder traversal
// of the slicing tree. The line "null" indicates a null tree.
// @param bR The input file
// @return The binary tree
// @throws IOException If there is an input error
public static SlicingTree readSlicingTree (BufferedReader bR) throws IOException {
// Read a line and trim leading and trailing spaces.
String data =bR.readLine().trim();
if (data.equals("null"))
{
return null;
}
else
{
SlicingTree left = readSlicingTree(bR);
SlicingTree right = readSlicingTree(bR);
return new SlicingTree(data, left, right);
}
}
//Return the data field of the root
// @return the data field of the root
// or null if the root is null
public Object getData()
{
if (root != null)
{
return root.data;
}
else
{
return null;
}
}
}
推荐答案
您需要导入该类(因为它是内部类)或将其引用为SlicingTree.STNode.
如果您的软件包名为mypackage，则导入应为:
You need to either import the class as it is a internal class or reference it asSlicingTree.STNode.
If your package is calledmypackagethen the import should be:
import mypackage.SlicingTree.STNode;
这篇关于在Java中切片树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
