首页 > 试题广场 >

二叉排序树

[编程题]二叉排序树
  • 热度指数：21832 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

输入描述:
输入包含多组测试数据，每组测试数据两行。
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。


输出描述:
输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。
示例1

输入

5
2 5 1 3 4

输出

-1
2
2
5
3
算法知识视频讲解
添加回答
Java
cantin头像 cantin 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner (System.in);
        int num;
        while(in.hasNext()==true)
        {
            num=in.nextInt();
            tree t=new tree();
            t.t=null;
            int i;
            for(i=1;i<=num;i++)
            {
                int key=in.nextInt();
                System.out.println(insert(t,key));
            }
        }
        in.close();
    }
    public static int search(bitree t,bitree parent,int key,tree g)
    {
        if(t==null)
        {
            g.t=parent;
            return 0;
        }
        else
        {
            if(key==t.data)
            {
                g.t=t;
                return 1;
            }
            else if(key<t.data)
                return search(t.lchild,t,key,g);
            else
                return search(t.rchild,t,key,g);
        }
    }

    public static int insert(tree g,int key)
    {
        tree k=new tree();
        k.t=null;
        bitree s;
        if(search(g.t, null, key, k)==1)
            return k.t.data;
        else
        {
            s=new bitree();
            s.data=key;
            s.lchild=s.rchild=null;
            if(k.t==null)
            {
                g.t=s;
                return -1;
            }
            else if(key<k.t.data)
                k.t.lchild=s;
            else
                k.t.rchild=s;
            return k.t.data;
        }
    }
}
class bitree
{
    int data;
    bitree lchild,rchild;
}
class tree
{
    bitree t;
}

发表于 2021-03-09 17:24:16 回复(0)
Java
LHC0512头像 LHC0512
Java  
import java.util.Scanner;

public class Main {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    
    static void creat(TreeNode root, int value){
        if (value<root.val){
            if (root.left==null) {
                root.left = new TreeNode(value);
                System.out.println(root.val);
            } else creat(root.left,value);
        }else {
            if (root.right==null){
                root.right= new TreeNode(value);
                System.out.println(root.val);
            }else creat(root.right,value);
        }
    }
    

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            TreeNode root = new TreeNode(scanner.nextInt());
            System.out.println("-1");
            for (int i = 1; i < n; i++) {
                creat(root,scanner.nextInt());
            }
        }
    }
}


发表于 2020-03-18 18:10:27 回复(0)
Java
yyywww头像 yyywww
import java.util.*;
public class Main{
    private static void insert(SortTree t,int num){
        
        if(t.value == Integer.MAX_VALUE){
            t.value = num;
            if(t.parents!=null) System.out.println(t.parents.value);
            else System.out.println(-1);
            return;
        }else if(num>=t.value){
            if(t.right==null) {
                
            t.right = new SortTree();
            t.right.parents = t;
            }
            insert(t.right,num);
        }else{
            if (t.left==null) {
                
            t.left = new SortTree();
            t.left.parents = t;
            }
            insert(t.left,num);
        }
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String line = scanner.nextLine();
        scanner.close();
        String[] valuestring = line.split(" ");
        
        SortTree tree = new SortTree();
        for(int i = 0;i<n;i++){
            insert(tree,Integer.parseInt(valuestring[i]));
    }
        
}
}
class SortTree{
    SortTree parents = null;
    SortTree left = null;
    SortTree right = null;
    int value = Integer.MAX_VALUE;
}

发表于 2018-12-31 15:02:48 回复(0)
Java
未来在天空头像 未来在天空
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
class binTree{

binTree left=null;
binTree right=null;
int val=-1;

binTree(int val){
this.val=val;
}
}

public void parentnode(ArrayList<Integer> a){
if (a.size()==0)
return;
binTree root=new binTree(a.get(0));
System.out.println("-1");
for (int i=1;i<a.size();i++)
sorttree(root,a.get(i));
}
public void sorttree(binTree root,int v){
if (root==null)
return;
if (v<=root.val){
if (root.left==null){
root.left=new binTree(v);
System.out.println(root.val);
}else {
sorttree(root.left,v);
}
}else {
if (root.right==null){
root.right=new binTree(v);
System.out.println(root.val);
}else
sorttree(root.right,v);
}
}
public static void main(String[] args){
Scanner scanr=new Scanner(System.in);
int n=scanr.nextInt();
scanr.nextLine();
String string=scanr.nextLine();
ArrayList<Integer> arrays= new ArrayList<Integer>();
for (int i=0;i<string.split(" ").length;i++){
arrays.add(Integer.parseInt(string.split(" ")[i]));
}
Main t=new Main();
t.parentnode(arrays);
}
}
//C版
#include<stdio.h>
#include<stdlib.h>

typedef struct binTree{
    binTree *left;
    binTree *right;
    int val;

}BinNode,*BTree;

BTree createBinTree(BTree root,int v){
    if(root==NULL)
        return root;
    if(v<root->val){
            if(root->left==NULL){
                BTree node=(BinNode *) malloc (sizeof(BinNode));
                node->left=NULL;
                node->right=NULL;
                node->val=v;
                root->left=node;
                printf("%d\n",root->val);
            }else{
                root->left=createBinTree(root->left,v);
            }
    }else{
            if(root->right==NULL){
                BTree node=(BinNode *)malloc(sizeof(BinNode));
                node->left=NULL;
                node->right=NULL;
                node->val=v;
                root->right=node;
                printf("%d\n",root->val);
            }else{
                root->right=createBinTree(root->right,v);
            }
    }
    return root;
}
int main(){
    int n;
    int i=0;
    int v;
    scanf("%d",&n);
    scanf("%d",&v);
    BTree root=(BinNode *)malloc(sizeof(BinNode));
    root->left=NULL;
    root->right=NULL;
    root->val=v;
    printf("-1\n");
    while(i<n-1){
        scanf("%d",&v);
        root=createBinTree(root,v);
        i++;
    }
    return 0;
}

编辑于 2018-06-01 13:05:59 回复(0)
Java
zichenchen头像 zichenchen
import java.util.Scanner;

public class Main {
 
int data;      //根节点数据
Main left;    //左子树
Main right; //右子树
public static void main(String[] args) {
//Scanner scan=new Scanner(System.in);
String[]arr ;
Scanner input=new Scanner(System.in);
while(input.hasNext()){
                String n=input.nextLine();
//System.out.println("zzzz");
Main ma=new Main(-1);
String str =input.nextLine();
arr= str.trim().split("\\s+");
   ma.xxx(ma,arr);
   
   
   }
   
}
public Main(int data)    
{
 this.data = data;
 left = null;
 right = null;
 
}
public void xxx(Main root,String[] arr){
for(int i=0;i<arr.length;i++){
insert(root, Integer.parseInt(arr[i]));
}
}
public void insert(Main root,int data){
 if(data>root.data)                               
 {
  if(root.right==null){
   root.right = new Main(data);
   System.out.println(root.data);
  }else{
   this.insert(root.right, data);
  }
 }else if(data<root.data){                                      
  if(root.left==null){
 
   root.left = new Main(data);
   System.out.println(root.data);
  }else{
   this.insert(root.left, data);
  }
 }}
}
修改四次，总算通过了
编辑于 2017-04-16 13:31:10 回复(0)
提交观点

问题信息

树 递归
难度：
5条回答 14228浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉排序树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号