關於最佳二元搜尋樹遞迴部份

發表時間：2005-06-07 08:24:48

IP:61.230.xxx.xxx 未訂閱

最近再嘗試寫一個最佳二元搜尋樹因為沒有學過任何演算法所以就照著藍皮書(DATA STRUCTURES IN C++)打可是有一個地方我不是很懂..就是遞迴部份書中的範例是

template 
BstNode* BST::Construct(Element*a,int i,int j)
{
   if (i!=j)
   {
     BstNode *node=new BstNode;
     node->data=a[r[i][j]];
     node->left=Construct(a,i,r[i][j]-1);
     node->left=Construct(a,r[i][j],j);
     return node;     
   }          
else return0;                                                         
}    template 
void BST::Construct(Element*a,int n)
{
root=Construct(a,0,n);
}

所以我就嘗試用JAVA寫..但是遞迴那邊一直有問題(說實在我也不知道是什麼問題) 希望知道的前輩能給予教導謝謝你們我的程式碼

import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
public  class Untitled1  extends JFrame
{
  String s,value;   //一些暫存檔案空間
  String input=" ";//讀取檔案用
  JMenuBar bar1;
  JMenuItem clearItem = new JMenuItem("清除");
  JMenuItem openItem = new JMenuItem("開啟舊檔");
  JMenuItem about = new JMenuItem("關於樹");
  JFileChooser jFileChooser1 = new JFileChooser();
  JTextArea ta1;
  JLabel L1;
  JPanel ContentPane;
  JTextField t1,getfile;
  JButton b1,b2,b3;      String a[]=new String[]{"do","if","retuin","while"};//資料
  int p[]=new int[]{3,3,1,1}; //點的收尋次數 
  int q[]=new int[]{2,3,1,1,1};//失敗節點
  int i=0,j=0,n=4;
  int w[][]=new int[4][4];//權重
  int c[][]=new int[4][4];//花費
  int r[][]=new int[4][4];//點      OBST OBST1 =  new OBST();//宣告 計算花費
  OPBinarySearch OBS = new OPBinarySearch();//宣告 最佳搜尋樹      public Untitled1()
   {
     super("二元樹");
     ContentPane=(JPanel)this.getContentPane();
     ContentPane.setLayout(null);//自定位置         bar1=new JMenuBar();
     this.setJMenuBar(bar1);
     JMenu fileMenu = new JMenu("File",false);
     JMenu otherMenu = new JMenu("other",false);
     bar1.add(fileMenu);
     fileMenu.add(clearItem);
     fileMenu.add(openItem);
    // ItemListener ItemListen1=new ItemListener();
    // clearItem.addActionListener(ItemListen1);
     bar1.add(otherMenu);
     otherMenu.add(about);
   //  about.addActionListener(ItemListen1);         openItem.addActionListener(new java.awt.event.ActionListener()
     {
       public void actionPerformed(ActionEvent e)
       {
    //     jbtnopen_actionPerformed(e);
       }
     });
     ta1=new JTextArea();
     ta1.setBounds(100,0,350,100);
     ContentPane.add(ta1);         b1=new JButton("讀入");
     b1.setBounds(0,0,100,25);
     ContentPane.add(b1);
     b1.addMouseListener(new valueListener());         b2=new JButton("建造");
     b2.setBounds(0,25,100,25);
     ContentPane.add(b2);
     b2.addMouseListener(new coListener());         b3=new JButton("收尋");
     b3.setBounds(0,75,100,25);
     ContentPane.add(b3);
    // b3.addMouseListener(new valueListener());         t1=new JTextField();
     t1.setBounds(0,50,100,25);
     ContentPane.add(t1);        L1=new JLabel("檔案路徑:");
    L1.setBounds(25,103,70,25);
    ContentPane.add(L1);
    getfile=new JTextField("D:/1.txt");
    getfile.setBounds(100,100,350,25);
    ContentPane.add(getfile);         this.setSize(400,185);
     this.setVisible(true);
   }
   public static void main(String arg[])
   {
     Untitled1 frame = new Untitled1();
     frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   }       class  valueListener extends MouseAdapter//讀入.頃聽事件
  {
    public void mouseClicked(MouseEvent e)
     {
       OBST1.insert(p,q,a,n);
     }
  }      class  coListener extends MouseAdapter//建造.頃聽事件
 {
   public void mouseClicked(MouseEvent e)
    {
      OBS.AddNode(a,i,j);
    }
 }    //---       class OBST //計算成本並儲存到陣列
   {
   public KnuthMin Knuth=new KnuthMin();//宣告KnuthMin
   //public TreeNode rootNode;//宣告樹點
    public void insert(int p[],int q[],String a[],int n)
    {
      for(i=0;i sum)
              {
               minsum=sum;
               choice=k;
               }
        }
    return choice;         }
   }       class TreeNode  //節點定義
   {
    String value;
    TreeNode left_Node;
    TreeNode right_Node;
    public TreeNode(String value)
    {
    this.value=value;
    this.left_Node=null;
    this.right_Node=null;
     }
   }
   class OPBinarySearch//建照最佳樹   ...這邊出問題
   {
     TreeNode rootNode; //指定何者是樹根
     public void AddNode(String a[], int i, int j)
     { //將點加入並開始創造樹
       if (rootNode == null) //如果第一個當作樹根並回傳
       {
         rootNode = new TreeNode(a[r[0][n]]); //這個點一定是樹根吧..
         return;
       }
       TreeNode nextNode = rootNode; //nextNode指向樹根
       if (i != j)
       {
         TreeNode node;
         node.value = a[r[i][j]];
         node.left_Node = AddNode(a[r[i][j]],i,r[i][j]-1);
         node.right_Node = AddNode(a[r[i][j]],r[i][j],j);
         return node;
       }
     }
   }
//---
}

不好意思這是學校資結作業..只是我真的不懂遞迴建造樹那邊發表人 - batela.tw 於 2005/06/07 08:41:42