2013年7月12日 星期五

java 二元搜尋樹



二元搜尋樹
一、首先建立二元樹的節點結構
public class bin_tree {
     private bin_tree left;//左子節點
     private bin_tree right;//右子節點
     private int data;
     private int x,y,oldx,oldy;
     private String sText;
     public bin_tree(int n){//新增節點Data
               this.left = null;
               this.right = null;
               this.data = n;//設定值
     }
     public void setLocation(int x,int y,String sText){//記錄坐標及顯示之數字
               this.x = x;
               this.y = y;
               this.sText = sText;
     }
     public void setOldLocation(int x,int y){//儲存舊的節點,繪製分支用
               this.oldx = x;
               this.oldy = y;
     }
}
二、二元搜尋(新增、刪除、前中後序走訪)
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.LinkedList;
import javax.swing.*;
public class View extends JFrame implements ActionListener,KeyListener{
private JLabel jl = new JLabel("輸入元素");
private JTextField jtInput = new JTextField();
private JButton jbInsert = new JButton("新增節點");
private JButton jbSearch = new JButton("搜尋資料");
private JButton jbVisit = new JButton("走訪節點");
private JButton jbPrintG = new JButton("印出圖片");
private JButton jbDelete = new JButton("刪除節點");
private JButton jbClear = new JButton("清空所有節點");
private JPanel jpNorth = new JPanel(new FlowLayout());
private JPanel jpCenter = new JPanel();
private bin_tree head = null;//首節點
private Graphics g;//繪圖
private LinkedList<Integer> lpreOrder = new LinkedList<Integer>();//前序走訪
private LinkedList<Integer> linorder = new LinkedList<Integer>();//中序走訪
private int x,y;
public View(){
super("二元搜尋樹Demo");
Dimension screenSize = java.awt.Toolkit.getDefaultToolkit().getScreenSize();
x = screenSize.width;
y = screenSize.height;
this.setSize(new Dimension(x,y));
this.add(getjpNorth(),BorderLayout.NORTH);
this.add(jpCenter,BorderLayout.CENTER);
x/=2;//首節點位置
y = 60;//首節點位置
this.setVisible(true);
}
private JPanel getjpNorth(){
this.jtInput.setColumns(5);
this.jbInsert.addActionListener(this);
this.jbSearch.addActionListener(this);
this.jbVisit.addActionListener(this);
this.jbPrintG.addActionListener(this);
this.jbDelete.addActionListener(this);
this.jbClear.addActionListener(this);
this.jtInput.addKeyListener(this);
this.jpNorth.add(jl);
this.jpNorth.add(jtInput);
this.jpNorth.add(jbInsert);
this.jpNorth.add(jbSearch);
this.jpNorth.add(jbDelete);
this.jpNorth.add(jbPrintG);
this.jpNorth.add(jbVisit);
this.jpNorth.add(jbClear);
return jpNorth;
}
public void actionPerformed(ActionEvent e) {
if (e.getSource() == jbInsert) Insert();
else if (e.getSource() == jbSearch) Search();
else if (e.getSource() == jbDelete) Delete();
else if (e.getSource() == jbVisit) Visit();
else if (e.getSource() == jbPrintG) printGraphics();
else {head = null;printGraphics();}
}
public void keyTyped(KeyEvent e) {}
public void keyPressed(KeyEvent e) {}
public void keyReleased(KeyEvent e) {if (e.getKeyCode() == KeyEvent.VK_ENTER)Insert();}
private void Insert() {
int n = getIntValue(jtInput.getText());
if (n == Integer.MAX_VALUE) return;
bin_tree h = new bin_tree(n);//new Node
int Div_Distance = 600;
if (head == null) {
head = h;
h.setLocation(x, y,n + "");//存入new座標
h.setOldLocation(x, y);//存入Old座標
}else{
bin_tree p,q = null;
p = head;
while (p!=null){
q = p;//q指向父截點
if (n == p.data) {
JOptionPane.showMessageDialog(this, "二元樹不允許重複數值");
return;
}
p = (n < p.data) ? p.left : p.right;//往左、右子樹
if (Div_Distance > 0)Div_Distance-=(Div_Distance/2);//子樹間隔
}
if (n < q.data) {
h.setOldLocation(q.x, q.y);//存入old座標
h.setLocation(q.x-Div_Distance, q.y+30,n + "");//存入new座標
q.left = h;//q左節點設為h
}
else{
h.setOldLocation(q.x, q.y);
h.setLocation(q.x+Div_Distance, q.y+30,n + "");
q.right = h;//q右節點設為h
}
}
printGraphics();
this.jtInput.requestFocus();
this.jtInput.selectAll();
}
private void Delete() {
int n = getIntValue(jtInput.getText());
bin_tree p = head, q = null;
while (p != null) {
if (p.data == n) break;//Find Data
q = p;//q指向父節點
p = (n < p.data) ? p.left : p.right;//往左右子樹
}
if (p == null) return;//Not Find Data
if (p.left != null && p.right != null){
bin_tree r = p.left;
q = p;
while (r.right != null){
q = r;
r = r.right;
}
p.data = r.data;
p.sText = r.sText;
if (r.left != null)r.left.setOldLocation(q.x, q.y);
if (q == p) q.left = r.left;
else q.right = r.left;
}else{
if (p == head){
head = (p.right == null) ? p.left : p.right;
head.setOldLocation(head.x, head.y);
}
else if (p.right == null){
if (p == q.left) q.left = p.left;
else q.right = p.left;
if (p.left != null) p.left.setOldLocation(q.x, q.y);
}else{
if (p == q.left) q.left = p.right;
else q.right = p.right;
if (p.right != null)p.right.setOldLocation(q.x, q.y);
}
}
printGraphics();
this.jtInput.requestFocus();
this.jtInput.selectAll();
}
private void printGraphics() {
g = jpCenter.getGraphics();//取得Center Panel的繪圖
this.jpCenter.update(g);//更新
postorder(head);//後序遞迴走訪繪圖
}
private void Search(){
bin_tree h = head;
int x = getIntValue(jtInput.getText());
while (h != null){
if (x == h.data) {
g.setColor(Color.red);
g.drawString(h.sText, h.x, h.y);
break;
}
h = (x < h.data) ? h.left:h.right;
}
this.jtInput.requestFocus();
this.jtInput.selectAll();
}
private void Visit() {
lpreOrder.clear();
linorder.clear();
preorder(head);
inorder(head);
ReConstructTree r = new ReConstructTree(linorder, lpreOrder);
JOptionPane.showMessageDialog(this,String.format("前序走訪:%s\n中序走訪:%s\n回推樹狀結構:%s", lpreOrder.toString(),linorder.toString(),r.getTreeNum()));
}
private int getIntValue(String s) {
int n = Integer.MAX_VALUE;
try {n = Integer.valueOf(s);}
catch (Exception e) {
n = Integer.MAX_VALUE;
jtInput.requestFocus();
jtInput.selectAll();
JOptionPane.showMessageDialog(this, "請輸入整數");
}
return n;
}
private void inorder(bin_tree p) {//中序走訪
if (p != null){
inorder(p.left);//左子樹
linorder.add(p.data);
inorder(p.right);//右子樹
}
}
private void preorder(bin_tree p){//前序走訪
if (p != null){
lpreOrder.add(p.data);
preorder(p.left);//左子樹
preorder(p.right);//右子樹
}
}
private void postorder(bin_tree p) {//後序走訪印圖片
if (p != null){
postorder(p.left);//左子樹
postorder(p.right);//右子樹
g.drawLine(p.oldx, p.oldy, p.x, p.y);
g.drawString(p.sText, p.x, p.y);
}
}
public static void main(String[] args) {
View v = new View();
v.setDefaultCloseOperation(EXIT_ON_CLOSE);
}
}
三、中前序、中後序還原二元樹

import java.util.LinkedList;
import java.util.Queue;

public class ReConstructTree {
private LinkedList<Integer> lpreorder = new LinkedList<Integer>();
private int index;
public ReConstructTree(LinkedList<Integer> inorder,LinkedList<Integer> preorder){//建構子
this.lpreorder = preorder;
Integer []inorderArray = inorder.toArray(new Integer[0]);
System.out.println(inorderArray.length);
makeTree(inorderArray,0,inorderArray.length-1);
}
public void makeTree( Integer[] inorder, int inleft, int inright) {
if (inleft >= inright) {return;}
int i = 0;
for (i = inleft; i <= inright; i++) {
if (inorder[i] == lpreorder.get(index)){
index++;
break;
}
}
if ((i-1) == inright) lpreorder.addLast(lpreorder.remove(index));//沒找到根節點,將元素移到最後
makeTree(inorder, inleft, i-1);//往左找
makeTree(inorder, i + 1, inright);//往右找
}
public String getTreeNum(){return lpreorder.toString();}
}

五、專案下載
1.bin_tree.java
2.ReConstructTree.java
3.View.java


-->

沒有留言:

張貼留言