时间戳

首页 > 解决方案 > 来自未排序数组的二叉树

data-structures - 来自未排序数组的二叉树

问题描述

我有一个记录数组，我试图从中构造一个二叉树。最终结果应该如下。-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 的输出。知道为什么会这样吗？

标签： data-structuresbinary-treepascal

解决方案

在 Pascal 中，记录是值类型，所以当你这样做时

root := binaryTree[0];

然后root是. _ _binaryTree[0]

当您在其中设置字段时，root您正在设置副本中的字段。

如果要选择反映在binaryTree数组中的更改，则必须在使用后重新分配值：

binaryTree[0] := root;

或者，使用指针，但我不确定你是否已经了解这些。

推荐阅读