我正在尝试插入一个二进制节点。我的代码很混乱,没有挽救的希望,所以我计划重写它(基本上我没有考虑回溯并且没有仔细思考算法)。
我正在尝试使用中序遍历插入二进制节点,但我不理解如何回溯。
我该如何在根节点为D的二叉树中搜索左子树,然后返回并搜索右子树?这可能是一个愚蠢的问题,但我被难住了。我能想到最好的方法是像这样进行:
但是当我到达底部时,我无法随着根节点返回。另外,它没有解决这样一个问题:如果我到达底部左侧节点,则必须先填写该节点的两个子节点,然后才能开始回溯。我想我这样考虑是错误的。
我正在尝试使用中序遍历插入二进制节点,但我不理解如何回溯。
D
/ \
B E
/ \ / \
A C F
我该如何在根节点为D的二叉树中搜索左子树,然后返回并搜索右子树?这可能是一个愚蠢的问题,但我被难住了。我能想到最好的方法是像这样进行:
def traverse(node):
if node is not None:
traverse(node.left)
traverse(node.right)
if (!root.hasLeftChild) {
root = root.getLeftChild();
recurse(root);
}
但是当我到达底部时,我无法随着根节点返回。另外,它没有解决这样一个问题:如果我到达底部左侧节点,则必须先填写该节点的两个子节点,然后才能开始回溯。我想我这样考虑是错误的。
B
、B->C->null->C 弹出 -> 回到 B -> D -> null -> D 弹出 -> 回到 B -> B 弹出
......这是因为,只有当两个子节点都被访问后,才会弹出父节点....在树中,如果您感到疑惑,只需了解最后一个父节点和叶子节点的操作方式,然后就能更好地理解它! :) - NoobEditor