java一个关于二叉树的简单编程题

可以将一个二叉树以若干条记录的形式存入数据库中。每条记录可以记为a Lb或者a Rb；a表示当前结点，Lb表示该结点为b的左子，Rb表示该结点为b的右子；a、b均为结点的编号（结点编号是正整数，并且是唯一的）。根结点用a #表示。如图所示二叉树可以用以下四条...可以将一个二叉树以若干条记录的形式存入数据库中。
每条记录可以记为a Lb或者a Rb；a表示当前结点，Lb表示该结点为b的左子，Rb表示该结点为b的右子；a、b均为结点的编号（结点编号是正整数，并且是唯一的）。根结点用a #表示。
如图所示二叉树可以用以下四条记录表示（记录是无序的）：

要求：给定一组这样的记录，求对应二叉树的前序遍历序列。
输入：输入为若干行。第一行的正整数N表示二叉树结点的个数。后续的N行为N条记录（对应N个结点）。
输出：输出二叉树的前序遍历序列（输出每个结点的编号，编号之间用逗号隔开）。
例如：
输入
5
9 L18
6 R18
39 #
18 R39
7 L39
输出
39,7,18,9,6
展开

emily_gfl · 2018-4-30 01:57:57

定义一个结点类：
public class Node {
private int value;
private Node leftNode;
private Node rightNode;

public Node getRightNode() {
  return rightNode;
}
public void setRightNode(Node rightNode) {
  this.rightNode = rightNode;
}
public int getValue() {
  return value;
}
public void setValue(int value) {
  this.value = value;
}
public Node getLeftNode() {
  return leftNode;
}
public void setLeftNode(Node leftNode) {
  this.leftNode = leftNode;
}

}

初始化结点树：
public void initNodeTree()
{
  int nodeNumber;
  HashMap map = new HashMap();
  Node nodeTree = new Node();

  Scanner reader = new Scanner(System.in);

  nodeNumber = reader.nextInt();
  for(int i = 0; i < nodeNumber; i++) {
int value = reader.nextInt();
String str = reader.next();
map.put(str, value);
  }

  if (map.containsKey("#")) {
int value = map.get("#");
nodeTree.setValue(value);
setChildNode(map, value, nodeTree);
  }

  preTraversal(nodeTree);
}

private void setChildNode(HashMap map, int nodeValue, Node parentNode) {
  int value = 0;
  if (map.containsKey("L" + nodeValue)) {
value = map.get("L" + nodeValue);
Node leftNode = new Node();
leftNode.setValue(value);
parentNode.setLeftNode(leftNode);

setChildNode(map, value, leftNode);
  }

  if (map.containsKey("R" + nodeValue)) {
value = map.get("R" + nodeValue);
Node rightNode = new Node();
rightNode.setValue(value);
parentNode.setRightNode(rightNode);

setChildNode(map, value, rightNode);
  }
}

前序遍历该结点树：
public void preTraversal(Node nodeTree) {
  if (nodeTree != null) {
System.out.print(nodeTree.getValue() + "\t");
preTraversal(nodeTree.getLeftNode());
preTraversal(nodeTree.getRightNode());
  }
}

幸福专卖店8888 · 2018-4-30 01:57:58

先序遍历按聽根节点，左子树右子树的顺序遍历。
这是以前写的示例，可以参考一下

java一个关于二叉树的简单编程题

2 个回复