python - BST（二叉搜索树）反向级别顺序遍历没有给我正确的答案/结果

问题描述

在这个关于二叉搜索树的练习中，我真的需要你的帮助。我必须沿途从下到上，从左到右颠倒遍历顺序。这是练习：

给定一个 BST，编写一个返回值列表的函数。树的最后一个深度的元素将首先出现在输出列表中。上一个深度级别的元素接下来会出现，一直到根。相同深度的元素会从小到大出现在列表中。

elements_in_bst_by order(tree_node)# 返回一个列表

例如，如果我们使用按以下顺序插入的值创建 BST 2,1,3,0将返回此列表[0,1,3,2]

如果你不明白，我会这样解释：

            2          root level 0
          1   3        children level 1
        0              children level 2

这应该返回 0 然后 1 然后 3 然后最后 2 （根）

这是练习中给出的模块（它包含二叉搜索树代码，PS：必须使用此模块）：

class TreeNode(object):
    """A tree node with two children trees"""

    def __init__(self, data, parent=None, left=None, right=None):
        self.data = data
        self.parent = parent
        self.left = left
        self.right = right

    def search(self, value):
        """Search in a BST"""
        if self.data is None:
            return None

        if self.data == value:
            return self

        if value < self.data:
            if self.left is None:
                return None
            return self.left.search(value)

        else:
            if self.right is None:
                return None
            return self.right.search(value)

    def insert(self, value):
        """insert a node in a BST"""
        if self.data is None:
            self.data = value
            return

        if value < self.data:
            if self.left is None:
                self.left = TreeNode(value, self)
            else:
                self.left.insert(value)

        else:
            if self.right is None:
                self.right = TreeNode(value, self)
            else:
                self.right.insert(value)

这是我的代码：

import bst

def preorder(root, level, dict):

    # base case: empty tree
    if root is None:
        return
    
    # insert current node and its level into the dict
    dict.setdefault(level, []).append(root.data)
    
    # recur for left and right subtree by increasing level by 1
    if root.left is not None:
        preorder(root.left,level + 1, dict)
    if root.right is not None:    
        preorder(root.right,level + 1, dict)
    
    
    # Recursive function to do reverse level order traversal of given binary tree
def tree_levels(tree):
    list = []
    # create an empty dict to store nodes between given levels
    dict = {}
    
    # traverse the tree and insert its nodes into the dict
    # corresponding to the their level
    preorder(tree, 0, dict)
    
    # iterate through the dict in reverse order and
    # print all nodes present in very level
    for i in range(0,len(dict)):
        list.append(dict[i])
    newest = [i[0] for i in list]
    return newest
root = TreeNode(4)
root.insert(5)
root.insert(3)
root.insert(2)
root.insert(1)
tree_levels(root)

它给了我这个错误：

列表不同：[2,1] != [1,2]

预期：[2,1]

实际：[1,2]

标签： pythonpython-3.xbinary-search-tree

from queue import Queue def preorder(root): ans = [] q = Queue() q.put(root) while not q.empty(): temp = [] n = q.qsize() while n: x = q.get() n-=1 temp.append(x.data) if x.left: q.put(x.left) if x.right: q.put(x.right) ans.append(temp) print(ans[::-1]) # prints [[1], [2], [3, 5], [4]] for your example

python - BST（二叉搜索树）反向级别顺序遍历没有给我正确的答案/结果

问题描述

解决方案

推荐阅读