java - 如何为二叉搜索树中的每个节点设置位置?
问题描述
我想建立一个 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);
}
推荐阅读
- android - 如何自定义 Firebase InAppMessaging 模式/对话框 UI?
- javascript - 当它自己的状态发生变化时,反应本机复选框会折叠手风琴
- html - 如何删除表格中的水平线?
- mysql - 使用 != 条件连接两个表
- python - 如何读取 .txt 文件并与 .xlsx 合并
- azure - 在 Azure Pipelines 上安装程序
- here-api - HERE 地图 - 有没有办法让标记在地图中居中,即使地图移动了?
- python - IIS 服务器对我的 python 烧瓶应用程序的缓慢响应
- java - StringBuilder如何在Java中反向工作?
- c# - 使用 C# 进行序言查询中的未定义过程