第十週

http://users.cs.fiu.edu/~weiss/dsj3/code/

【二】、試題名稱：樹狀排序程式
【功能要求】
1.請檢查下列程式中的錯誤，以完成樹狀排序。
2.建立TreeNode class,表樹基本節點及利用insert加入新節點。
3.建立Tree class, 計算樹的排序方法，有inorder,postorder,preorder。
4.輸入十組數字加入樹之節點，並排序後輸出。
5.請依照範例資料檔驗證程式的正確性。

//-----------------------------------------------------------------------------
import java.io.*;
import java.awt.*;
import javax.swing.*;
import java.util.StringTokenizer;

public class RoamToBinary
{
static int[] array;
static String output = "";
String userInput,v="";
char tempStr;
int temp,a,q=1,r,va=0;
public static void main(String args[])
{

File position;
File text;
String InFileName,OutFileName;

try{
InFileName = args[0];
StringTokenizer tokens = new StringTokenizer( InFileName, ".t");
position = new File(InFileName);
OutFileName = tokens.nextToken() + ".w" + tokens.nextToken();
System.out.print("Input File Name:" + InFileName + "\n" );
System.out.print("Output to the File :" + OutFileName);
text = new File(OutFileName);
}
catch(Exception e)
{
System.out.println("Error:"+e);
System.exit(1);
position = new File("");
text = new File("");
}


try{
BufferedReader input = new BufferedReader(new FileReader( position ) );
String ro = input.readLine();
int length=ro.length();

output=translation(ro, length);
}

catch(IOException IOException)
{ }
try{

BufferedWriter output1 = new BufferedWriter(new FileWriter( text) );
output1.write(output);
output1.flush();

}
catch(IOException IOException)
{ }
System.exit(0);
}


public static String translation(String romanNum,int length)
{
int sum = 0;
int i, decimalNum;
int q=1, a=0, r=0;
int previous = 100;
String v=" ";
for(i = 0; i < length; i++)
{
char tempStr=romanNum.charAt(i);
switch(tempStr)
{
case 'C': sum += 100;
break;
case 'L': sum += 50;
break;
case 'X': sum += 10;
break;
case 'V': sum += 5;
break;
case 'I': sum += 1;
previous = 1;
}
}

while(q!=0)
{

q=a/2;
r=a%2;
q=1;
v=r+v;
}

return v;


}
}

---------------------------------------------------------------------------
930202.s01
IVCV
---------------------------------------------------------------------------
【程式碼】


1. TreeTest.java
2. Tree.java

http://www.google.com.tw/search?hl=zh-TW&q=TreeTest.java&btnG=Google+%E6%90%9C%E5%B0%8B&meta=&aq=f&oq=

TreeTest.java *作業1： 請用JAVA寫出一個簡化版二元搜索樹，限定 ...TreeTest.java *作業1： 請用JAVA寫出一個簡化版二元搜索樹，限定：不能使用繼承、多檔、只能以單支原始碼，內含類別製作及測試， 提供元素新增/刪除/查詢功能程式，此 ...
mis.im.tku.edu.tw/~ed_jiang18c/java/TreeTest.java -

/*
* TreeTest.java
*作業1：
請用JAVA寫出一個簡化版二元搜索樹，限定：不能使用繼承、多檔、只能以單支原始碼，內含類別製作及測試，
提供元素新增/刪除/查詢功能程式，此程式包含3個class，
分別是
1.定義結點（結點內存一個整數型態的數值、左小孩、右小孩）、
2.二元搜尋樹
3.二元搜尋樹測試，在二元搜尋樹class中提供新增、中序列印、搜尋數值是否在樹中、刪除四個method
*在TreeTest class中可提供一些資料測試BinarySearchTree class的正確性。
*補充一下...新增的功能中如遇到樹中已有和要新增相同的資料...則列印重複錯誤訊息..不允許新增......
* Created on 2004年10月11日, 上午 8:07
*/
/**
*
未使用的樹：
新增數字'10'後的樹： 10
新增數字'5'後的樹： 5 10
新增數字'18'後的樹： 5 10 18
搜尋數字'10'是否在樹？ true
刪除數字'10'...樹： 5 18
新增數字'5'後的樹： 5 18
The insert item is already in the list -- duplicates are not allowed.
*
* @author Edward
*/
class TreeNode{
int info;
TreeNode llink;
TreeNode rlink;
}

class BinarySearchTree{
protected TreeNode root=null;

public void insert(int insertValue){
TreeNode current;
TreeNode trailCurrent=null;
TreeNode newNode;

newNode=new TreeNode();

newNode.info=insertValue;
newNode.llink=null;
newNode.rlink=null;

if (root==null)
root=newNode;
else {
current=root;
while(current != null){
trailCurrent = current;
if (current.info==insertValue){
System.err.print("The insert item is already in "
+ "the list -- duplicates are "
+ "not allowed.");
return;
}//end if
else {
if(current.info>insertValue)
current = current.llink;
else
current = current.rlink;
}//end else
}//end while

if (trailCurrent.info>insertValue)
trailCurrent.llink = newNode;
else
trailCurrent.rlink = newNode;
}//end else

}

public void inorderPrint(){
inorder(root);
}

public void inorder(TreeNode p){
if (p != null){
inorder(p.llink);
System.out.print(p.info + " ");
inorder(p.rlink);
}//end if
}

public boolean search(int searchValue){
TreeNode current;
boolean found = false;

if(root == null)
System.out.println("Cannot search an empty tree.");
else{
current = root;

while(current != null && !found){
if (current.info==searchValue)
found = true;
else
if (current.info > searchValue)
current = current.llink;
else
current = current.rlink;
}//end while
}//end else

return found;
}

public void delete(int deleteValue){
TreeNode current;
TreeNode trailCurrent;
boolean found = false;

if(root == null)
System.err.println("Cannot delete from the empty tree.");
else{
current = root;
trailCurrent = root;

while(current != null && !found){
if(current.info==deleteValue)
found = true;
else{
trailCurrent = current;

if (current.info > deleteValue)
current = current.llink;
else
current = current.rlink;
}//end else
}//end while

if(current == null)
System.out.println("The delete item is not in the list.");
else
if(found){
if (current == root)
root = deleteFromTree(root);
else
if (trailCurrent.info>deleteValue)
trailCurrent.llink = deleteFromTree(trailCurrent.llink);
else
trailCurrent.rlink = deleteFromTree(trailCurrent.rlink);
}//end if
}//end else
}

private TreeNode deleteFromTree(TreeNode p){
TreeNode current;
TreeNode trailCurrent;

if(p == null)
System.err.println("Error: The node to be deleted "
+ "is null.");
else if(p.llink == null && p.rlink == null)
p = null;
else if(p.llink == null)
p = p.rlink;
else if(p.rlink == null)
p = p.llink;
else{
current = p.llink;
trailCurrent = null;

while(current.rlink != null){
trailCurrent = current;
current = current.rlink;
}//end while

p.info = current.info;

if(trailCurrent == null)
p.llink = current.llink;
else
trailCurrent.rlink = current.llink;
}//end else

return p;
}
}//end class

public class TreeTest {

/** Creates a new instance of TreeTest */
public TreeTest() {
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
BinarySearchTree testNode=new BinarySearchTree();

System.out.print("未使用的樹：");
testNode.inorderPrint();
System.out.println("");

testNode.insert(10);
System.out.print("新增數字'10'後的樹： ");
testNode.inorderPrint();
System.out.println("");

testNode.insert(5);
System.out.print("新增數字'5'後的樹： ");
testNode.inorderPrint();
System.out.println("");

testNode.insert(18);
System.out.print("新增數字'18'後的樹： ");
testNode.inorderPrint();
System.out.println("");

System.out.print("搜尋數字'10'是否在樹？ ");
System.out.print(testNode.search(10));
System.out.println("");

System.out.print("刪除數字'10'...樹： ");
testNode.delete(10);
testNode.inorderPrint();
System.out.println("");

testNode.insert(5);
System.out.print("新增數字'5'後的樹： ");
testNode.inorderPrint();
System.out.println("");
}//end main

}

-----------------------------------------------------------------------------

http://www.google.com.tw/search?hl=zh-TW&q=Tree.java&btnG=%E6%90%9C%E5%B0%8B&meta=&aq=f&oq=

www.cs.uiowa.edu/~sriram/21/spring07/code/tree.java