如何为二叉搜索树中的每个节点设置位置?
How can I set positions to each node inside the Binary Search Tree?
我想构建一个 BST 并将我的每个节点设置为升序排列的位置。例如,如果二叉搜索树包含 3、6、2、4,则该节点的位置应为 pos1-2、pos2-3、pos3-4、pos4-6。
这是我的 insertBST 方法
TreeNode insertBST(TreeNode parent, int value) {
if (parent == null) {
parent = new TreeNode(value);
return parent;
}
if (value <= parent.value) {
parent.leftChild = this.insertBST(parent.leftChild, value);
} else if (value >= this.root.value) {
parent.rightChild = this.insertBST(this.root.rightChild, value);
}
return parent;
}
这是我要设置位置的 inOrderTraverseBST 方法。
int count = 0;
public void inOrderTraverseBST(TreeNode root) {
if (root == null) {
return;
}
this.inOrderTraverseBST(root.leftChild);
root.position = this.count;
this.count++;
this.inOrderTraverseBST(root.rightChild);
root.position = this.count;
}
但是inOrderTraversBST方法是错误的。所以我想知道如何编写 inOrderTraverseBST 方法的方法以便将所有位置设置到节点。
只需删除最后一行。有了它,您可以在遍历右子树后重新分配一个节点的位置。
稍微简化一下
public void inOrderTraverseBST(TreeNode root) {
if (root == null) {
return;
}
this.inOrderTraverseBST(root.leftChild);
root.position = this.count++;
this.inOrderTraverseBST(root.rightChild);
}
我想构建一个 BST 并将我的每个节点设置为升序排列的位置。例如,如果二叉搜索树包含 3、6、2、4,则该节点的位置应为 pos1-2、pos2-3、pos3-4、pos4-6。 这是我的 insertBST 方法
TreeNode insertBST(TreeNode parent, int value) {
if (parent == null) {
parent = new TreeNode(value);
return parent;
}
if (value <= parent.value) {
parent.leftChild = this.insertBST(parent.leftChild, value);
} else if (value >= this.root.value) {
parent.rightChild = this.insertBST(this.root.rightChild, value);
}
return parent;
}
这是我要设置位置的 inOrderTraverseBST 方法。
int count = 0;
public void inOrderTraverseBST(TreeNode root) {
if (root == null) {
return;
}
this.inOrderTraverseBST(root.leftChild);
root.position = this.count;
this.count++;
this.inOrderTraverseBST(root.rightChild);
root.position = this.count;
}
但是inOrderTraversBST方法是错误的。所以我想知道如何编写 inOrderTraverseBST 方法的方法以便将所有位置设置到节点。
只需删除最后一行。有了它,您可以在遍历右子树后重新分配一个节点的位置。
稍微简化一下
public void inOrderTraverseBST(TreeNode root) {
if (root == null) {
return;
}
this.inOrderTraverseBST(root.leftChild);
root.position = this.count++;
this.inOrderTraverseBST(root.rightChild);
}