stacknode.java

这是一个用java语言写的排序树

import java.io.*;
class Stack 
{
	Object arr[]=new Object[30];
	int top=-1;
	public boolean IsFull()
    {
		  return top==arr.length-1;
    }
	public boolean IsEmpty()
    {
        return top==-1;
    }
	public Object pop() 
	{
		return arr[top--];
	}
	public void push(Object N) 
	{
		if (IsFull())
	        System.out.println("Stack overflow"); 
		else
			arr[++top]=N;
	}
	Object StackTop()
    {
       if(IsEmpty())
          {
    	     System.out.println("Stack is empty");
    	     return null;
    	   }
       else 
    	   return arr[top];
     }
}
class Node
{
	public int iData;
	public double dData;
	public Node leftChild;
	public Node rightChild;
	public char tag=0;
	public void displayNode()
	{
		System.out.print('{');
		System.out.print(iData);
		System.out.print(",");
		System.out.print(dData);
		System.out.print("}");
	}
}
class Tree
{
	private Node root;
	public Tree()
	{
		root=null;
	}
	public Node find(int key)
	{
		Node current=root;
		while(current.iData!=key)
		{
			if(key<current.iData)
				current=current.leftChild;
			else
			    current=current.rightChild;
			if(current==null)
				return null;
		}
		return current;
	}
	public void insert(int id,double dd)
	{
		Node newNode=new Node();
		newNode.iData=id;
		newNode.dData=dd;
		if(root==null)
			root=newNode;
		else
		{
			Node current=root;
			Node parent;
			while(true)
			{
				parent=current;
				if(id<current.iData)
				{
					current=current.leftChild;
					if(current==null)
					{
						parent.leftChild=newNode;
						return;
					}
				}
				else
				{
					current=current.rightChild;
					if(current==null)
					{
						parent.rightChild=newNode;
						return;
					}
				}
			}
		}
	}
	public boolean delete(int key)
	{
		Node current=root;
		Node parent=root;
		boolean isLeftChild=true;
		while(current.iData!=key)
		{
			parent=current;
			if(key<current.iData)
			{
				isLeftChild=true;
				current=current.leftChild;
			}
			else
			{
				isLeftChild=false;
				current=current.rightChild;
			}
			if(current==null)
				return false;
		}
		if(current.leftChild==null&&current.rightChild==null)
		{
			if(current==root)
				root=null;
			else 
				if(isLeftChild)
				   parent.leftChild=null;
			else
				parent.rightChild=null;
		}
		else 
			if(current.rightChild==null)
			   if(current==root)
				  root=current.leftChild;
			   else 
				   if(isLeftChild)
					   parent.leftChild=current.leftChild;
			else 
				parent.rightChild=current.leftChild;
		else 
			if(current.leftChild==null)
			    if(current==root)
			    	root=current.rightChild;
			    else 
			    	if(isLeftChild)
			    		parent.leftChild=current.rightChild;
			else 
				parent.leftChild=current.rightChild;
		else
		{
			Node successor=getSuccessor(current);
			if(current==root)
				root=successor;
			else 
				if(isLeftChild)
					parent.leftChild=successor;
			successor.leftChild=current.leftChild;
		}
		return true;
	}
	private Node getSuccessor(Node delNode)
	{
		Node successorParent=delNode;
		Node successor=delNode;
		Node current=delNode.rightChild;
		while(current!=null)
		{
			successorParent=successor;
			successor=current;
			current=current.leftChild;
		}
		if(successor!=delNode.rightChild)
		{
			successorParent.leftChild=successor.rightChild;
			successor.rightChild=delNode.rightChild;
		}
		return successor;
	}
	public void traverse(int traverseType)
	{
		switch(traverseType)
		{
			case 1:
				System.out.print("\nPreorder traversal:  ");
			    preOrder(root);
			    break;
			case 2:
				System.out.print("\ninorder traversal:  ");
			    inOrder(root);
			    break;
			case 3:
				System.out.print("\npostorder traversal:  ");
			    postOrder(root);
			    break;
		}
		System.out.println();
	}
	private void preOrder(Node localRoot)
	{
		/*
		  if(localRoot!=null)
		  	{
			System.out.print(localRoot.iData+" ");
			preOrder(localRoot.leftChild);
			preOrder(localRoot.rightChild);
			}
		*/
		Stack tree = new Stack();
		while(localRoot!=null||!tree.IsEmpty())
		{
			while(localRoot!=null)
			{
				System.out.print(localRoot.iData+" ");
				tree.push(localRoot);
				localRoot=localRoot.leftChild;
			}
			if(!tree.IsEmpty())
			{
				localRoot=(Node)tree.pop();
				localRoot=localRoot.rightChild;
			}
		}
	}
	private void inOrder(Node localRoot)
	{
		/*
		 if(localRoot!=null)
		   {
		 	  inOrder(localRoot.leftChild);
		 	  System.out.print(localRoot.iData+" ");
		 	  inOrder(localRoot.rightChild);
		   }
		*/
		Stack tree = new Stack();
		while(localRoot!=null||!tree.IsEmpty())
		{
			while(localRoot!=null)
			{
				tree.push(localRoot);
				localRoot=localRoot.leftChild;
			}
			if(!tree.IsEmpty())
			{
				localRoot=(Node)tree.pop();
				System.out.print(localRoot.iData+" ");
				localRoot=localRoot.rightChild;
			}
		}
	}
	private void postOrder(Node localRoot)
	{
		/*
		 if(localRoot!=null)
		  {
			postOrder(localRoot.leftChild);
			postOrder(localRoot.rightChild);
			System.out.print(localRoot.iData+" ");
		  }
		*/
		Stack tree = new Stack();
		do
		{
			while(localRoot!=null)
			{
				localRoot.tag='L';
				tree.push(localRoot);
				localRoot=localRoot.leftChild;
			}
			while(!tree.IsEmpty()&&((Node)tree.StackTop()).tag=='R')
			{
				System.out.print(((Node)tree.pop()).iData+" ");
			}
			if(!tree.IsEmpty())
			{
				((Node)tree.StackTop()).tag='R';
				localRoot=((Node)tree.StackTop()).rightChild;
			}
		}
		while(!tree.IsEmpty());
	}
	public void displayTree()
	{
		Stack globalStack=new Stack();
		globalStack.push(root);
		int nBlanks=32;
		boolean isRowEmpty=false;
		System.out.println("..............................");
		while(isRowEmpty==false)
		{
			Stack localStack=new Stack();
			isRowEmpty=true;
			for(int j=0;j<nBlanks;j++)
				System.out.print(' ');
			while(globalStack.IsEmpty()==false)
			{
				Node temp=(Node)globalStack.pop();
				if(temp!=null)
				{
					System.out.print(temp.iData);
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);
					if(temp.leftChild!=null||temp.rightChild!=null)
						isRowEmpty=false;
					else
					{
						System.out.print("........");
						localStack.push(null);
						localStack.push(null);
					}
					for(int j=0;j<nBlanks*2.2;j++)
						System.out.print(' ');
				}
				System.out.print(' ');
				nBlanks/=2;
				while(localStack.IsEmpty()==false)
					globalStack.push(localStack.pop());
			}
			System.out.println("................................");
		}
	}
}
public class stackNode 
{
	public static void main(String[]args) throws IOException
	{
		int value;
		Tree theTree=new Tree();
		theTree.insert(50,1.5);
		theTree.insert(25,1.2);
		theTree.insert(75,1.7);
		theTree.insert(12,1.5);
		theTree.insert(37,1.2);
		theTree.insert(43,1.7);
		theTree.insert(30,1.5);
		theTree.insert(33,1.2);
		theTree.insert(87,1.7);
		theTree.insert(93,1.5);
		theTree.insert(97,1.5);
		while(true)
		{
			System.out.print("Enter first letter of show");
			System.out.print("insert,find,delete,or traverse:   ");
			int choice=getChar();
			switch(choice)
			{
			case 's':
				theTree.displayTree();
				break;
			case 'i':
				System.out.print("Enter value to insert: ");
				value=getInt();
				theTree.insert(value,value+0.9);
				break;
			case 'f':
				System.out.print("Enter value to find: ");
				value=getInt();
				Node found=theTree.find(value);
				if(found!=null)
				{
					System.out.print("Found: ");
					found.displayNode();
					System.out.print("\n");
				}
				else
				  System.out.print("Could not find:  ");
				  System.out.print(value+'\n');
				  break;
			 case 'd':
				System.out.print("Enter value to delete:  ");
				value=getInt();
				boolean didDelete=theTree.delete(value);
				if(didDelete)
					System.out.print("Deleted"+value+'\n');
				else
					System.out.print("Could not delete:  ");
					System.out.print(value+'\n');
					break;
			 case 't':
				 System.out.print("Enter type 1,2 or 3:");
				 value=getInt();
				 theTree.traverse(value);
				 break;
			default:
				System.out.print("Invalid entry\n");
			}
		}
	}
	public static String getString()throws IOException
	{
		InputStreamReader isr=new InputStreamReader(System.in);
		BufferedReader br=new BufferedReader(isr);
		String s=br.readLine();
		return s;
	}
	public static char getChar()throws IOException
	{
		String s=getString();
		return s.charAt(0);
	}
	public static int getInt()throws IOException
	{
		String s=getString();
		return Integer.parseInt(s);
	}
}