第十一週

第十一週 二元排序樹
------------------------------------------------------------------------------
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;
}