PDA

Просмотр полной версии : Реализация бинарного дерева[C++|Java]


Zimper
07.03.2012, 03:37
Среда Разработки:NetBeans
Язык:Java,C++(синтаксис такой же)
Задача:Написать программу на языке Java,которая демонстрирует построение и обработку нелинейной структуры данных-дерево.

Елементы записи таблици:Фамилия,имя,курс,студ-билет,пол,место жительства.
Критерии удаления записи из таблиц:Студенток первого курса,которые проживают в общежитие.
Способ обхода дерева:параллельный обход


package tree;
import java.util.Scanner;

/**
*
* @author Zimper
*/
class data
{
public String Sname,Ssname,Slive,Ssex;
public int Skurs=-1,Sbilet=-1;
}

class Root_Tree
{
static public Node_Tree root=null;
}

class Node_Tree extends Root_Tree
{
public Node_Tree right=null,left=null;
public data Student=new data();


public Node_Tree insertNode(data bilet,Node_Tree l)
{
Node_Tree temp=null;
if(l==null)
{
temp=new Node_Tree();
l=temp;
l.Student=bilet;

temp=l;
}
else
{
if(l.Student.Sbilet>bilet.Sbilet)
{
l.left=insertNode(bilet,l.left);
temp=l;
}
else
{
l.right=insertNode(bilet,l.right);
temp=l;
}
}
return temp;
}

public void Print_Data(Node_Tree me,String node)
{
System.out.println(node+" "+me.Student.Sname+" "+me.Student.Ssname+" "+me.Student.Slive+" "+me.Student.Ssex+" "+me.Student.Skurs+" "+me.Student.Sbilet);
}

public void Node_walk(Node_Tree me)
{
if(me!=null)
{
Node_walk(me.left);
Node_walk(me.right);
Print_Data(me,"Node=");
}
}

public Node_Tree ReturnLast(Node_Tree me)
{
Node_Tree temp=new Node_Tree();

if(me!=null)
{

System.out.print("Ms="+me.Student.Sbilet+"\n");
if(me.right!=null)
{
temp=me.right;
}
if(me.right==null)
{
temp=me;
}

if(me.right!=null)
{
ReturnLast(me.right);
}

}
if(temp.right!=null)
{
temp=temp.right;
}
return temp;
}

public Node_Tree Delete_Node(Node_Tree me,Node_Tree delete)
{






if(me!=null)
{

Delete_Node(me.left,null);
Delete_Node(me.right,null);

///leavs

if(me.left!=null && me.left.left==null && me.left.right==null && me.left.Student.Skurs==1 && me.left.Student.Slive.matches("obsh") && me.left.Student.Ssex.matches("woman")) {me.left=null;}
if(me.right!=null && me.right.left==null && me.right.right==null && me.right.Student.Skurs==1 && me.right.Student.Ssex.matches("woman") && me.right.Student.Slive.matches("obsh")){me.right=null;}

//////
Node_Tree farright=new Node_Tree();
Node_Tree tempright=new Node_Tree();


if(me!=null && me.Student.Skurs==1 && me.Student.Slive.matches("obsh") && me.Student.Ssex.matches("woman") && me==me.root)
{
System.out.println("Root found");
tempright=me.right;
if(me.left!=null && me.left.left!=null && me.left.right!=null)
{

farright=ReturnLast(me.left.right);
me.root=me.left;
me=me.left;
System.out.println("Left="+farright.Student.Sbilet);
if(tempright!=null)
farright.right=tempright;
}
if(me.left==null)
{
if(me.right!=null)
{
me.root=me.right;
me=me.right;
}
}

if(me.left!=null && me.left.left==null && me.left.right==null)
{
me.left.right=me.right;
me.root=me.left;

}



Delete_Node(me,null);
}

if(me.left!=null && (me.left.Student.Skurs==1 && me.left.Student.Slive.matches("obsh") && me.left.Student.Ssex.matches("woman")))
{
tempright=me.left.right;
if(me.left.left!=null)
{
farright=ReturnLast(me.left.left);
if(farright!=null)
{
me.left=me.left.left;
farright.right=tempright;
}
}
else
{
me.left=me.left.right;
}
}

if(me.right!=null && (me.right.Student.Skurs==1 && me.right.Student.Slive.matches("obsh") && me.right.Student.Ssex.matches("woman")))
{
tempright=me.right.right;
if(me.right.left!=null)
{
farright=ReturnLast(me.right.left);
if(farright!=null)
me.right=me.right.left;
farright.right=tempright;
}
else
{
me.right=me.right.right;
}
}

}


return me.root;

}
public void Add_Data(String name,String sname,String slive,String ssex,int kurs,int bilet,Node_Tree t)
{
data temp=new data();
temp.Sname=name;
temp.Ssname=sname;
temp.Slive=slive;
temp.Ssex=ssex;
temp.Skurs=kurs;
temp.Sbilet=bilet;
if(root==null)
{
Student=temp;
root=t;
}
else
{
if(Student.Sbilet>bilet)
{
left=insertNode(temp,left);
}
else
{
right=insertNode(temp,right);
}
}
}






}

class input
{

public void Input(Node_Tree me)
{
Scanner vvod=new Scanner(System.in);
data temp=new data();
int count=0;
String inp=new String();
int kurs=0,bilet=0,ascii=0;
char intcheck[]=new char[100];
boolean flag=false;
System.out.println("Write count of students:");
count=vvod.nextInt();


Scanner scan=new Scanner(System.in);
for(int i=0;i<count;i++)
{
flag=false;
while(!flag)
{
System.out.print("Student name:");
inp=scan.nextLine();
if(inp.length()>1) flag=true;
}
flag=false;
temp.Sname=inp;
while(!flag)
{
System.out.print("Student sname:");
inp=scan.nextLine();
if(inp.length()>1) flag=true;
}
flag=false;
temp.Ssname=inp;


while(!flag)
{
System.out.print("Student sex:(man,woman)");
inp=scan.nextLine();

if(inp.matches("woman") || inp.matches("man"))
{
flag=true;
}
}
flag=false;
temp.Ssex=inp;

while(!flag)
{
System.out.print("Living in:(home,obsh)");
inp=scan.nextLine();
if(inp.matches("home") || inp.matches("obsh")) flag=true;
}
flag=false;
temp.Slive=inp;

while(!flag)
{
System.out.print("Student kurs:");
inp=scan.nextLine();
intcheck=inp.toCharArray();
ascii=(int)intcheck[0];
if((ascii<56) && (ascii>48) && inp.length()>0 && inp.length()<7)
{
flag=true;
kurs=Integer.parseInt(inp);
}
else
{
System.out.println("Invalid kurs value!");
}
}
flag=false;
temp.Skurs=kurs;


while(!flag)
{
System.out.print("Student bilet:(4 numbers)");
inp=scan.nextLine();
intcheck=inp.toCharArray();
flag=true;
for(int j=0;j<inp.length();j++)
{

ascii=(int)intcheck[j];
if((ascii<58) && (ascii>47))
{
flag=true;
}
else
{
flag=false;
break;
}
}

if(flag && inp.length()==4)
{

bilet=Integer.parseInt(inp);
}
else
{
flag=false;
System.out.println("Invalid bilet!");
}
}
temp.Sbilet=bilet;
me.Add_Data(temp.Sname,temp.Ssname,temp.Slive,temp .Ssex,temp.Skurs,temp.Sbilet, me);
}

}

}
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {

Node_Tree me=new Node_Tree();
/*
me.Add_Data("Sergi", "Brin", "obsh", "man", 2,24, me);
me.Add_Data("Olexander", "Kostin", "obsh", "man", 2,10, me);
me.Add_Data("Luda", "Glushak", "obsh", "woman", 2,14, me);
me.Add_Data("Sergi", "Olexandrov", "obsh", "man", 3,21, me);
me.Add_Data("Sergi", "Brin", "obsh", "man", 2,9, me);
me.Add_Data("Olga", "Koc", "obsh", "woman", 2,20, me);
me.Add_Data("Dmitri", "Ivanov", "home", "man", 2,16, me);
me.Add_Data("Anna", "Ivanova", "obsh", "woman", 2,15, me);
me.Add_Data("Alex", "Koc", "home", "man", 2,18, me);
*/



input data=new input();

data.Input(me);


System.out.println("Before delete!"+"\n");
me.Node_walk(me);
me=me.Delete_Node(me,null);
System.out.print("\n");
System.out.println("After delete!"+"\n");
me.Node_walk(me);

try
{
Thread.sleep(9000000);
}

catch(Exception m)
{

}
}

}