2009-07-19

对树形索引使用深度遍历的一个例子

Posted in Java at 23:28 Author:仲远 浏览量: 3,160

标签:, ,

对于树结构（典型的为二叉树），通常可以使用深度优先遍历和广度优先遍历两种方法来进行树节点的浏览，这些都是最基本的算法。以下就提供一个对于树形索引使用深度优先遍历的代码示例，由于代码中涉及到对于别的方法的调用，因此仅供参考，感兴趣的人理解算法思想即可。

  1. package com.databese.index.bplustree;
  2.  
  3. import java.io.BufferedWriter;
  4. import java.io.File;
  5. import java.io.FileWriter;
  6.  
  7. import com.databese.index.util.Const;
  8. import com.databese.index.util.Function;
  9.  
  10. /**
  11. *
  12. *  对整个索引进行深度优先遍历，并生成对应XML文件
  13. *
  14. */
  15. public class DFSRetrieval {
  16.    
  17.     StringBuffer indexContent = new StringBuffer();
  18.    
  19.     /**
  20.      * 构造函数
  21.      * @param indexFilePath
  22.      */
  23.     public DFSRetrieval(String indexFilePath)
  24.     {
  25.         this.indexRetrieval(indexFilePath);
  26.         this.write2XML();
  27.         System.out.println("索引转换成XML文件成功!");
  28.     }
  29.    
  30.     /**
  31.      * 深度优先遍历
  32.      * @param indexFilePath
  33.      */
  34.     public void indexRetrieval(String indexFilePath)
  35.     {
  36.         String indexName = Function.getIndexName(indexFilePath);
  37.         BTree btree = BTree.openIndex(indexName);
  38.         this.indexContent.append("<root>");
  39.         this.nodeRetrieval(btree.index_head.root);       
  40.         this.indexContent.append("</root>");
  41.        
  42.     }
  43.  
  44.     /**
  45.      * 将索引内容写到外部xml文件中
  46.      *
  47.      */
  48.     public void write2XML()
  49.     {
  50.         try{
  51.             BufferedWriter out = new BufferedWriter(new FileWriter(new File(Const.XML_PATH)));
  52.             out.write(this.indexContent.toString());
  53.             out.close();
  54.         }catch(Exception e)
  55.         {
  56.             e.printStackTrace();
  57.         }
  58.     }
  59.    
  60.     public void nodeRetrieval(Node node)
  61.     {
  62.         //如果是叶子节点，就将所有的叶子节点关键字输出来
  63.         if (node instanceof LeafNode) {
  64.             for(int i=0; i<node.used_keys; i++)
  65.             {
  66.                 this.indexContent.append("<key>")
  67.                     .append(node.keys[i])
  68.                     .append("</key>");
  69.             }
  70.             return ;
  71.         }
  72.        
  73.         if(node  instanceof InnerNode) {
  74.             InnerNode innerNode = (InnerNode) node;
  75.             for(int i=0; i<innerNode.used_keys; i++)
  76.             {
  77.                 //读取孩子节点信息
  78.                 Node childNode = innerNode.getChildNode(i);
  79.                 this.indexContent.append("<point>");
  80.                 this.nodeRetrieval(childNode);
  81.                 this.indexContent.append("</point>");
  82.                
  83.                 //读取关键字信息
  84.                 this.indexContent.append("<key>")
  85.                     .append(innerNode.keys[i])
  86.                     .append("</key>");
  87.             }
  88.            
  89.             //根据节点中最后一个指针去获取孩子信息
  90.             Node childNode = innerNode.getChildNode(innerNode.used_keys);
  91.             this.indexContent.append("<point>");
  92.             this.nodeRetrieval(childNode);
  93.             this.indexContent.append("</point>");
  94.            
  95.         }
  96.        
  97.         return;
  98.     }
  99.    
  100.     public static void main(String[] args) {
  101.         DFSRetrieval dfsRetrieval = new DFSRetrieval("./index/all200000.index");
  102.     }
  103. }

本文可以自由转载，转载时请保留全文并注明出处：
转载自仲子说 [ http://www.wangzhongyuan.com/ ]
原文链接：

» 上一篇：Ubuntu 9.04 Server安装图形桌面的方法
» 下一篇：Eclipse

Leave a Comment

*
To prove you're a person (not a spam script), type the security text shown in the picture. Click here to regenerate some new text.
Click to hear an audio file of the anti-spam word