使用递归绘制树

Question

我正在尝试使用递归绘制一棵树。树需要看起来像这样：

关于我应该如何做的简短总结：

树干的长度为 length，宽度为 width
树干分成两个树枝
左边是躯干长度的3/4，右边是躯干长度的2/3
左分支宽度是树干宽度的3/4，右分支宽度是树干宽度的1/2
我们收到的参数是长度，min_length，宽度，alpha（所有双精度）
枝条长到比min_length

这是我解决问题的方法。我只想画树干，左分支和右分支。我设法做到了这一点，具有以下功能：

public void drawTree(double length, double min_length, double width, double alpha) {
        //Draws the trunk of the tree
        StdDraw.setPenRadius(width);
        StdDraw.line(250, 150, 250, 150+length);        

        //Left branch
        double hypotenuse = (3.0/4.0)*length;
        double opposite = Math.sin(alpha) * hypotenuse;
        double adjacent = Math.sqrt(Math.pow(hypotenuse, 2)-Math.pow(opposite, 2));
        StdDraw.setPenRadius(width*3.0/4.0);
        StdDraw.line(250,150+length,250-adjacent,150+length+opposite);

        //Right branch
        double hypotenuse2 = (2.0/3.0)*length;
        double opposite2 = Math.sin(alpha) * hypotenuse2;
        double adjacent2 = Math.sqrt(Math.pow(hypotenuse2, 2)-Math.pow(opposite2, 2));
        StdDraw.setPenRadius(width*1.0/2.0);
        StdDraw.line(250,150+length,250+adjacent2,150+length+opposite2);       

    }

这是输出，正如我想要的那样：

我以为剩下的会很容易，但在过去的 3 小时里我没有取得任何进展:/。我包括了停止条件的 if 语句。但是我对递归部分一无所知。我试过这个：

if (length > min_length) {
    //Left branch
    double hypotenuse = (3.0/4.0)*length;
    double opposite = Math.sin(alpha) * hypotenuse;
    double adjacent = Math.sqrt(Math.pow(hypotenuse, 2)-Math.pow(opposite, 2));
    StdDraw.setPenRadius(width*3.0/4.0);
    StdDraw.line(250,150+length,250-adjacent,150+length+opposite);
    //Right branch
    double hypotenuse2 = (2.0/3.0)*length;
    double opposite2 = Math.sin(alpha) * hypotenuse2;
    double adjacent2 = Math.sqrt(Math.pow(hypotenuse2, 2)-Math.pow(opposite2, 2));
    StdDraw.setPenRadius(width*1.0/2.0);
    StdDraw.line(250,150+length,250+adjacent2,150+length+opposite2);
    //My first attempt
    drawTree(hypotenuse*hypotenuse, min_length, width, alpha);
    drawTree(hypotenuse2*hypotenuse2, min_length, width, alpha);
    //My second attempt
    drawTree(hypotenuse, min_length, width, alpha);
    drawTree(hypotenuse2, min_length, width, alpha);       
}

我理解简单的递归，如阶乘、回文等，但我仍然坚持这一点，非常感谢任何帮助。

Answer 1

你的 drawTree() 太复杂了。调用它 drawTrunk 并只绘制树的树干。然后创建一个 drawTree 例程，如下所示：

drawTree(basePoint, length, width, angle)
  if length > min_length
    drawTrunk(length, width, angle)
    newBasePoint = top of trunk
    drawTree(newBasePoint, 3/4. * length, 3/4. * width, angle + 45)
    drawTree(newBasePoint, 2/3. * length, 2/3. * width, angle - 45)

Answer 2

正如评论和当前答案中已经指出的那样，使 drawTree 方法与当前绘制树的哪一部分无关是至关重要的。

您不能在此方法中使用绝对坐标。而且您必须跟踪 您当前所在的位置 。例如，这可以通过将 Point2D 传递给描述当前树部分起点的递归方法来完成。

您甚至不需要明确的代码来绘制分支：请注意，单行已经是一棵树。然后分支只是 "smaller trees"：它们又是单行，但长度和宽度不同。

（而且相对于之前的树有一定的角度。你没说这个，但是根据截图的角度好像是Math.PI / 5）

import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.RenderingHints;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.function.DoubleConsumer;

import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.SwingUtilities;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class RecursiveTreeDrawing
{
    public static void main(String[] args) 
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }    

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new BorderLayout());

        RecursiveTreeDrawingPanel p = new RecursiveTreeDrawingPanel();
        p.setPreferredSize(new Dimension(500,500));
        f.getContentPane().add(p, BorderLayout.CENTER);

        JPanel c = new JPanel(new GridLayout(0,1));

        c.add(createControl("left length", 0, 0.9, 
            d -> p.setLeftLengthFactor(d)));
        c.add(createControl("left width", 0, 0.9, 
            d -> p.setLeftWidthFactor(d)));
        c.add(createControl("left angle", 0, Math.PI, 
            d -> p.setLeftAngleDelta(d)));

        c.add(createControl("right length", 0, 0.9, 
            d -> p.setRightLengthFactor(d)));
        c.add(createControl("right width", 0, 0.9, 
            d -> p.setRightWidthFactor(d)));
        c.add(createControl("right angle", -Math.PI, 0, 
            d -> p.setRightAngleDelta(d)));
        f.getContentPane().add(c, BorderLayout.SOUTH);

        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private static JPanel createControl(
        String name, double min, double max, DoubleConsumer doubleConsumer)
    {
        JPanel p = new JPanel(new GridLayout(1,0));
        p.add(new JLabel(name));
        JSlider slider = new JSlider(0, 100, 0);
        slider.addChangeListener(new ChangeListener()
        {

            @Override
            public void stateChanged(ChangeEvent e)
            {
                int value = slider.getValue();
                double v = value / 100.0;
                double d = min + v * (max - min);
                doubleConsumer.accept(d);
            }
        });
        p.add(slider);

        return p;
    }

}


class RecursiveTreeDrawingPanel extends JPanel
{
    private double leftLengthFactor = 3.0 / 4.0;
    private double leftWidthFactor = 3.0 / 4.0;
    private double leftAngleDelta = Math.PI / 5.0;
    private double rightLengthFactor = 2.0 / 3.0;
    private double rightWidthFactor = 1.0 / 2.0;
    private double rightAngleDelta = - Math.PI / 5.0; 

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;
        g.setColor(Color.BLACK);
        g.fillRect(0,0,getWidth(),getHeight());
        g.setRenderingHint(
            RenderingHints.KEY_ANTIALIASING, 
            RenderingHints.VALUE_ANTIALIAS_ON);
        Point2D start = new Point2D.Double(
            getWidth() * 0.5, 
            getHeight() * 0.7);
        g.setColor(Color.GRAY);
        drawTree(g, start, 100.0, 2.0, 10.0, 0);
    }

    private void drawTree(Graphics2D g, 
        Point2D start, double length, double minLength, 
        double width, double alpha)
    {
        if (length < minLength)
        {
            return;
        }
        g.setStroke(new BasicStroke((float)width, 
            BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
        Point2D end = new Point2D.Double(
            start.getX() + Math.sin(alpha + Math.PI) * length,
            start.getY() + Math.cos(alpha + Math.PI) * length);
        g.draw(new Line2D.Double(start, end));
        drawTree(g, end, length * leftLengthFactor, minLength, 
            width * leftWidthFactor, alpha + leftAngleDelta);
        drawTree(g, end, length * rightLengthFactor, minLength, 
            width * rightWidthFactor, alpha + rightAngleDelta);
    }

    public void setLeftLengthFactor(double leftLengthFactor)
    {
        this.leftLengthFactor = leftLengthFactor;
        repaint();
    }

    public void setLeftWidthFactor(double leftWidthFactor)
    {
        this.leftWidthFactor = leftWidthFactor;
        repaint();
    }

    public void setLeftAngleDelta(double leftAngleDelta)
    {
        this.leftAngleDelta = leftAngleDelta;
        repaint();
    }

    public void setRightLengthFactor(double rightLengthFactor)
    {
        this.rightLengthFactor = rightLengthFactor;
        repaint();
    }

    public void setRightWidthFactor(double rightWidthFactor)
    {
        this.rightWidthFactor = rightWidthFactor;
        repaint();
    }

    public void setRightAngleDelta(double rightAngleDelta)
    {
        this.rightAngleDelta = rightAngleDelta;
        repaint();
    }

}

使用递归绘制树

Drawing a tree using recursion

java

recursion

stddraw