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

-->