第十三週

第十三週

fig. 19.17 tree.java
http://www.cis.temple.edu/~ingargio/cis67/software/deitel-jHTP4/ch19/


//=====================================================================
教學錄影
http://www.powercam.cc/slide/1615

//=====================================================================



class Mytreeone
{
TreeNode root;


Mytreeone()
{
//root=null;

}


void preorderTravel()
{
preorderHelper(root);
}
void preorderHelper(TreeNode node)
{
if(node==null)
return;
System.out.println(node.data);
preorderHelper(node.leftNode);
preorderHelper(node.rightNode);
}

void inoderTravel()
{
inoderHelper(root);
}
void inoderHelper(TreeNode node)
{
if(node==null)
return;
inoderHelper(node.leftNode);
System.out.println(node.data);
inoderHelper(node.rightNode);


}


void postorderTravel()
{
postorderHelper(root);
}
void postorderHelper(TreeNode node)
{
if(node==null)
return;
postorderHelper(node.leftNode);
postorderHelper(node.rightNode);
System.out.println(node.data);


}














void insertNode(int insertvalue)
{
if (root==null )
{

root=new TreeNode(insertvalue);
}
else
{

root.insert(insertvalue);

}


}
public static void main(String args[])
{
Mytreeone tree=new Mytreeone();

tree.insertNode(47);
tree.insertNode(25);
tree.insertNode(77);
tree.insertNode(11);
tree.insertNode(43);
tree.insertNode(65);
tree.insertNode(93);
tree.insertNode(7);
tree.insertNode(17);
tree.insertNode(31);
tree.insertNode(44);
tree.insertNode(68);

tree.preorderTravel();
System.out.println("==========");
tree.inoderTravel();
System.out.println("==========");
tree.postorderTravel();
}
}

fig

=================================
http://www.powercam.cc/slide/1561
=================================================================================
class Mytree{
TreeNode root;
Mytree()
{
root=null;
}
void insertNode(int insertValue )
{
if ( root == null )
root = new TreeNode( insertValue );

else
root.insert( insertValue );
}


void preorderTraversal()
{
preorderHelper( root);

}

void preorderHelper( TreeNode node )
{
if(node==null)
{
System.out.println("空的");
return;
}
else
{

System.out.println("不空的");
// output node data
System.out.println( node.data + " " );

// traverse left subtree
preorderHelper( node.leftNode );

// traverse right subtree
preorderHelper( node.rightNode );
}
}
public static void main(String args[]){
//TreeNode root = new TreeNode(47);
Mytree tree = new Mytree();
tree.insertNode(47);
tree.insertNode(25);
tree.insertNode(77);
tree.preorderTraversal();
}

}






==========================================================
// class TreeNode definition
class TreeNode {

// package access members
TreeNode leftNode;
int data;
TreeNode rightNode;

// initialize data and make this a leaf node
public TreeNode( int nodeData )
{
data = nodeData;
leftNode = rightNode = null; // node has no children
}

// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public synchronized void insert( int insertValue )
{
// insert in left subtree
if ( insertValue < data ) {

// insert new TreeNode
if ( leftNode == null )
leftNode = new TreeNode( insertValue );

// continue traversing left subtree
else
leftNode.insert( insertValue );
}

// insert in right subtree
else if ( insertValue > data ) {

// insert new TreeNode
if ( rightNode == null )
rightNode = new TreeNode( insertValue );

// continue traversing right subtree
else
rightNode.insert( insertValue );
}

} // end method insert

} // end class TreeNode
==========================================================

第十二週

第十二週

fig. 19.17 tree.java
http://www.cis.temple.edu/~ingargio/cis67/software/deitel-jHTP4/ch19/

http://www.google.com.tw/search?hl=zh-TW&q=fig.+19.17+tree.java&btnG=%E6%90%9C%E5%B0%8B&meta=&aq=f&oq=
http://www.cis.temple.edu/~ingargio/cis67/software/deitel-jHTP4/ch19/



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

ArrayList members to binary tree nodes
http://forums.sun.com/thread.jspa?threadID=5373085

http://forums.sun.com/thread.jspa?threadID=5381791

第十一週

第十一週 二元排序樹
------------------------------------------------------------------------------
class BinarySortTree{
protected TreeNode root=null;

public void insert(int insertValue){


TreeNode newNode=new TreeNode();

newNode.info=insertValue;
newNode.llink=null;
newNode.rlink=null;
//System.out.print(newNode.info);

TreeNode current=new TreeNode();

if (root==null)
{
root=newNode;
}
else
{
current=root;
current.displayNode();
if (current.info>insertValue)
current.llink = newNode;
else
current.rlink = newNode;

}


TreeNode trailCurrent=new TreeNode();
if (trailCurrent.info>insertValue)
{

trailCurrent.llink = newNode;
trailCurrent.llink.displayNode();
}
else
trailCurrent.rlink = newNode;



}
public static void main(String[] args) {

BinarySortTree testNode=new BinarySortTree();
testNode.insert(17);
testNode.insert(6);
testNode.insert(23);
}


}

class TreeNode{
int info;
TreeNode llink;
TreeNode rlink;

public void displayNode() // display ourself
{
System.out.print("{");
System.out.print(info);
System.out.print("} ");
}

}

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

二元樹排序法是將鑑值依照輸入的順序建立二元樹,第一個鍵值為樹根,當輸入的值比樹根值大,則置入右子樹,
反之則置入左子樹,接著再利用中序走訪二元樹的節點一一走訪,即可得排序之鑑值.
其運作步驟如下:
1 第一筆資料鑑值視為樹根
2.其餘鍵值則個別與樹根比較,若比樹根值大,則置入右子樹,反之則置入左子樹.
3.當鍵值進入下一層子樹時,重複2步驟,直到無數值可用.
4.建好二元樹之後,利用中序走訪即可排序.

例

17,6, 23, 50, 40, 10, 15, 4, 20

17
6 23 (6<17 左, 23 >17 右)
10 50 (10<17, 左 , 10>6 右)
40
-------------------------------------------------------
17
6 23
10 50
15 40 (15<17 左, 15>6, 右, 15>10 右)

--------------------------------------------------------
17
6 23
4 10 20 50
15 40
--------------------------------------------------------------
二元樹以建立完成

--------------------------------------------------------------
在利用中序走訪

4, 6 , 10, 15, 17, 20, 23, 40, 50
排序完成,此為二元樹排序法(Brinary Tree Sorting)
ex
20,10, 50, 30, 40, 60, 15, 8, 12
http://users.cs.fiu.edu/~weiss/dsj3/code/

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


javax.swing.tree

Interface TreeNode

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

class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child

public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node

---------------------------------------------------------------
class TreeNode{
int info;
TreeNode llink;
TreeNode rlink;
}

第十週

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

第九週

javascript教學
http://www.google.com.tw/search?hl=zh-TW&q=javascript%E6%95%99%E5%AD%B8&meta=&aq=1&oq=javascript

期中考
範圍:乙級技能檢定學科

第八週

2009/04/24 5:30 下課
2009/04/24 研討會召開 2009/04/24 Conference period
資訊科技國際研討會(International Conference on Advanced Information Technologies, AIT)
http://ait.inf.cyut.edu.tw/#b

(期末考補課)


第八週

// UsingArrays.java -------------------------------------------------------------------------------------------
public class UsingArrays
{
private int intArray[] = { 1, 2, 3, 4, 5, 6 };
public double doubleArray[] = { 8.4, 9.3, 0.2, 7.9, 3.4 };
public UsingArrays()
{
} // end UsingArrays constructor
public static void main( String args[] )
{
} // end main
}
//----------------------------------------------------------------------------------
import java.util.Arrays;
import java.lang.Math;

public class UsingArrays
{
static private int intArray[] = { 1, 2, 3, 4, 5, 6 };
public double doubleArray[] = { 8.4, 9.3, 0.2, 7.9, 3.4 };
public UsingArrays()
{
} // end UsingArrays constructor
public static void main( String args[] )
{
double tmp=0.0;
UsingArrays gundam=new UsingArrays();
Arrays.sort(gundam.doubleArray);



for(int i=0;i<=4;i++ )
{
System.out.println(gundam.doubleArray[i]);
tmp=Math.max(tmp,gundam.doubleArray[i]);
}
System.out.println(tmp);
} // end main


}

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


------------------------------------------------------------------------------------
【一】、試題編號：11900-930202
【二】、試題名稱：樹狀排序程式
【功能要求】
1.請檢查下列程式中的錯誤，以完成樹狀排序。
2.建立TreeNode class,表樹基本節點及利用insert加入新節點。
3.建立Tree class, 計算樹的排序方法，有inorder,postorder,preorder。
4.輸入十組數字加入樹之節點，並排序後輸出。
5.請依照範例資料檔驗證程式的正確性。
【動作要求】
1、程式執行結果須按試題使用說明第(七)至(九)等項規定設計。
2、執行程式時先以範例資料檔930202.s01進行測試，若完全無誤後，向監評人員要求交卷，並由監評人員以測試檔930202.t01或930202.t02測試程式，並將結果存入930202.w01及930202.w02，以完成測試。
3、測試檔案的筆數(大小)並不同於範例資料檔案。
4、測試檔案型態格式和範例資料檔案相同。
5、程式執行結果，請參照【輸出範例】。
6、將所有程式編譯後之可執行檔或Class檔(以原程式檔名)存入測試磁片，連同原始碼列印於報表上(右上角簽名並註明座號)，等評審完畢後繳回。
【限制】 程式中所有類別名稱、方法及方法中的列印與檔案輸入／輸出指令或方法皆不可修改。
【程式碼】
1. TreeTest.java
2. Tree.java
http://www.google.com.tw/search?hl=zh-TW&q=Tree.java+&btnG=Google+%E6%90%9C%E5%B0%8B&meta=&aq=f&oq=


How to Use Trees
http://kaul.inf.fh-bonn-rhein-sieg.de/home/java/sun_tut/uiswing/components/tree.html