Я реализовал рекурсивное бинарное дерево поиска и с трудом добавляю узлы после установки корня.Концептуально я знаю, что мне нужно сделать, и вытащил быстрый пример (извиняюсь, если картинка получилась странной).Регистр $ a0 будет иметь адрес переменной, содержащей указатель на корневой узел дерева (т. Е. Указатель на указатель на корневой узел).Регистр $ a1 - это число, добавляемое в дерево.Проходя по примеру, в самом начале $ a0 будет указывать на ptr_root, который будет указывать на вновь созданный корневой узел.Структура узла содержит значение текущего узла (смещение 0), указатель на левый дочерний элемент (смещение 4) и указатель на правый дочерний элемент (смещение 8).Когда вы посмотрите на код, вы увидите несколько строк, где я использую подпрограмму под названием allocate_mem, которая инициализирует структуру с этими полями длины слова.Теперь, когда build_tree снова запускается для другого числа, если есть корень, он будет возвращаться вправо или влево. Что нужно сделать, так это обновить $ a0, чтобы он теперь указывал на левого / правого дочернего элемента текущего узла.Вот где у меня проблемы. Моя программа сейчас не запускается, потому что я внес изменения, которые заставили меня использовать несуществующую память.Однако, когда он запустится, он отобразит только корневой узел.Я подозреваю, что я либо загружал значение left (вместо указателя), либо не обновлял указатель.Что меня действительно отталкивало, так это то, как я могу добраться до левого или правого ребенка и, конечно, обновить указатель.Любые идеи?
.globl allocate_mem
.globl ptr_root
#
# Name: build_tree
#
# Description: creates a new node with the provided number, and then insert
# this new node in the proper position in the binary search
# tree, updating whatever pointer is necessary.
#
# Arguments: a0 the address of the variable that contains the pointer to
# the root node of the tree (i.e., a pointer to a pointer to
# the root node).
# a1 the number to be inserted into the tree
#
build_tree:
addi $sp,$sp,-8
sw $ra, 4($sp)
sw $s0, 0($sp)
beq $a0, $zero, new_root
slt $t1, $a1, $s0
bne $t1, $zero, go_left
# lw $s0, 0($a0)
la $s0, 0($a0)
la $t5, 8($s0)
move $a0, $t5
jal build_tree
new_root:
li $a0, 3
jal allocate_mem
la $t3, ptr_root
lw $t4, 0($t3)
sw $a1, 0($v0)
sw $zero, 4($v0)
sw $zero, 8($v0)
sw $v0, 0($t3)
j finished
go_left:
# lw $s0, 0($a0)
la $s0, 0($a0)
la $t5, 4($s0)
move $a0, $t5
jal build_tree
finished:
lw $ra, 4($sp)
lw $s0, 0($sp)
addi $sp,$sp,8
jr $ra
Редактировать: Просто обновление моего прогресса.Я провел некоторое исследование и попытался заставить мою программу работать, но все же безуспешно.Я смог заставить его работать, но он все еще только устанавливает рут.Я предполагаю, что я либо перезаписываю $ a0, либо неправильно устанавливаю поддеревья.Я должен экономить $ a0 перед каждой рекурсией вниз по build_tree, но, несмотря ни на что, это либо приводит к доступу к несуществующей памяти, либо, похоже, ничего не делает.В самом верху я экспериментировал с сохранением в стеке регистра s, предназначенного для хранения $ a0, и выполнения одного слова загрузки в $ a0 с необходимым смещением, когда дело доходит до перехода влево или вправо.Но я думаю, что это не правильно.Кроме того, на рисунке я имел в виду, что 12 находится внутри корня, не уверен, о чем я думал, помещая 3, потому что это не имеет смысла.Итак, представьте, что это 12.