Двоичное дерево из несортированного массива - PullRequest
Новая
       73

Двоичное дерево из несортированного массива

0 голосов
/ 25 октября 2018

У меня есть массив записей, из которых я пытаюсь построить двоичное дерево.Конечный результат должен быть следующим.-1 представляет собой ноль, и если левый и правый указатели равны -1, это конечный узел. 

| Index | Left Pointer | Data | Right Pointer |
|:-----:|:------------:|:----:|:-------------:|
|   0   |       1      |  17  |       4       |
|   1   |       2      |   8  |       3       |
|   2   |      -1      |   4  |       7       |
|   3   |      -1      |  12  |       6       |
|   4   |       5      |  22  |       8       |
|   5   |      -1      |  19  |       -1      |
|   6   |      -1      |  14  |       -1      |
|   7   |      -1      |   5  |       -1      |
|   8   |       9      |  30  |       -1      |
|   9   |      -1      |  25  |       -1      |

Это мой текущий код: 

type node = record
    data : string;
    left : integer;
    right : integer;
end;

var
  binaryTree : array[0..9] of node;

procedure output;
var
    i : integer;
begin
    for i := 0 to 9 do
    begin
        writeln('Data: ' , binaryTree[i].data);
        writeln('Left: ' , binaryTree[i].left);
        writeln('Right: ' , binaryTree[i].right);
    end;
end;

procedure takeInput;
var
    i : integer;
begin
    for i := 0 to 9 do
        readln(binaryTree[i].data); 
end;

procedure initialisePointers;
var 
    i : integer;
begin
    // initialise to -1 for null
    for i := 0 to 9 do
    begin
        binaryTree[i].left := -1;
        binaryTree[i].right := -1;
    end;
end;

procedure setPointers;
var
    i : integer;
    root, currentNode : node;
begin
    // first value becomes root
    root := binaryTree[0];
    for i := 1 to 9 do
    begin
        currentNode := root;
        while true do
        begin
            if binaryTree[i].data < currentNode.data then
            begin
                if currentNode.left = -1 then
                begin
                    currentNode.left := i;
                    break;
                end
                else
                    currentNode := binaryTree[currentNode.left]
            end
            else
            begin
                if binaryTree[i].data >= currentNode.data then
                begin
                    if currentNode.right = -1 then
                    begin
                        currentNode.right := i;
                        break;
                    end
                    else
                        currentNode := binaryTree[currentNode.right]
                end;
            end;
        end;
    end;
end;

begin
    takeInput;
    initialisePointers;
    setPointers;
    output;
end.

С показанным вводомв таблице я получаю вывод всех указателей, остающихся в -1, как инициализировано.Любая идея, почему это может быть?

1 Ответ

0 голосов
/ 25 октября 2018

В Паскале записи являются типами значений, поэтому, когда вы делаете, например,

root := binaryTree[0];

, тогда root является копией из binaryTree[0].

Когда вы устанавливаете поля в root, вы настраиваете поля в копии.

Если вы хотите, чтобы выбранные изменения отражались обратно в массиве binaryTree, вы должны присвоить значение обратно послеиспользуйте:

binaryTree[0] := root;

Или используйте указатели, но я не уверен, что вы уже узнали о них.

...