java - 打印树的最小和路径
问题描述
我有一个代码可以计算我创建的树的最小总和路径。
我的树类是这样的:
import java.util.LinkedList;
import java.util.Queue;
public class SolutionTree {
SolutionNode root;
public SolutionTree() {
root = null;
}
public void addRoot(int rootValue) {
root = new SolutionNode(rootValue);
}
// New Node Adder
public void addSolutionNode(int newNodeValue) {
SolutionNode newNode = new SolutionNode(newNodeValue);
SolutionNode newNodeRoot = breadth(root);
if(newNodeRoot.getChildLeft() == null) {
newNodeRoot.setChildLeft(newNode);
newNode.setParentLeft(newNodeRoot);
}
else if(newNodeRoot.getChildRight() == null) {
newNodeRoot.setChildRight(newNode);
newNode.setParentLeft(newNodeRoot);
if(newNodeRoot != root) {
if(newNodeRoot.getParentLeft().getChildRight().getChildLeft() == null) {
newNodeRoot.getParentLeft().getChildRight().setChildLeft(newNode);
newNode.setParentRight(newNodeRoot.getParentLeft().getChildRight());
}
}
}
}
// Node Class of Solution Tree
protected class SolutionNode {
private int value;
private SolutionNode parentLeft;
private SolutionNode parentRight;
private SolutionNode childLeft;
private SolutionNode childRight;
// Constructor
public SolutionNode() {
value = 0;
parentLeft = null;
parentRight = null;
childLeft = null;
childRight = null;
}
// Constructor
public SolutionNode(int v) {
value = v;
parentLeft = null;
parentRight = null;
childLeft = null;
childRight = null;
}
// MODIFIERS
public void setValue(int val) {
value = val;
}
public void setParentLeft(SolutionNode leftParent) {
parentLeft = leftParent;
}
public void setParentRight(SolutionNode rightParent) {
parentLeft = rightParent;
}
public void setChildLeft(SolutionNode leftChild) {
childLeft = leftChild;
}
public void setChildRight(SolutionNode rightChild) {
childRight = rightChild;
}
//ACCESSORS
public int getValue() {
return value;
}
public SolutionNode getParentLeft() {
return parentLeft;
}
public SolutionNode getParentRight() {
return parentRight;
}
public SolutionNode getChildLeft() {
return childLeft;
}
public SolutionNode getChildRight() {
return childRight;
}
}
// function to compute the minimum sum path
// It only returns the sum of the values of nodes on the min sum path
int minSumPath(SolutionNode current) {
if(current == null)
return 0;
int sum = current.getValue();
int left_sum = minSumPath(current.childLeft);
int right_sum = minSumPath(current.childRight);
if(left_sum <= right_sum) {
sum += minSumPath(current.childLeft);
}
else {
sum += minSumPath(current.childRight);
}
return sum;
}
// Breadth First Traversal
public static SolutionNode breadth(SolutionNode root) {
Queue<SolutionNode> queue = new LinkedList<SolutionNode>() ;
if (root == null)
return null;
queue.clear();
queue.add(root);
while(!queue.isEmpty()){
SolutionNode node = queue.remove();
if(node.childLeft != null)
queue.add(node.childLeft);
if(node.childRight != null)
queue.add(node.childRight);
if(node.childLeft == null || node.childRight == null)
return node;
}
return null;
}
}
我有一个程序,它从 .txt 文件中读取整数并添加到解决方案树并计算树的最小总和路径(从根到叶节点(节点值的总和))。通过调用 SolutionTree 的 minSumPath 方法。
我想打印计算出的路径。例如,如果树是:
1
2 3
4 5 6
最小和路径是 7,它是通过求和 1 + 2 + 4 来计算的。我想打印这个过程。有什么想法我该怎么做?我将不胜感激任何帮助。
提前致谢。
解决方案
而不是在递归方法中返回一个 int,您应该返回一个类,该类包含您传递的节点的总和和字符串。
此代码应该适合您:
public class number{
private int sum;
private String str;
// CONSTRUCTOR
public number(int sum, String str){
this.sum=sum;
this.str=str;
}
public void add(int sum2){
sum+=sum2;
if(!str.equals(""))
str = str +" + "+ sum2;
else if(str.equals(""))
str = "" + sum2;
}
// ACCESSORS
public String getStr() {
return this.str;
}
public int getSum() {
return this.sum;
}
// MODIFIERS
public void setStr(String newStr) {
this.str = newStr;
}
public void setSum(int newSum) {
this.sum = newSum;
}
}
// function to compute the minimum sum path
// It only returns the sum of the values of nodes on the min sum path
number minSumPath(SolutionNode current) {
number tr1= new number(0,"");
if(current == null){
return tr1;
}
int sum = current.getValue();
int left_sum = minSumPath(current.childLeft).sum;
int right_sum = minSumPath(current.childRight).sum;
if(left_sum <= right_sum) {
tr1= minSumPath(current.childLeft);
tr1.add(sum);
}
else {
tr1= minSumPath(current.childLeft);
tr1.add(sum);
}
return tr1;
}
推荐阅读
- oracle - 如何在oracle中禁用序列
- ruby-on-rails - 在rails 5中刷新时缓存未保存的表单数据的最佳方法
- r - 如何防止用户直接通过 URL 访问 R Shiny 应用程序?
- node.js - BodyParser 给出一个空对象
- android - 如何使android上的吐司出现直到用户触摸屏幕?
- hibernate - HQL查询如何返回实体?
- perl - 如何使用 IO::Socket::SSL 获取我自己的服务器 IP 地址
- ffmpeg - 使用 ffmpeg 命令在视频中添加多个元数据
- postgresql - Postgres docker实例在重启后不会保持状态
- javascript - 折线图路径中不必要的间隙