给定 BST 中的一个节点，如何找到下一个更高的密钥？
一般方法取决于节点中是否有父链接。
如果您存储父链接
然后你选择：
- 如果当前节点有右子节点，则为右子节点的最左子节点。如果右孩子没有左孩子，那么右孩子就是你的顺序继承人。
- 向上导航父祖先节点，当您找到其左子节点是您当前所在节点的父节点时，该父节点就是原始节点的中序后继节点。
如果您有右孩子，请执行此方法（上面的情况 1）：
如果您没有合适的孩子，请执行此方法（上面的情况 2）：
如果您不存储父链接
然后，您需要对树进行完整扫描，通常使用堆栈跟踪节点，以便您拥有必要的信息，基本上可以执行与依赖父链接的第一个方法相同的操作。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
