台灣最大程式設計社群網站
線上人數
677
 
會員總數:242755
討論主題:187717
歡迎您免費加入會員
討論區列表 >> Java >> 二元搜尋樹中序法遞迴要怎麼輸出樹的結構?
[]  
[我要回覆]
回應主題 加入我的關注話題 檢舉此篇討論 將提問者加入個人黑名單
二元搜尋樹中序法遞迴要怎麼輸出樹的結構?
價值 : 50 QP  點閱數:353 回應數:0

樓主

銓珩
門外漢
0 11
71 5
發送站內信

請問大大能夠解答說// 以中序法輸出資料,採遞迴方式 我這一段程式碼要怎麼輸出樹的結構??
提示:可參考利用 (樹高, node 在 中序法的順序) 當 一個矩陣的座標, 顯示整棵樹時 將此矩陣列印出來,每個節點座標 = (樹高, node 在 中序法的順序)

雖然有提示,但是我還是做不出來 請問有大大能夠解答嗎QQQ
讓他輸出能夠排成像這樣,但前提是5.6.7.8.10.11.13是要使用者自行輸入的值,然後我下面也有寫判斷式,只差在不會輸出成像這樣的樹狀結構,求解!!!
8
/ \
6 10
/\ / \
5 7 11 13

[code]


/**
*
* @author Bright
*/

import java.io.*;
import java.util.Scanner;
import java.util.InputMismatchException;

class Score {
int score; // 學生成績
Score llink; // 左子鏈結
Score rlink; // 右子鏈結
};

public class binarysearchtree {

Score root, ptr;
Scanner keyboard = new Scanner(System.in);

// 建構函數
binarysearchtree()
{
root = null;
}

// 新增函數; 新增一筆新的資料
public void insert_f()
{
int score = 0;
System.out.printf("\n=====INSERT DATA=====\n");
System.out.print("Enter student score: ");
score = keyboard.nextInt();
access(score);
}

// 刪除函數; 將資料從二元搜尋樹中刪除
public void delete_f()
{
int score = 0;
if (root == null) {
System.out.println("No student record!");
return;
}
System.out.printf("\n=====DELETE DATA=====\n");
System.out.print("Enter student score: ");
score = keyboard.nextInt();

removing(score);
}

// 修改函數; 修改學生成績
public void modify_f()
{
Score node;
int score;
if (root == null) { // 判斷根節點是否為null
System.out.println("No student record!");
return;
}
System.out.printf("\n=====MODIFY DATA=====\n");
System.out.print("Enter student score: ");
score = keyboard.nextInt();
if ((node = search(score)) == null)
System.out.println("Student " + score + " not found!");
else {
// 列出原資料狀況
System.out.println("Original student score: " + node.score);
System.out.print("Enter new score: ");
node.score = keyboard.nextInt();
System.out.println("Student " + score + " has been modified");
}
}
public void search_f(){
int score;
System.out.print("輸入要查詢的值: ");
score = keyboard.nextInt();

if (search(score) != null) { // 資料已存在則顯示錯誤
System.out.println("輸入的值 " + score + " 已存在!");
return;
}
else{
System.out.println("輸入的值 " + score + " 目前不存在!");
}
}

// 輸出函數; 由小至大輸出至螢幕
public void show_f()
{
if (root == null) { // 判斷根節點是否為null
System.out.println("No student record!");
return;
}
System.out.printf("\n=====SHOW DATA=====\n");
inorder(root); // 以中序法輸出資料
}

// 處理二元搜尋樹,將新增資料加入至二元搜尋樹中
public void access(int score)
{
Score node, prev = null; //prev儲存根節點來比較
if (search(score) != null) { // 資料已存在則顯示錯誤
System.out.println("Student " + score + " has existed!");
return;
}
ptr = new Score();
ptr.score = score;
ptr.llink = ptr.rlink = null; //清空新增之值之左右link
if (root == null) // 當根節點為null的狀況
{
root = ptr;
System.out.println("第一次輸入成功");
}

else { // 當根節點不為null的狀況
node = root;
while (node != null) { // 搜尋資料插入點
prev = node;
if (ptr.score < node.score)
node = node.llink;
else
node = node.rlink;
}
if (ptr.score < prev.score) //找到之後清空 l,r link
prev.llink = ptr;
else
prev.rlink = ptr;
}
}

// 將資料從二元搜尋樹中移除
public void removing(int score)
{

Score del_node;

if ((del_node = search(score)) == null) { // 找不到資料則顯示錯誤
System.out.println("您輸入的值: " + score + " 不存在!");

return;
}

// 節點不為樹葉節點的狀況
if (del_node.llink != null || del_node.rlink != null) //只要擁有左或右鏈結,就不是樹葉節點
{
System.out.println("left" + del_node.llink);
System.out.println("right" + del_node.rlink);
del_node = replace(del_node); //replace
}

else // 節點為樹葉節點的狀況
if (del_node == root) //若值為根節點
{
root = null;
}

else
connect(del_node, 'n'); //connect
del_node = null; // 釋放記憶體
System.out.println("Student " + score + " has been deleted!");
}

// 尋找刪除非樹葉節點的替代節點
public Score replace(Score node)
{
Score re_node;
// 當右子樹找不到替代節點,會搜尋左子樹是否存在替代節點
if ((re_node = search_re_r(node.rlink)) == null)
re_node = search_re_l(node.llink);
if (re_node.rlink != null) // 當替代節點有右子樹存在的狀況
connect(re_node, 'r');
else
if (re_node.llink != null) // 當替代節點有左子樹存在的狀況
connect(re_node, 'l');
else // 當替代節點為樹葉節點的狀況
connect(re_node, 'n');
node.score = re_node.score;
return re_node;
}

// 調整二元搜尋樹的鏈結,link為r表示處理右鏈結,為l表處理左鏈結,
// 為m則將鏈結指向null

public void connect(Score node, char link) //刪除樹葉節點
{
Score parent;
parent = search_p(node); // 取得父節點
if (node.score < parent.score) // 節點為父節點左子樹的狀況
if (link == 'r') //link 為 r
parent.llink = node.rlink;
else if (link == 'l') // link 為l
parent.llink = node.llink;
else // link 為 n
parent.llink = null; //父節點的左鏈結刪掉

// node 節點為父節點右子樹的狀況
else if (link == 'r') // link 為 r
parent.rlink = node.rlink;
else if (link == 'l') // link 為 l
parent.rlink = node.llink;
else // link 為 n
parent.rlink = null;
}

// 以中序法輸出資料,採遞迴方式
public void inorder(Score node)
{
if (node != null) {
inorder(node.llink);
System.out.printf("%-3d ",node.score);
inorder(node.rlink);
}
}
// 搜尋target所在節點
public Score search(int target)
{
Score node;
node = root;
while (node != null) {
if (target == node.score)
return node;
else
if (target < node.score) // target小於目前節點,往左搜尋
node = node.llink;
else // target大於目前節點,往右搜尋
node = node.rlink;
}
return node;
}

// 搜尋右子樹替代節點
Score search_re_r(Score node)
{
Score re_node;
re_node = node;
while (re_node != null && re_node.llink != null)
re_node = re_node.llink;
return re_node;
}

// 搜尋左子樹替代節點
public Score search_re_l(Score node)
{
Score re_node;
re_node = node;
while (re_node != null && re_node.rlink != null)
re_node = re_node.rlink;
return re_node;
}

// 搜尋node(我輸入的值)的父節點
Score search_p(Score node) //node為輸入的值
{
Score parent;
parent = root; //父節點
while(parent != null) { //一直到沒有父節點
if (node.score < parent.score) //比父節點小
if (node.score == parent.llink.score) //如果輸入的值等於他的左節點,那parents就是他的父節點,值接回傳
return parent;
else
parent = parent.llink;
else
if (node.score == parent.rlink.score)
return parent;
else
parent = parent.rlink;
}
return parent;
}

public static void main(String args[])
{
int option = 0;
Scanner keyboard = new Scanner(System.in);
binarysearchtree obj = new binarysearchtree();

while (true) {
System.out.println("");
System.out.println("*************************");
System.out.println(" <1> 新增 ");
System.out.println(" <2> 刪除 ");
System.out.println(" <3> 修改 ");
System.out.println(" <4> 顯示 ");
System.out.println(" <5> 查詢 ");
System.out.println(" <6> 離開 ");
System.out.println("*************************");
System.out.print("Enter your choice: ");
try {
option = keyboard.nextInt();
} catch(InputMismatchException e) {
keyboard.nextLine();
System.out.printf("Not a correctly number.\n");
System.out.printf("Try again\n\n");
}
switch (option) {
case 1:
obj.insert_f();
break;
case 2:
obj.delete_f();
break;
case 3:
obj.modify_f();
break;
case 4:
obj.show_f();
break;
case 5:
obj.search_f();
break;
case 6:
System.exit(0);
default:
System.out.println("Wrong option!");
}
}
}
}

[/code]




搜尋相關Tags的文章: [ 二元搜尋樹樹狀結構 ] ,
本篇文章發表於2017-12-22 21:38
別忘捐VP感謝幫助你的人 新手會員瞧一瞧
目前尚無任何回覆
   

回覆
如要回應,請先登入.