二叉树中每个节点的坐标

Coordinates of every node in a binary tree?

本文关键字：坐标 节点 二叉树      更新时间：2023-09-26

我有以下函数来计算二叉树中每个节点的坐标。

//x & y parameters should be untouched
//root assumed to be 0,0
function nodeCoordinates(node, x, y)
{
    if (x === undefined && y === undefined ) {x = 0; y = 0;}
    if (!node) {return;}
    console.log("Node: " + node.value + " x: " + x + " y: " + y);
    nodeCoordinates(node.left, --x, --y);
    nodeCoordinates(node.right, x+=2, y--);
}

节点与树(BST):

//Nodes for BST
function Node(val) {
    this.value = val;
    this.left = null;
    this.right = null;
}
//Binary Search Tree
function BST() {
    this.root = null;
}

对于x，如果它向左，它应该递减。右转则递增

对于y，它应该在下降一级时减少。

示例测试代码和输出:

my_BST.insert(50);
my_BST.insert(60);
my_BST.insert(55);
my_BST.insert(20);
my_BST.insert(70);
my_BST.insert(80);
my_BST.insert(10);
my_BST.insert(30);
my_BST.insert(65);
nodeCoordinates(my_BST.root);
    节点:50 x: 0 y: 0
  • 节点:20 x: -1 y: -1
  • 节点:10 x: -2 y: -2
  • 节点:30 x: 0 y: -2
  • 节点:60 x: 1 y: -1
  • 节点:55 x: 0 y: -2
  • 节点:70 x: 2 y: -2
  • 节点:65 x: 1 y: -3
  • 节点:80 x: 3 y: -3

输出是正确的，但这是通过递归传递参数的方式摆弄的结果，感觉不直观。有人能帮我解释一下发生了什么事吗?有没有更直观的方法来解决这个问题?

我将改变参数处理，而不使用赋值或自增操作符。

function nodeCoordinates(node, x, y) {
    x = x || 0;
    y = y || 0;
    if (!node) {
        return;
    }
    console.log("Node: " + node.value + " x: " + x + " y: " + y);
    nodeCoordinates(node.left, x - 1, y - 1);
    nodeCoordinates(node.right, x + 1, y - 1);
}

基本上y是树的水平，与低于零。

x具有误导性，因为节点可以具有相同的"坐标"，如

Node: 30 x: 0 y: -2
Node: 55 x: 0 y: -2
相关文章：