In a tree with arbitrary number of children, find whether a node is in the left half subtrees or right half subtrees of a given node

huangapple
go评论105阅读模式
英文:

In a tree with arbitrary number of children, find whether a node is in the left half subtrees or right half subtrees of a given node

问题

Question: 查找节点是否位于节点root的左半子树或右半子树中。

Meaning of left half and right half: 假设节点root有n个子节点，每个子节点都有子树。

如果一个节点是从左到右编号为[1..(Math.floor(n/2))]的节点或是其中一个子树中的节点，那么它被认为位于root的左半子树中；否则，它位于root的右半子树中[(Math.floor(n/2) + 1)..n]。

左半子树中的所有节点的key值都小于root，右半子树中的所有节点的key值都大于root。

Idea: 预处理

对树进行中序遍历，并为adjacencyLists.node中的每个节点分配key（整数）。然后，在查询时比较key值，以确定节点是否位于左半子树或右半子树：

伪代码:

  1. QUERY(root, queryNode)
  2.   if (queryNode.key < root.key) {
  3.     print "queryNode is in left half of root"
  4.   } else {
  5.     print "queryNode is in the right half of root"
  6.   }

Implementation:

  1. var adjacencyLists = {
  2.   root: 'A',
  3.   nodes: {
  4.     A: {
  5.       id: 'A',
  6.       connectedNodes: ['B', 'C']
  7.     },
  8.     // ... (其他节点的信息)
  9.   }
  10. }
  12. var keyLookup = {};
  13. var count = 0;
  15. function inorderTraversalNumberingOfNodes(cur) {
  16.   if (adjacencyLists.nodes[cur].connectedNodes.length) {
  17.     // 递归左半子树
  18.     for (let i = 0; i < Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i++) {
  19.       inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
  20.     }
  21.     // 递归右半子树
  22.     for (let i = Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i < adjacencyLists.nodes[cur].connectedNodes.length; i++) {
  23.       inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
  24.     }
  25.     count++;
  26.     keyLookup[cur] = { key: count };
  27.   } else {
  28.     count++;
  29.     keyLookup[cur] = {key : count };
  30.   }
  31. }
  33. inorderTraversalNumberingOfNodes(adjacencyLists.root);
  34. console.log(keyLookup)
  36. // 查询节点是否位于根节点的左半部分或右半部分
  38. function query(rootNodeId, queryNodeId) {
  39.   if (keyLookup[queryNodeId].key < keyLookup[rootNodeId].key) {
  40.     console.log(`query node ${queryNodeId} is in the left half of root node ${rootNodeId}`);
  41.   } else {
  42.     console.log(`query node ${queryNodeId} is in the right half of root node ${rootNodeId}`);
  43.   }
  44. }
  46. query('A', 'D');
  47. query('M', 'C');

预期节点的key值： 对邻接列表进行中序遍历应为节点分配以下key值：

  1. {
  2.   "D": {
  3.     "key": 1
  4.   },
  5.   "K": {
  6.     "key": 3
  7.   },
  8.   "E": {
  9.     "key": 4
  10.   },
  11.   "B": {
  12.     "key": 2
  13.   },
  14.   // ... (其他节点的key值)
  15. }

现在，在QUERY(A, D)上，输出应为queryNode is in left half of root，因为1 < 5。您之前未能获得预期的答案，因为未能正确分配节点的key值。

英文:

Question: To find whether a node is in the left half subtrees or the right half subtrees of a node root.

Meaning of left half and right half : Suppose a node root has n child and each of which has subtrees.

A node is said to be in the left half subtrees of root, if it is a node numbered [1..(Math.floor(n/2))] from left to right or it is a node in one of their subtrees, else it is in the right half subtrees of root [(Math.floor(n/2) + 1)..n].

All the nodes in the left half get key values less than root and all the nodes in the right half get key values greater than root.

Idea: Preprocessing

Do an inorder traversal of the tree and assign key(Whole numbers) to each node in adjacencyLists.node. Then on query, compare key values to determine whether a node is in the left half subtrees or right half subtrees:

Pseudo code:

  1. QUERY(root, queryNode)
  2. if (queryNode.key &lt; root.key) {
  3. print &quot;queryNode is in left half of root&quot;
  4. } else {
  5. print &quot;queryNode is in the right half of root&quot;
  6. }

Implementation:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. var adjacencyLists = {
  2. root: &#39;A&#39;,
  3. nodes: {
  4. A: {
  5. id: &#39;A&#39;,
  6. connectedNodes: [&#39;B&#39;, &#39;C&#39;]
  7. },
  8. B: {
  9. id: &#39;B&#39;,
  10. connectedNodes: [&#39;D&#39;, &#39;E&#39;]
  11. },
  12. C: {
  13. id: &#39;C&#39;,
  14. connectedNodes: [&#39;F&#39;, &#39;G&#39;, &#39;H&#39;, &#39;Q&#39;, &#39;R&#39;]
  15. },
  16. D: {
  17. id: &#39;D&#39;,
  18. connectedNodes: []
  19. },
  20. E: {
  21. id: &#39;E&#39;,
  22. connectedNodes: [&#39;K&#39;]
  23. },
  24. F: {
  25. id: &#39;F&#39;,
  26. connectedNodes: [&#39;I&#39;]
  27. },
  28. G: {
  29. id: &#39;G&#39;,
  30. connectedNodes: [&#39;J&#39;, &#39;L&#39;, &#39;N&#39;, &#39;P&#39;]
  31. },
  32. H: {
  33. id: &#39;H&#39;,
  34. connectedNodes: [&#39;M&#39;, &#39;O&#39;]
  35. },
  36. K: {
  37. id: &#39;K&#39;,
  38. connectedNodes: []
  39. },
  40. I: {
  41. id: &#39;I&#39;,
  42. connectedNodes: []
  43. },
  44. J: {
  45. id: &#39;J&#39;,
  46. connectedNodes: []
  47. },
  48. L: {
  49. id: &#39;L&#39;,
  50. connectedNodes: []
  51. },
  52. M: {
  53. id: &#39;M&#39;,
  54. connectedNodes: []
  55. },
  56. N: {
  57. id: &#39;N&#39;,
  58. connectedNodes: []
  59. },
  60. O: {
  61. id: &#39;O&#39;,
  62. connectedNodes: []
  63. },
  64. P: {
  65. id: &#39;P&#39;,
  66. connectedNodes: []
  67. },
  68. Q: {
  69. id: &#39;Q&#39;,
  70. connectedNodes: []
  71. },
  72. R: {
  73. id: &#39;R&#39;,
  74. connectedNodes: []
  75. },
  76. }
  77. }
  78. var keyLookup = {};
  79. var count = 0;
  80. function inorderTraversalNumberingOfNodes(cur) {
  81. if (adjacencyLists.nodes[cur].connectedNodes.length) {
  82. // recurse left half subtrees
  83. for (let i = 0; i &lt; Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i++) {
  84. inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
  85. }
  86. // recurse right half subtrees
  87. for (let i = Math.ceil(adjacencyLists.nodes[cur].connectedNodes.length / 2); i &lt; adjacencyLists.nodes[cur].connectedNodes.length; i++) {
  88. inorderTraversalNumberingOfNodes(adjacencyLists.nodes[cur].connectedNodes[i]);
  89. }
  90. count++;
  91. keyLookup[cur] = { key: count };
  92. } else {
  93. count++;
  94. keyLookup[cur] = {key : count };
  95. }
  96. }
  97. inorderTraversalNumberingOfNodes(adjacencyLists.root);
  98. console.log(keyLookup)
  99. // query to determine whether a node is in the left half or right half of root
  100. function query(rootNodeId, queryNodeId) {
  101. if (keyLookup[queryNodeId].key &lt; keyLookup[rootNodeId].key) {
  102. console.log(`query node ${queryNodeId} is in the left half of root node ${rootNodeId}`);
  103. } else {
  104. console.log(`query node ${queryNodeId} is in the right half of root node ${rootNodeId}`);
  105. }
  106. }
  107. query(&#39;A&#39;, &#39;D&#39;);
  108. query(&#39;M&#39;, &#39;C&#39;);

<!-- end snippet -->

Expected key values of nodes: An inorder traversal of the adjacency list should assign following key to nodes:

  1. {
  2. &quot;D&quot;: {
  3. &quot;key&quot;: 1
  4. },
  5. &quot;K&quot;: {
  6. &quot;key&quot;: 3
  7. },
  8. &quot;E&quot;: {
  9. &quot;key&quot;: 4
  10. },
  11. &quot;B&quot;: {
  12. &quot;key&quot;: 2
  13. },
  14. &quot;I&quot;: {
  15. &quot;key&quot;: 6
  16. },
  17. &quot;F&quot;: {
  18. &quot;key&quot;: 7
  19. },
  20. &quot;J&quot;: {
  21. &quot;key&quot;: 8
  22. },
  23. &quot;L&quot;: {
  24. &quot;key&quot;: 9
  25. },
  26. &quot;N&quot;: {
  27. &quot;key&quot;: 11
  28. },
  29. &quot;P&quot;: {
  30. &quot;key&quot;: 12
  31. },
  32. &quot;G&quot;: {
  33. &quot;key&quot;: 10
  34. },
  35. &quot;M&quot;: {
  36. &quot;key&quot;: 14
  37. },
  38. &quot;O&quot;: {
  39. &quot;key&quot;: 16
  40. },
  41. &quot;H&quot;: {
  42. &quot;key&quot;: 15
  43. },
  44. &quot;Q&quot;: {
  45. &quot;key&quot;: 17
  46. },
  47. &quot;R&quot;: {
  48. &quot;key&quot;: 18
  49. },
  50. &quot;C&quot;: {
  51. &quot;key&quot;: 13
  52. },
  53. &quot;A&quot;: {
  54. &quot;key&quot;: 5
  55. }
  56. }

Now, on QUERY(A, D), the output should be queryNode is in left half of root, since 1 &lt; 5.

I don't get the expected answer since I am unable to assign correct key to nodes.

答案1

得分: 1

你可以首先获取订单，然后获取用于获取侧边的索引值。

  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: [] } } },
  2.     index = 0,
  3.     getOrder = parent => value => {
  4.         if (!adjacencyLists.nodes[value].connectedNodes.length) {
  5.             adjacencyLists.nodes[value].index = adjacencyLists.nodes[value].index || ++index;
  6.         }
  7.         adjacencyLists.nodes[value].connectedNodes.forEach(getOrder(value));
  8.         adjacencyLists.nodes[parent].index = adjacencyLists.nodes[parent].index || ++index;
  9.     },
  10.     query = (a, b) => a === b
  11.         ? 'middle'
  12.         : adjacencyLists.nodes[a].index < adjacencyLists.nodes[b].index
  13.             ? 'left'
  14.             : 'right';
  16. getOrder('A')('A');
  18. console.log(query('A', 'D')); // 或反之亦然...?
  19. console.log(adjacencyLists);
  1. .as-console-wrapper { max-height: 100% !important; top: 0; }
英文:

You could get the order first and then take the index value for getting the side.

<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
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';

  1. getOrder(&#39;A&#39;)(&#39;A&#39;);
  2. console.log(query(&#39;A&#39;, &#39;D&#39;)); // or vice versa ...?
  3. console.log(adjacencyLists);

<!-- language: lang-css -->
.as-console-wrapper { max-height: 100% !important; top: 0; }
<!-- end snippet -->

huangapple
  • 本文由 发表于 2020年1月3日 19:08:04
  • 转载请务必保留本文链接：https://go.coder-hub.com/59577515.html
  • algorithm
  • data-structures
  • javascript
  • node.js
  • tree
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定