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

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

由于您不是在要求代码本身，而是在寻求帮助来编写自己的代码......有一百万种方法可以做到这一点。有些更优化。有些写得更快。这完全取决于您的需求。在这里，我认为你需要了解一棵树是什么。你的任何子树，本身就是一棵树。所以，你必须明白，这确实意味着任何事情。例如，只有每棵树的正确分支？还是第一个右枝的所有树？也许是第二个分支？print the right tree如果我做对了（Da bum tss！），你想在你的架构上打印树的正确分支，称为根。为什么不说呢？这样，即使您想从子树开始打印树，也很容易做到这一点！I want to print all the numbers above 41您需要可视化您的算法将执行的操作。在这里，您要打印 41（主树的右分支）以上的所有数字。让我为此编写伪代码（假设您已经在值为65的根节点上：我想按升序写所有数字...我的根是65。我的左边是50岁，我的右边是91岁。哪个是最低的？50. 它还有其他分支吗？不。打印它！我的根仍然是65，我的权利是91。我的根低于我的树枝？打印它！然后转到正确的分支。我的主要现在是91，我的左边是72，我的右边是99。哪个是最低的？你得到了递归。即使经过所有这些，您仍然可以选择使另一个更快 - 编写，而不是计算！- 解决方案。从您需要的分支中收集所有值，并打印排序的值！