打印二叉搜索树的右子树中的所有节点

Question

我对数据结构和递归相当陌生。因此，我决定尝试实现一种方法，该方法将在此给定树中打印右侧子树的所有节点的所有值（按升序排列，即：50，65，72，91，99），就像学习经验一样。这是我正在使用的树，视觉上。我在理解如何通过正确的子树递归方面遇到了很多问题。这就是我到目前为止尝试过的方法（实际方法在底部）：class BinarySearchTree:    _root: Optional[Any]    # The left subtree, or None if the tree is empty.    _left: Optional[BinarySearchTree]    # The right subtree, or None if the tree is empty.    _right: Optional[BinarySearchTree]def __init__(self, root: Optional[Any]) -> None:    """Initialize a new BST containing only the given root value.    """    if root is None:        self._root = None        self._left = None        self._right = None    else:        self._root = root        self._left = BinarySearchTree(None)        self._right = BinarySearchTree(None)def is_empty(self) -> bool:    """Return True if this BST is empty.    >>> bst = BinarySearchTree(None)    >>> bst.is_empty()    True    """    return self._root is None# That is what I have tried doing so far.def print_right_subtree(self) -> None:    """Print the right subtree in order    >>> bst = BinarySearchTree(41)    >>> left = BinarySearchTree(20)    >>> left._left = BinarySearchTree(11)    >>> left._right = BinarySearchTree(29)    >>> left._right._right = BinarySearchTree(32)    >>> right = BinarySearchTree(65)    >>> right._left = BinarySearchTree(50)    >>> right._right = BinarySearchTree(91)    >>> right._right._left = BinarySearchTree(72)    >>> right._right._right = BinarySearchTree(99)    >>> bst._left = left    >>> bst._right = right    >>> bst.print_right_subtree()    50    65    72    91    99    """    if self.is_empty():        pass    else:        # I am not really sure what to do here...         # I have tried setting self._left = None, but that just made things even more complicated!        print(self._root)        self._right.print_right_subtree()任何帮助将不胜感激！另外，如果你们中的任何一个人有一个我可以遵循的教程，那对于像我这样的新手来说真的很棒，:)。

Answer 1

如果要打印右侧子树中的节点，则只需调用与他的右侧节点对应的树的属性即可。print_tree

首先，定义一个print_tree方法：

def print_tree(self) -> None:

    if self.is_empty():

        pass

    else:

        # you are free to do additional things here such as print node value or etc..

        self._left.print_tree()

        self._right.print_tree()

然后是print_right_subtree方法：

def print_right_subtree(self) -> None:

    self._right.print_tree() # which correspond to the print_tree of the _right attribute

Answer 2

由于您不是在要求代码本身，而是在寻求帮助来编写自己的代码......

1. 有一百万种方法可以做到这一点。有些更优化。有些写得更快。这完全取决于您的需求。

2. 在这里，我认为你需要了解一棵树是什么。你的任何子树，本身就是一棵树。所以，你必须明白，这确实意味着任何事情。例如，只有每棵树的正确分支？还是第一个右枝的所有树？也许是第二个分支？print the right tree

3. 如果我做对了（Da bum tss！），你想在你的架构上打印树的正确分支，称为根。为什么不说呢？这样，即使您想从子树开始打印树，也很容易做到这一点！I want to print all the numbers above 41

4. 您需要可视化您的算法将执行的操作。在这里，您要打印 41（主树的右分支）以上的所有数字。让我为此编写伪代码（假设您已经在值为65的根节点上：

• 我想按升序写所有数字...

• 我的根是65。我的左边是50岁，我的右边是91岁。

• 哪个是最低的？50. 它还有其他分支吗？不。打印它！

• 我的根仍然是65，我的权利是91。我的根低于我的树枝？打印它！然后转到正确的分支。

• 我的主要现在是91，我的左边是72，我的右边是99。

• 哪个是最低的？你得到了递归。

---

即使经过所有这些，您仍然可以选择使另一个更快 - 编写，而不是计算！- 解决方案。从您需要的分支中收集所有值，并打印排序的值！