創作內容

5 GP

Binary Search Tree (using array)

作者：Breguet│2014-01-12 18:07:09│巴幣：10│人氣：2422
題目：
寫一程式建立一棵binary search tree, 同時寫recursise與nonrecursive 版method (或function) 去traverse這棵binary search tree, 將它的preorder, inorder, 與 postorder列印出來.請參考課本第七章所附之建立binary search tree與 binary tree traversal程式, 假設每個binary search tree node存一個整數, 而binary search tree的preorder, inorder, postorder是以visit node時以輸出該node所存之整數順序代表。

程式架構：

使用者輸入要輸入幾個數字，以size記錄，產生兩個Array，大小為2^(size)。
numTree為儲存數字，storage為儲存是否有存入數字。
用一個while迴圈讓使用者輸入，
第一個數字放在root(index=1)。
第二個以後，
若較小或等於放在left child。(index*2)
若較大放在right child。(index*2+1)
輸入滿15(size)個數就跳出迴圈。

印tree
第一行空7格(size/2)，並逐行遞減，以變數tab記錄。
每印到2^n-1的數則換行，以變數chLine記錄。
countPrNum則紀錄印出幾個node。

迴圈以i=1開始，到array.length結束。
有node印出數字。
沒有node印x。

Traversal(Recursion)

Inorder
catch 三個值，storage[]，numTree[]，curIndex=1
如果curIndex在範圍內，
則作以下判斷，
如果沒有left child(curIndex*2)和right child(curIndex*2+1)
若有node，印出值。
如果有則，
呼叫Inorder(storage[]，numTree[]，curIndex*2)
印出目前的值。
呼叫Inorder(storage[]，numTree[]，curIndex*2+1)

如果不在範圍內
若有node，印出來。

Preorder和Postorder大致上一樣。
只是Preorder是
System.out.print(numTree[curIndex]+" ");    //node
preorder(storage,numTree,curIndex*2);//left child
preorder(storage,numTree,curIndex*2+1);//right child

Postorder是，
preorder(storage,numTree,curIndex*2);//left child
preorder(storage,numTree,curIndex*2+1);//right child
System.out.print(numTree[curIndex]+" ");    //node

Traversal(Non Recursion)
Inorder
用另一個boolean array紀錄storage裡的值，stoInorder。
用一個stack紀錄存過的index。
用IfChild紀錄目前的index。

while loop(prCount!=size)
如果有left child
將自己push進去。
將left child push進去。

如果沒有left child
如果有node，印出來。
將自己的位置設成false。
將prCount++。

檢查是否有right child，
有的話push進去。

Preorder
用另一個boolean array紀錄storage裡的值，stoPreorder。
用一個stack紀錄存過的index。
用IfChild紀錄目前的index。

while loop(prCount!=size)
如果沒有left child也沒有right child，
若有node，印出來，prCount++，位置設成false。

若有的話
先將自己印出來。
prCount++。
檢查right child，有的話push
檢查left child，有的話push

Postorder
用另一個boolean array紀錄storage裡的值，stoPreorder。
用一個stack紀錄存過的index。
用IfChild紀錄目前的index。

while loop(prCount!=size)
如果沒有left child也沒有right child，
若有node，印出來，prCount++，位置設成false。

若有的話
push自己。
檢查right child，push right child。
檢查left child，有的話push。


討論：
建tree的想法，因為對array還是比較熟一些，所以先用array來寫，結果弄到後面好像也沒比較輕鬆，如果其他作業也完成的話，會來試看看linked list的部分。
一開始的數放root，其餘的數，小的放左邊，大的放右邊，以此類推。
index=0的位置則放棄掉，這樣才會有index*2=left child，index*2+1=right child的效果。

recursive的方法很直觀，即是以Traversal的順序來印出。non recursive則是每個Order略有不同，一部分是寫一寫想到更好的方法，因而改掉的，以及要注意印出的順序，push的順序會有所不同，例如：若是LRV，push順序就是 node,right child,left child。



執行畫面：

How many number do you want?15
Please input number:
20 16 11 19 25 61 5 8 97 3 12 66 18 17 30


How many number do you want?15
Please input number:
85 13 73 87 61 51 22 44 85 74 16 79 74 92 96



How many number do you want?15
Please input number:
56 36 75 100 9 44 41 24 15 37 64 71 91 6 2




程式碼：

Recursive

import java.util.Scanner;
public class BinaryTree {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.print("How many number do you want?");
int size=input.nextInt();
int numTree []=new int[(int)Math.pow(2, size)];
boolean storage []=new boolean[(int)Math.pow(2, size)];
System.out.println("Please input number:");
//input number
for(int i=0;i<size;i++){
int num=input.nextInt();
for(int j=1;j<numTree.length;){
int temp=j;
if(!storage[j]){
numTree[j]=num;
storage[j]=true;
break;
}
else if (storage[j]){
if(num<numTree[j])
j*=2;
else if(num>numTree[j])
j=j*2+1;
else
j*=2;
}
}
}
//print tree
int chLine=1;
int tab=15;
int countPrNum=0;
boolean space=true;
int i=1;
for(;i<numTree.length;i++){
if(space){
for(int j=0;j<tab;j++){
System.out.print("  ");
}
space=false;
}
if(storage[i]){
System.out.print(numTree[i]+" ");
countPrNum++;
}
else
System.out.print("x");
if(i==(int)Math.pow(2,chLine)-1){
System.out.println();
chLine++;
tab--;
space=true;
if(countPrNum==size)
break;
}
}
System.out.print("\n");
System.out.print("Inorder:");
inorder (storage,numTree,1);
System.out.print("\n");
System.out.print("Preorder:");
preorder (storage,numTree,1);
System.out.print("\n");
System.out.print("Postorder:");
postorder (storage,numTree,1);
}
static void inorder (boolean storage[],int numTree[],int curIndex){
if(curIndex*2+1<storage.length){
if(storage[curIndex*2]==false&&storage[curIndex*2+1]==false){
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
else {
inorder(storage,numTree,curIndex*2);
System.out.print(numTree[curIndex]+" ");
inorder(storage,numTree,curIndex*2+1);
}
}
else{
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
}
static void preorder (boolean storage[],int numTree[],int curIndex){
if(curIndex*2+1<storage.length){
if(storage[curIndex*2]==false&&storage[curIndex*2+1]==false){
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
else {
System.out.print(numTree[curIndex]+" ");
preorder(storage,numTree,curIndex*2);
preorder(storage,numTree,curIndex*2+1);
}
}
else{
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
}
static void postorder (boolean storage[],int numTree[],int curIndex){
if(curIndex*2+1<storage.length){
if(storage[curIndex*2]==false&&storage[curIndex*2+1]==false){
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
else {
postorder(storage,numTree,curIndex*2);
postorder(storage,numTree,curIndex*2+1);
System.out.print(numTree[curIndex]+" ");
}
}
else{
if(storage[curIndex])
System.out.print(numTree[curIndex]+" ");
}
}
}


Non Recursive

import java.util.Scanner;
import java.util.Stack;
public class BinaryTree_NR {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.print("How many number do you want?");
int size=input.nextInt();
int numTree []=new int[(int)Math.pow(2, size)];
boolean storage []=new boolean[(int)Math.pow(2, size+1)];
System.out.println("Please input number:");
//input number
for(int i=0;i<size;i++){
int num=input.nextInt();
for(int j=1;j<numTree.length;){
int temp=j;
if(!storage[j]){
numTree[j]=num;
storage[j]=true;
break;
}
else if (storage[j]){
if(num<numTree[j])
j*=2;
else if(num>numTree[j])
j=j*2+1;
else
j*=2;
}
}
}
//print tree
int chLine=1;
int tab=15;
int countPrNum=0;
boolean space=true;
int i=1;
for(;i<numTree.length;i++){
if(space){
for(int j=0;j<tab;j++){
System.out.print("  ");
}
space=false;
}
if(storage[i]){
System.out.print(numTree[i]+" ");
countPrNum++;
}
else
System.out.print("x");
if(i==(int)Math.pow(2,chLine)-1){
System.out.println();
chLine++;
tab--;
space=true;
if(countPrNum==size)
break;
}
}
System.out.print("\n");
System.out.print("Inorder:");
inorder (storage,numTree,size,1);
System.out.print("\n");
System.out.print("Preorder:");
preorder (storage,numTree,size,1);
System.out.print("\n");
System.out.print("Postorder:");
postorder (storage,numTree,size,1);
}
//LVR
static void inorder (boolean storage[],int numTree[],int size,int curIndex){
Stack <Integer> inorder=new Stack<Integer>();
boolean stoInorder []=new boolean[storage.length];
for(int i=1;i<storage.length;i++){
stoInorder[i]=storage[i];
}
inorder.push(curIndex);
int prCount=0;
int lfChild;
while(true){
if(prCount==size)
break;
lfChild=inorder.pop();
if(stoInorder[lfChild*2]){
inorder.push(lfChild);
inorder.push(lfChild*2);
continue;
}
else{
if(stoInorder[lfChild]){
System.out.print(numTree[lfChild]+" ");
stoInorder[lfChild]=false;
prCount++;
if(stoInorder[lfChild*2+1])
inorder.push(lfChild*2+1);
}
}
}
}
//VLR
static void preorder (boolean storage[],int numTree[],int size,int curIndex){
Stack <Integer> preorder=new Stack<Integer>();
boolean stoPreorder []=new boolean[storage.length];
for(int i=1;i<storage.length;i++){
stoPreorder[i]=storage[i];
}
preorder.push(curIndex);
int prCount=0;
int lfChild;
while(true){
if(prCount==size)
break;
lfChild=preorder.pop();
if(stoPreorder[lfChild*2]==false&&stoPreorder[lfChild*2+1]==false){
System.out.print(numTree[lfChild]+" ");
stoPreorder[lfChild]=false;
prCount++;
continue;
}
else{
System.out.print(numTree[lfChild]+" ");
prCount++;
if(stoPreorder[lfChild*2+1])
preorder.push(lfChild*2+1);
if(stoPreorder[lfChild*2])
preorder.push(lfChild*2);
}
}
}
//RVL
static void postorder (boolean storage[],int numTree[],int size,int curIndex){
Stack <Integer> postorder=new Stack<Integer>();
boolean stoPostorder []=new boolean[storage.length];
for(int i=1;i<storage.length;i++){
stoPostorder[i]=storage[i];
}
postorder.push(curIndex);
int prCount=0;
int lfChild;
while(true){
if(prCount==size)
break;
lfChild=postorder.pop();
if(stoPostorder[lfChild*2]==false&&stoPostorder[lfChild*2+1]==false){
System.out.print(numTree[lfChild]+" ");
stoPostorder[lfChild]=false;
prCount++;
continue;
}
else{
postorder.push(lfChild);
if(stoPostorder[lfChild*2+1]){
postorder.push(lfChild*2+1);
}
if(stoPostorder[lfChild*2]){
postorder.push(lfChild*2);
}
}
}
}
}


喜歡5 收藏 1 引用 留言 推上首頁 檢舉
引用網址：https://home.gamer.com.tw/TrackBack.php?sn=2307406
All rights reserved. 版權所有，保留一切權利

相關創作

同標籤作品搜尋：JAVA

【zerojudge】b901+d715 階乘最後一位非零數
java參數錯誤
2023 01 30 ●淺談─轉職JAVA軟體工程師(年資四年)
YTSuperHeroVFX【Minecraft半生存伺服器】,【建築創造模式世界】JAVA 1.18.2 自架
CPE 一顆星解答 - Java 筆記與心得分享

留言共 2 篇留言

ays.：
剛剛好最近計概教了二元樹部分,實作看可以有更具體的理解呢!
感謝大大^^

01-12 18:25

Breguet：
等期末考完再貼一個比較好的實作方式 現在還在編輯中 ><01-12 18:55
紳士der阿嘟：
不明覺厲 @@

01-12 21:50

我要留言提醒：您尚未登入，請先登入再留言

5喜歡★NTUCSIE 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：Rat in Maze... 後一篇：count letter...

追蹤私訊切換新版閱覽

作品資料夾
未分類 (26)

colann 給 colann：
想找發明、小說、繪圖、漫畫、動畫、配音、音樂、模型的創作者們，一起交流、交友、交往！ >.0看更多我要大聲說昨天23:22


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準，可能無法使用新的應用程式來呈現網站內容，在瀏覽器支援度及網站安全性的雙重考量下，為了讓巴友們有更好的使用體驗，巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特：
。Google Chrome（推薦）
。Mozilla Firefox
。Microsoft Edge（Windows10以上的作業系統版本才可使用）

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營，請將 gamer.com.tw 加入廣告阻擋工具的白名單中，謝謝 !【教學】