如何製作二叉樹？

Question

我正在MIPS上做作業，分配是在MIPS中創建一個接受雙精度浮點數並動態分配空間的二叉樹。有沒有人可以使用MIPS中的任何二叉樹示例？

Answer 1

如果您知道如何在MIPS中創建數組，則可以將二叉樹投影到數組上。它或多或少會對空間造成巨大的浪費，但它將以半簡單的方式工作。

首先確定如何在堆棧中組織節點。我將組織它：

[data to store] #presumably floating point numbers 
[address of left node] 
[address of right node] 

指定一個空值的節點，可能0x7ff ... F

指定一個空地址，大概0

創建大小的陣列：（2^n - 1）* NodeSize
其中n =從1開始計數的樹最深分支的深度，而不是0. NodeSize是描述節點所需的字數。

該數組的索引將對應於下面描述的模式。

 0 
/ \ 
    1  2 
/\ /\ 
3 4 5 6 

這將是有點困難的工作，但它應該工作。我想在技術上你要麼不需要數組索引空值，如果你管理好樹，或者如果你保持它的格式，我不需要保存其他節點的地址，因爲它們是暗示了他們的指標。所以你真的只需要一個或另一個。你應該真正選擇哪一個更容易，通過計算出你想使用地址的多少以及樹的完整程度。如果您的樹已滿，則隱含的邊可以節省空間。

tl; dr這會通過兩種方式描述一棵樹來浪費空間。刪除陣列的想法或地址。

Answer 2

我有一個類似的項目。

我的解決辦法如下：

################################################## 
# 
# Binary Search Tree - Project 1 
# 
# First Assembly Program :) 
# 
################################################## 
.data 
nl: .asciiz "\n" 
prompt1: "\nPlease select an option from the list below:\n" 
prompt2: "[A] - Add a record to the tree\n" 
prompt3: "[F] - Find a record in the tree\n" 
prompt4: "[P] - Perform a preorder traversal\n" 
prompt5: "[I] - Perform an inorder traversal\n" 
prompt6: "[Q] - Quit the program\n" 
prompt7: "\nChoose a character: " 
empty: "\nThe Tree is Empty." 
youentered: "\nYou Entered: " 
recordfound: "\nRecord Found: " 
recordnotfound: "\nRecord Not Found! " 
goodbye: "\nGoodbye!" 
addid: "\nEnter the ID to add: " 
addyear: "Enter the year: " 
addtitle: "Enter the title: " 
adddescription: "Enter the description: " 
id: "\nID: " 
year: "\nYear: " 
title: "\nTitle: " 
description: "Description: " 
#idsize: .word 0 
#optiona: 97 addrecord a 
#optionf: 102 findrecord f 
#optionp: 112 preorder p 
#optioni: 105 inorder  i 
#optionq: 113 quit  q 
################################################################### 
# 
# Note: I reuse a lot of print statements 
# This code is far from what I would call optimized 
# 
# This is my first assembly program and I'm really just 
# Happy to see it all working :) 
# 
# I spent about 18 hours writing this so lol :) 
# 
# The only thing that I've gotten to crash it so far is 
# Entering characters when it's waiting for an int :) 
# 
###################################################### 
# 
# Here is my memory setup: 
# 
# $s5 - Stores Root Node 
# $s7 - Stores Size of Tree (Not Really Necessary) 
# 
# Each New Item Contains a chunk of 344 bytes 
# The bytes are setup as such: 
# 
# 8 Bytes - [ID] 
# 8 Bytes - [Year] 
# 64 Bytes - [Title] 
# 256 Bytes - [Description] 
# 8 Bytes - [LeftNodeAddress] 
# 8 Bytes - [RightNodeAddress] 
# 
# 
# Example Tree: 
# 
#      10  -Root 
#     / \ 
#      7  15  -Branch 
#     /\ /\ 
#     6 9 12 17 -Leaf 
# 
# In Memory: 
# 
#  [Offset: 328] - [ID] - [Offset: 336] 
#    |      | 
# [Off: 328][ID][Off:336] [Off: 328][ID][Off: 336] . . . 
# 
# 
######################################################## 
.text 
################### 
##Prompt Function## 
################### 
prompt: 
li $v0, 4 
la $a0, prompt1   #Please select an option from the list below: 
syscall 

li $v0, 4 
la $a0, prompt2   #[A] - Add a record to the tree 
syscall 

li $v0, 4 
la $a0, prompt3   #[F] - Find a record in the tree 
syscall 

li $v0, 4 
la $a0, prompt4   #[P] - Preorder traversal 
syscall 

li $v0, 4 
la $a0, prompt5   #[I] - Inorder traversal 
syscall 

li $v0, 4 
la $a0, prompt6   #[Q] - Quit the program 
syscall 
################### 
##Get User Input ## 
################### 
getinput: 
li $v0, 4   #Choose a character: 
la $a0, prompt7 
syscall 

li $v0, 12   #Read a single character from console 
syscall 

move $s0, $v0 

beq $s0, 97, addrecord  #If you press 'a', addrecord 
beq $s0, 102, findrecord #If you press 'f', findrecord 
beq $s0, 112, preorder  #If you press 'p', preorder 
beq $s0, 105, inorder  #If you press 'i', inorder 
beq $s0, 113, exit  #If you press 'q', exit 

li $v0, 4   #If you press something random 
la $a0, nl   #Display new line 
syscall 

j getinput   #And ask for a new character 
################### 
## Add A Record ## 
################### 
addrecord: 
li $v0, 9   #allocate memory for new record 
li $a0, 344   #enough memory for 2 addresses and all the data 
syscall 


move $s0, $v0   #hang onto the initial address of all our info 

li $v0, 4   #prompt for ID 
la $a0, addid 
syscall 

li $v0, 5   #enter integer 
syscall 

sw $v0, 0($s0)   #store our ID into memory Offset: 0 

li $v0, 4   #prompt for add year 
la $a0, addyear 
syscall 

li $v0, 5   #enter integer 
syscall 

sw $v0, 4($s0)   #store year into our memory Offset: 4 

li $v0, 4   #prompt for add title 
la $a0, addtitle 
syscall 

li $v0, 8   #read our title into the allocated space 
la $a0, 8($s0)   #Offset: 8 
li $a1, 64 
syscall 

li $v0, 4   #prompt for add description 
la $a0, adddescription 
syscall 

li $v0, 8   #read our description into the allocated space 
la $a0, 72($s0)   #Offset: 72 
li $a1, 256 
syscall 

bne $s7, 0, setlocations #if this isn't root node let's set the locations 

add $s7, $s7, 1   #add 1 to the size of the records 

move $s5, $s0   #store this address as root node for now 

j prompt 
######################## 
##Set Memory Locations## 
######################## 
setlocations: 
move $s6, $s5   #Keep $s5 as our root and use $s6 as temporary storage 
move $s4, $s6   #Use $s4 to find the null node slot 
storelocations: 
beqz $s4, store   #If we've reached a leaf, store 
lw $t2, 0($s4)   #get ID from current node 
lw $t1, 0($s0)   #get Current ID from new node node we're adding 
ble $t1,$t2,goleft  #get left location if new node <= current node 
move $s6, $s4 
lw $s4, 336($s4)  #get node to the right if new node > current node 
li $t3, 336   #be ready to store to the right slot 
j storelocations 
goleft: 
move $s6, $s4 
lw $s4, 328($s4)  #load the node to the left 
li $t3, 328   #be ready to store to the left slot 
j storelocations 
store: 
beq $t3, 336, storeright #if $t3 was set to storeRight, then store to the right 
sw $s0, 328($s6)  #else store the new node's location into our node's left slot 
add $s7, $s7, 1   #remind our size register that it's growing 
j prompt   #back to the prompt 
storeright: 
sw $s0, 336($s6)  #store new node to the right slot 
j prompt   #back to the prompt 
######################## 
## Find Record by ID ## 
######################## 
findrecord: 
move $s6, $s5 
bne $s7, 0, search 
li $v0, 4   #if tree is empty 
la $a0, empty   #display message Tree is empty 
syscall 
j prompt   #and go wait for input 
search: 
move $s6, $s5 
li $v0, 4   #print ID: 
la $a0, id 
syscall 

li $v0, 5   #let user enter ID 
syscall 

move $t1, $v0   #store the id we're looking for in $t1 
checkagain: 
lw $t2, ($s6)   #store the id we're currently looking at 
bne $t1, $t2, checkempty #if this isn't the right ID, is it the last one? 
########################### 
##If we find the record: 
########################### 
li $v0, 4 
la $a0, recordfound  #Record Found: 
syscall 

li $v0, 4   #Print ID: 
la $a0, id 
syscall 

li $v0, 1   #Print the ID stored at $s6  [Offset: 0] 
lw $a0, 0($s6) 
syscall 

li $v0, 4   #Print Year: 
la $a0, year 
syscall 

li $v0, 1   #Print the Year stored at $s6 [Offset: 4] 
lw $a0, 4($s6) 
syscall 

li $v0, 4   #Print Title: 
la $a0, title 
syscall 

li $v0, 4   #Print the Title stored at $s6 [Offset: 8] 
la $a0, 8($s6) 
syscall 

li $v0, 4   #Print Description: 
la $a0, description 
syscall 

li $v0, 4   #Print descript stored at $s6 [Offset: 72] 
la $a0, 72($s6) 
syscall 

j getinput 

checkempty: 
ble $t1, $t2, checkleft  #If $t1 <= $t2 check the left node 
lw $s6, 336($s6)  #Otherwise check the right node 
bne $s6, 0, checkagain  #If this record isn't empty, check again 
li $v0, 4   #Otherwise 
la $a0, recordnotfound  #Record not found 
syscall 
j getinput 
checkleft: 
lw $s6, 328($s6)  #Check the left node 
bne $s6, 0, checkagain  #If the record isn't empty, check again 
li $v0, 4   #Otherwise 
la $a0, recordnotfound  #Record not found 
syscall 
j getinput 
treeempty: 
li $v0, 4   #if tree is empty 
la $a0, empty   #display message Tree is empty 
syscall 
j prompt 
##################################### 
# 
# The Inorder Function 
# 
##################################### 
inorder: 
beq $s7, 0, treeempty  #If the tree is empty display empty message 
move $s6, $s5   #$s6 is the record we're currently at 
move $t0, $s6   #t0 will iterate $s6 is our starting node 
move $t1, $t0   #t1 will be thrown on the stack to keep track of everything 
jal printinorder 
j prompt 
printinorder: 
addi $sp, $sp, -12  #allocate 8 bytes for the stack 
sw $ra, 0($sp)   #4 for the $ra variable 
sw $t1, 4($sp)   #4 for $t1 

bne $t0, 0, dontreturn  #if $t0 isn't null don't return 
lw $ra, 0($sp)   #otherwise: 
lw $t1, 4($sp)   #pop stack 
addi $sp, $sp, 12  #and prepare 
jr $ra    #to return 
dontreturn: 
move $t1, $t0   #put $t0 in $t1 
lw $t0, 328($t0)  #load the next pointer to the left 
jal printinorder  #and recurse back to printorder 
move $s6, $t1   #if we're back here, it's time to print 
j goprint   #so go print 
afterprint: 
move $t0, $t1   #after we print, move $t1 back to $t0 
lw $t0, 336($t0)  #get the next pointer to the right 
jal printinorder  #recurse to see if it's the last one 
move $s6, $t1   #if we made it here, it is, let's print 
beq $s6, $t1, done  #if we already printed this one, we're done (Root Node) 
j goprint   #Go print the node to the right 
done: 
lw $ra, 0($sp)   #if we're done, pop our stack 
lw $t1, 4($sp)   #clean it up 
addi $sp, $sp, 12  #8 bytes worth 
jr $ra    #and return 
goprint: 
li $v0, 4   #Print ID: 
la $a0, id 
syscall 

li $v0, 1   #Print the ID stored at $s6  [Offset: 0] 
lw $a0, 0($s6) 
syscall 

li $v0, 4   #Print Year: 
la $a0, year 
syscall 

li $v0, 1   #Print the Year stored at $s6 [Offset: 4] 
lw $a0, 4($s6) 
syscall 

li $v0, 4   #Print Title: 
la $a0, title 
syscall 

li $v0, 4   #Print the Title stored at $s6 [Offset: 8] 
la $a0, 8($s6) 
syscall 

li $v0, 4   #Print Description: 
la $a0, description 
syscall 

li $v0, 4   #Print descript stored at $s6 [Offset: 72] 
la $a0, 72($s6) 
syscall 

j afterprint 

##################################### 
# 
# The Preorder Function 
# 
##################################### 
preorder: 
beq $s7, 0, treeempty  #If the tree is empty display empty message 
move $s6, $s5   #$s6 is the record we're currently at 
move $t0, $s6   #t0 will iterate $s6 is our starting node 
move $t1, $t0   #t1 will be thrown on the stack to keep track of everything 
jal printpreorder 
j prompt 
printpreorder: 
addi $sp, $sp, -12  #allocate 8 bytes for the stack 
sw $ra, 0($sp)   #4 for the $ra variable 
sw $t1, 4($sp)   #4 for $t1 
bne $t0, 0, dontreturnpo #if $t0 isn't null don't return 
lw $ra, 0($sp)   #otherwise: 
lw $t1, 4($sp)   #pop stack 
addi $sp, $sp, 12  #and prepare 
jr $ra    #to return 
dontreturnpo: 
move $s6, $t0   #if we made it here, it is, let's print 
j goprintpo   #so go print 
afterprintpo: 
move $t1, $t0   #put $t0 in $t1 
lw $t0, 328($t0)  #load the next pointer to the left 
jal printpreorder  #and recurse back to printorder 
move $t0, $t1   #after we print, move $t1 back to $t0 
lw $t0, 336($t0)  #get the next pointer to the right 
jal printpreorder  #recurse to see if it's the last one 
donepo: 
lw $ra, 0($sp)   #if we're done, pop our stack 
lw $t1, 4($sp)   #clean it up 
addi $sp, $sp, 12  #8 bytes worth 
jr $ra    #and return 
goprintpo: 
li $v0, 4   #Print ID: 
la $a0, id 
syscall 

li $v0, 1   #Print the ID stored at $s6  [Offset: 0] 
lw $a0, 0($s6) 
syscall 

li $v0, 4   #Print Year: 
la $a0, year 
syscall 

li $v0, 1   #Print the Year stored at $s6 [Offset: 4] 
lw $a0, 4($s6) 
syscall 

li $v0, 4   #Print Title: 
la $a0, title 
syscall 

li $v0, 4   #Print the Title stored at $s6 [Offset: 8] 
la $a0, 8($s6) 
syscall 

li $v0, 4   #Print Description: 
la $a0, description 
syscall 

li $v0, 4   #Print descript stored at $s6 [Offset: 72] 
la $a0, 72($s6) 
syscall 

j afterprintpo 

exit: 
li $v0, 4   #Say 
la $a0, goodbye   #Goodbye! 
syscall 

li $v0, 10   #Terminate Program 
syscall