程式扎記: [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式 - Java version

標籤

2010年10月18日 星期一

[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式 - Java version

範例代碼 : 
有關類別 BinaryTree 中的 inorderDisplay() 函數, 請參考這裡. 

- BTreeInLS.java :
  1. package DSwJ.S16;  
  2.   
  3. public class BTreeInLSextends Comparablesuper T>> {  
  4.     private TNode root = null;  
  5.     private int level=0;  
  6.       
  7.     public BTreeInLS(){}  
  8.     public void addNode(T item){  
  9.         TNode tmpNode = root;  
  10.         int tmpLevel = level;  
  11.         if(tmpNode==null) {  
  12.             root = new TNode(item);  
  13.             root.right = null;  
  14.             root.left = null;  
  15.         } else {  
  16.             //TNode prevNode = null;             
  17.             while(true) {  
  18.                 if(item.compareTo(tmpNode.nodeValue)>0) { // 往右子樹移動  
  19.                     if(tmpNode.right==null) {  
  20.                         if(level1){level++;}  
  21.                         tmpNode.right = new TNode(item);  
  22.                         tmpNode.right.left = null;  
  23.                         tmpNode.right.right = null;  
  24.                         return;  
  25.                     } else {  
  26.                         tmpNode = tmpNode.right;  
  27.                         tmpLevel++;  
  28.                     }  
  29.                     //prevNode = tmpNode;                     
  30.                 } else { // 往左子樹移動  
  31.                     if(tmpNode.left==null) {  
  32.                         if(level1){level++;}  
  33.                         tmpNode.left = new TNode(item);  
  34.                         tmpNode.left.left = null;  
  35.                         tmpNode.left.right = null;  
  36.                         return;  
  37.                     } else {  
  38.                         tmpNode = tmpNode.left;  
  39.                         tmpLevel++;  
  40.                     }  
  41.                     //prevNode = tmpNode;  
  42.                 }  
  43.             }  
  44.         }  
  45.     }  
  46.     public int getLevel(){return level;}  
  47.     public void showData(){  
  48.         for(int i=0; i<=level; i++) {  
  49.             showNode(i, 0, root);  
  50.         }  
  51.         System.out.println();  
  52.     }  
  53.     public TNode getRoot(){return root;}  
  54.     public void showNode(int tlvl, int clvl, TNode node) {  
  55.         if(node!=null) {  
  56.             if(tlvl == clvl) {  
  57.                 System.out.printf("[%s] ", node.nodeValue);  
  58.             } else {  
  59.                 showNode(tlvl, clvl+1, node.left);  
  60.                 showNode(tlvl, clvl+1, node.right);  
  61.             }  
  62.         }  
  63.     }  
  64.       
  65.     public static void main(String args[]) {  
  66.         int data[] = {0,6,3,5,9,7,8,4,2}; // 原始陣列    
  67.         BTreeInLS bTreeLS = new BTreeInLS();  
  68.         for(int i=0; i
  69.             bTreeLS.addNode(data[i]);  
  70.         }  
  71.         System.out.print("Source Data: ");  
  72.         bTreeLS.showData();  
  73.         System.out.println("Inorder > "+BinaryTree.inorderDisplay(bTreeLS.getRoot()));  
  74.     }  
  75. }  

執行結果 : 
Source Data: [0] [6] [3] [9] [2] [5] [7] [4] [8]
Inorder > 0 2 3 4 5 6 7 8 9

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!