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

论坛 期权论坛 期权     
匿名   2018-4-26 13:56   2876   2
可以将一个二叉树以若干条记录的形式存入数据库中。每条记录可以记为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
展开

分享到 :
0 人收藏

2 个回复

倒序浏览
2#
emily_gfl  1级新秀 | 2018-4-30 01:57:57 发帖IP地址来自
定义一个结点类:
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());
  }
}
3#
幸福专卖店8888  1级新秀 | 2018-4-30 01:57:58 发帖IP地址来自
先序遍历 按 聽根节点, 左子树 右子树 的顺序遍历。
这是以前写的示例,可以参考一下
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:58388
帖子:6688
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP