97. 二叉排序树
时间限制 1000 ms 内存限制 65536 KB
题目描述
二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：
- 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；
- 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；
- 左、右子树本身也是一颗二叉排序树。
现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
输入格式
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过108。
输出格式
输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值
输入样例
5
2 5 1 3 4输出样例
-1
2
2
5
3不是很难的题但确实体现了北邮爱考树相关的编程题，从历年的初试题也能看得出来。
用类表示节点，在节点内部定义父节点。
用节点数组按输入顺序存储节点。
在递归创建二叉排序树的时候，记录父节点。
package test;
import java.io.BufferedInputStream;
import java.util.Scanner;
class NODE1{
int value;
NODE1 father;
NODE1 left;
NODE1 right;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public NODE1 getFather() {
return father;
}
public void setFather(NODE1 father) {
this.father = father;
}
public NODE1 getLeft() {
return left;
}
public void setLeft(NODE1 left) {
this.left = left;
}
public NODE1 getRight() {
return right;
}
public void setRight(NODE1 right) {
this.right = right;
}
public NODE1(int value, NODE1 father, NODE1 left, NODE1 right) {
super();
this.value = value;
this.father = father;
this.left = left;
this.right = right;
}
}
public class ErchashuMain {
public static void main(String[] args) {
Scanner scan = new Scanner (new BufferedInputStream(System.in));
int T = scan.nextInt();
NODE1 root = new NODE1(scan.nextInt(),null, null, null);
NODE1 [] nodes = new NODE1[T];
nodes[0] = root;
root.father = new NODE1(-1,null, null, null);
for(int i=1;i<T;i++){
nodes[i] = new NODE1(scan.nextInt(),null, null, null);
Insert(nodes[i],root);
}
for(int i=0;i<T;i++){
System.out.println(nodes[i].father.value);
}
}
private static int Insert(NODE1 tarnode, NODE1 root) {
if(tarnode.value<root.value){
if(root.left!=null){
Insert(tarnode,root.left);
}else{
tarnode.father = root;
root.left = tarnode;
return 1;
}
}
if(tarnode.value>root.value){
if(root.right!=null){
Insert(tarnode,root.right);
}else{
tarnode.father = root;
root.right = tarnode;
return 1;
}
}
return 1;
}
}