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

Question

可以将一个二叉树以若干条记录的形式存入数据库中。
每条记录可以记为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

Answer 1

定义一个结点类：
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<String, Integer> map = new HashMap<String, Integer>();
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<String, Integer> 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());
}
}

Answer 2

先序遍历 按  根节点， 左子树 右子树 的顺序遍历。

这是以前写的示例，可以参考一下

本回答被网友采纳