Как я могу сделать машинописные указатели в c-программировании? - PullRequest
Новая
       31

Как я могу сделать машинописные указатели в c-программировании?

0 голосов
/ 04 июля 2019

Чтобы найти ближайших соседей из списка местоположений (широта, долгота), реализована функция k мерного дерева.Однако, когда я пытаюсь пройти по k-мерному дереву, я обнаружил ошибку: 

error TS2345: Argument of type 'KDTreeNode | undefined' is not assignable to parameter of type 'KDTreeNode'.

Кажется, что "указатели" назначены в левом / правом поддереве неправильно.(Я был программистом переменного тока, я не нахожу ничего, что эквивалентно в машинописи.)

Пожалуйста, прокомментируйте, как правильно назначить узлы левого / правого листа в машинописи.

полный список кодов 

export type Point = number[];

export interface KDTreeNode {
    point: Point;
    left?: KDTreeNode;
    right?: KDTreeNode;
}

export class KDTree {
    root: KDTreeNode;
    points: Point[];

    constructor(points: Point[]) {
        this.root = { point: [], left: undefined, right: undefined };
        this.points = points;

        this.buildTree(this.root, this.points);
    }

    buildTree(node: KDTreeNode, points: Point[], depth: number = 0): void {
        let axis: number = -1;
        let median: number = -1;

        // Select axis based on depth so that axis cycles through all valid values
        axis = depth % points[0].length;

        console.log("points :" + points);
        // sort point array
        points.sort((a, b) => a[axis] - b[axis]);
        console.log("points.length :" + points.length);
        console.log("points.sort :" + points);

        median = Math.floor(points.length / 2);

        // build and return node
        node.point = points[median];

        const leftPoints = points.slice(0, median);
        console.log("leftPoints.length :" + leftPoints.length);
        if (leftPoints.length) {
            node.left = { point: [], left: undefined, right: undefined };
            this.buildTree(node.left, leftPoints, depth + 1);
        }

        const rightPoints = points.slice(median + 1);
        console.log("rightPoints.length :" + rightPoints.length);
        if (rightPoints.length) {
            node.right = { point: [], left: undefined, right: undefined };
            this.buildTree(node.right, rightPoints, depth + 1);
        }
    }

    treeBrowser() {
        this.traverse(this.root);
    }

    traverse(root: KDTreeNode) {
        if (root) {
            console.log(root.point);
            this.traverse(root.right);
            this.traverse(root.left);
        }
    };
}

export const KDTreeMain = () => {
    var points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]];

    var newTree = new KDTree(points);
    newTree.treeBrowser();

};

KDTreeMain();

1 Ответ

3 голосов
/ 04 июля 2019

Ошибка говорит о том, что не так: root.right и root.left объявлены так: 

left?: KDTreeNode;
right?: KDTreeNode;

Таким образом, их тип KDTreeNode | undefined (из-за ?). Но вы пытаетесь использовать их в traverse, который принимает только KDTreeNode (не | undefined): 

traverse(root: KDTreeNode) {

Вам нужно либо:

  1. Сделать travese принять KDTreeNode | undefined или
  2. Сделайте что-нибудь, чтобы проверить, что root.rignt и root.left не undefined, прежде чем передавать их в traverse

Код в traverse проверяет, что root не undefined, поэтому вы, вероятно, просто хотите # 1: 

// #1
traverse(root?: KDTreeNode) {

Альтернативно, # 2 будет выглядеть так: 

// #2
if (root.right) {
    this.traverse(root.right);
}
if (root.left) {
    this.traverse(root.left);
}

Эти охранники сообщают компилятору TypeScript, что к моменту вызова traverse известно, что right и left не равны undefined.

...