97. 二叉排序树

时间限制 1000 ms 内存限制 65536 KB

题目描述

二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：

若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；
若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；
左、右子树本身也是一颗二叉排序树。

现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

输入格式

第一行，一个数字N（N<=100），表示待插入的节点数。

第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过108。

输出格式

输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值

输入样例

5

2 5 1 3 4

输出样例

不是很难的题但确实体现了北邮爱考树相关的编程题，从历年的初试题也能看得出来。

用类表示节点，在节点内部定义父节点。

用节点数组按输入顺序存储节点。

在递归创建二叉排序树的时候，记录父节点。

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;

	}

}

巴特西

北邮oj 97. 二叉排序树