javascript - 在具有任意数量子 Node 的树中，查找 Node 是否在给定 Node 的左半子树或右半子树中

Question

问题:判断一个 Node 是在 Node root的左半子树还是右半子树中。

---

左半边和右半边的含义:假设一个 Node root有n个子 Node ，每个子 Node 都有子树。

如果 Node 编号为[1..(Math.floor(n/2))]，则称该 Node 位于root 的左半子树中。从左到右或者它是它们的一个子树中的一个 Node ，否则它在 root 的右半子树中 [(Math.floor(n/2) + 1)..n] .

左半部分的所有 Node 都得到key小于根的值，右半部分的所有 Node 都得到 key值大于根。

---

想法:预处理

对树进行中序遍历，并为adjacencyLists.node中的每个 Node 分配键(整数) .然后查询，比较key判断一个 Node 是在左半子树还是右半子树的值:

伪代码:

QUERY(root, queryNode)
  if (queryNode.key < root.key) {
    print "queryNode is in left half of root"
  } else {
    print "queryNode is in the right half of root"
  }

---

实现:

var adjacencyLists = {
  root: 'A',
  nodes: {
    A: {
      id: 'A',
      connectedNodes: ['B', 'C']
    },
    B: {
      id: 'B',
      connectedNodes: ['D', 'E']
    },
    C: {
      id: 'C',
      connectedNodes: ['F', 'G', 'H', 'Q', 'R']
    },
    D: {
      id: 'D',
      connectedNodes: []
    },
    E: {
      id: 'E',
      connectedNodes: ['K']
    },
    F: {
      id: 'F',
      connectedNodes: ['I']
    },
    G: {
      id: 'G',
      connectedNodes: ['J', 'L', 'N', 'P']
    },
    H: {
      id: 'H',
      connectedNodes: ['M', 'O']
    },
    K: {
      id: 'K',
      connectedNodes: []
    },
    I: {
      id: 'I',
      connectedNodes: []
    },
    J: {
      id: 'J',
      connectedNodes: []
    },
    L: {
      id: 'L',
      connectedNodes: []
    },
    M: {
      id: 'M',
      connectedNodes: []
    },
    N: {
      id: 'N',
      connectedNodes: []
    },
    O: {
      id: 'O',
      connectedNodes: []
    },
    P: {
      id: 'P',
      connectedNodes: []
    },
    Q: {
      id: 'Q',
      connectedNodes: []
    },
    R: {
      id: 'R',
      connectedNodes: []
    },
  }
}

var keyLookup = {};
var count = 0;

function inorderTraversalNumberingOfNodes(cur) {
  if (adjacencyLists.nodes[cur].connectedNodes.length) {
    // recurse left half subtrees
    for (let i = 0; i < Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i++) {
      inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
    }
    // recurse right half subtrees
    for (let i = Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i < adjacencyLists.nodes[cur].connectedNodes.length; i++) {
      inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
    }
    count++;
    keyLookup[cur] = { key: count };
  } else {
    count++;
    keyLookup[cur] = {key : count };
  }
}

inorderTraversalNumberingOfNodes(adjacencyLists.root);
console.log(keyLookup)

// query to determine whether a node is in the left half or right half of root

function query(rootNodeId, queryNodeId) {
  if (keyLookup[queryNodeId].key < keyLookup[rootNodeId].key) {
    console.log(`query node ${queryNodeId} is in the left half of root node ${rootNodeId}`);
  } else {
    console.log(`query node ${queryNodeId} is in the right half of root node ${rootNodeId}`);
  }
}

query('A', 'D');
query('M', 'C');

---

Node 的预期键值:邻接表的中序遍历应该为 Node 分配以下键:

{
  "D": {
    "key": 1
  },
  "K": {
    "key": 3
  },
  "E": {
    "key": 4
  },
  "B": {
    "key": 2
  },
  "I": {
    "key": 6
  },
  "F": {
    "key": 7
  },
  "J": {
    "key": 8
  },
  "L": {
    "key": 9
  },
  "N": {
    "key": 11
  },
  "P": {
    "key": 12
  },
  "G": {
    "key": 10
  },
  "M": {
    "key": 14
  },
  "O": {
    "key": 16
  },
  "H": {
    "key": 15
  },
  "Q": {
    "key": 17
  },
  "R": {
    "key": 18
  },
  "C": {
    "key": 13
  },
  "A": {
    "key": 5
  }
}

现在，在 QUERY(A, D) ，输出应该是queryNode is in left half of root , 自 1 < 5 .

我没有得到预期的答案，因为我无法分配正确的 key到 Node 。

Answer 1

可以先获取顺序，再取索引值获取边。

var adjacencyLists = { root: 'A', nodes: { A: { id: 'A', connectedNodes: ['B', 'C'] }, B: { id: 'B', connectedNodes: ['D', 'E'] }, C: { id: 'C', connectedNodes: ['F', 'G', 'H', 'Q', 'R'] }, D: { id: 'D', connectedNodes: [] }, E: { id: 'E', connectedNodes: ['K'] }, F: { id: 'F', connectedNodes: ['I'] }, G: { id: 'G', connectedNodes: ['J', 'L', 'N', 'P'] }, H: { id: 'H', connectedNodes: ['M', 'O'] }, K: { id: 'K', connectedNodes: [] }, I: { id: 'I', connectedNodes: [] }, J: { id: 'J', connectedNodes: [] }, L: { id: 'L', connectedNodes: [] }, M: { id: 'M', connectedNodes: [] }, N: { id: 'N', connectedNodes: [] }, O: { id: 'O', connectedNodes: [] }, P: { id: 'P', connectedNodes: [] }, Q: { id: 'Q', connectedNodes: [] }, R: { id: 'R', connectedNodes: [] } } },
    index = 0,
    getOrder = parent => value => {
        if (!adjacencyLists.nodes[value].connectedNodes.length) {
            adjacencyLists.nodes[value].index = adjacencyLists.nodes[value].index || ++index;
        }
        adjacencyLists.nodes[value].connectedNodes.forEach(getOrder(value));
        adjacencyLists.nodes[parent].index = adjacencyLists.nodes[parent].index || ++index;
    },
    query = (a, b) => a === b
        ? 'middle'
        : adjacencyLists.nodes[a].index < adjacencyLists.nodes[b].index
            ? 'left'
            : 'right';

getOrder('A')('A');

console.log(query('A', 'D')); // or vice versa ...?
console.log(adjacencyLists);

.as-console-wrapper { max-height: 100% !important; top: 0; }