如何计算二进制搜索中以“W”开头的字数

Question

我必须做一个函数来计算在我的二叉搜索树中以W开头的单词数。现在，我的程序返回0，即使有一个单词以W开头

这是我的密码：

def countNodes(tree):
    count = 0 

    if tree == None:
        return count

    if tree['left'] != None:
        if tree['data'][1][0] == 'w' or tree['data'][1][0] == 'W':   
            return count+1

    if tree['right'] != None:
         if (tree['data'][1][0] == 'w' or tree['data'][1][0] == 'W'):
            return count+1

    countNodes(tree['left'])
    countNodes(tree['right'])
    return count

def main():
    myTree = None  #create an empty tree
    #Create a tree with the nodes [20, 2, 25, 14, 1, 23, 75, 93, 74]
    #Note that the add function always returns the root of the BST!
    myTree = add(myTree, [20, "Jenna"])
    myTree = add(myTree, [2, "Wendy"])
    myTree = add(myTree, [25, "Layla"])
    myTree = add(myTree, [14, "Robert"])
    myTree = add(myTree, [1, "Jamie"])
    myTree = add(myTree, [23, "Stephanie"])
    myTree = add(myTree, [75, "Jay"])
    myTree = add(myTree, [93, "Barbara"])
    myTree = add(myTree, [74, "John"])

    print(countNodes(myTree))

Answer 1

以基本情况为例，即没有树，然后返回0，否则检查单词是否以字母开头并在树的分支上递归。你知道吗

def countNodes(tree):
    if tree == None:
        return 0
    count = 1 if tree["data"][1].startswith("W") else 0
    return count + countNodes(tree["left"]) + countNodes(tree["right"])

我建议您对检查值有一个额外的参数：

def countNodes(tree, toCheck):
    if tree == None:
        return 0
    count = 1 if tree["data"][1].startswith(toCheck) else 0
    return count + countNodes(tree["left"], toCheck) + countNodes(tree["right"], toCheck)

Answer 2

因此，您只需要更改递归函数行：

countNodes(tree['left'])
countNodes(tree['right'])

相反，请执行以下操作：

count += countNodes(tree['left'])
count += countNodes(tree['right'])

当您找到一个W时，您也不需要返回，您只需要迭代您的计数器：

count = 0 

if tree == None:
    return count



if tree['left'] != None:
    if tree['data'][1][0] == 'w' or tree['data'][1][0] == 'W':

        count += 1


if tree['right'] != None:
     if (tree['data'][1][0] == 'w' or tree['data'][1][0] == 'W'):

        count += 1


count += countNodes(tree['left'])
count += countNodes(tree['right'])
return count

这样你就知道你有多个以W开头的名字了

Answer 3

因为Node类的代码在与问题一起出现的代码中丢失了，我从here中取了一些，并根据提供的数据对其进行了调整：

class Node:
    """
    Tree node: left and right child + data which can be any object
    """
    def __init__(self, data=(0,' ')):
        """
        Node constructor

        @param data node data object
        """
        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        """
        Insert new node with data
        @param data node data object to insert
        """
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data 

    def lookup(self, data, parent=None):
        """
        Lookup node containing data
        @param data node data object to look up
        @param parent node's parent
        @returns node and node's parent if found or None, None
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

    def delete(self, data):
        """
        Delete node containing data

        @param data node's content to delete
        """
        # get node containing data
        node, parent = self.lookup(data)
        if node is not None:
            children_count = node.children_count()

        if children_count == 0:
            # if node has no children, just remove it
            if parent:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            else:
                self.data = None
        elif children_count == 1:
            # if node has 1 child
            # replace node with its child
            if node.left:
                n = node.left
            else:
                n = node.right
            if parent:
                if parent.left is node:
                    parent.left = n
                else:
                    parent.right = n
                del node
            else:
                self.left = n.left
                self.right = n.right
                self.data = n.data
        else:
             # if node has 2 children
             # find its successor
             parent = node
             successor = node.right
             while successor.left:
                 parent = successor
                 successor = successor.left
             # replace node data by its successor data
             node.data = successor.data
             # fix successor's parent's child
             if parent.left == successor:
                 parent.left = successor.right
             else:
                 parent.right = successor.right 

    def print_tree(self):
        """
        Print tree content inorder
        """
        if self.left:
            self.left.print_tree()
        print( self.data, end='')
        if self.right:
            self.right.print_tree()

    def children_count(self):
        """
        Returns the number of children

        @returns number of children: 0, 1, 2
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

    def compare_trees(self, node):
        """
        Compare 2 trees

        @param node tree's root node to compare to
        @returns True if the tree passed is identical to this tree
        """
        if node is None:
            return False
        if self.data != node.data:
            return False
        res = True
        if self.left is None:
            if node.left:
                return False
        else:
            res = self.left.compare_trees(node.left)
        if res is False:
            return False
        if self.right is None:
            if node.right:
                return False
        else:
            res = self.right.compare_trees(node.right)
        return res

    def tree_data(self):
        """
        Generator to get the tree nodes data
        """
        # we use a stack to traverse the tree in a non-recursive way
        stack = []
        node = self
        while stack or node: 
            if node:
                stack.append(node)
                node = node.left
            else: # we are returning so we pop the node and we yield it
                node = stack.pop()
                yield node.data
                node = node.right

#:class node()


def countNodes(tree):
    count = 0
    if tree.data[1][0].upper() == 'W':
        count += 1
    print("visitingNode", tree.data, "count", count, "tree.data[1]", tree.data[1])
    if tree.left == None and tree.right==None:
        return count
    if tree.left != None:
        count += countNodes(tree.left)
    if tree.right != None:
        count += countNodes(tree.right)
    return count


def main():
    myTree = Node()  #create an empty tree
    #Create a tree with the nodes [20, 2, 25, 14, 1, 23, 75, 93, 74]
    #Note that the add function always returns the root of the BST!
    myTree.insert((20, "Jenna"))
    myTree.insert((2, "Wendy"))
    myTree.insert((25, "Layla"))
    myTree.insert((14, "Robert"))
    myTree.insert((1, "Jamie"))
    myTree.insert((23, "Stephanie"))
    myTree.insert((75, "Jay"))
    myTree.insert((93, "Barbara"))
    myTree.insert((74, "John"))

    print("Number of names beginning with 'W' or 'w':", countNodes(myTree))

if __name__ == '__main__':

    main()

上面代码中的countNodes()函数按预期工作并打印：

visitingNode (0, ' ') count 0 tree.data[1]  
visitingNode (20, 'Jenna') count 0 tree.data[1] Jenna
visitingNode (2, 'Wendy') count 1 tree.data[1] Wendy
visitingNode (1, 'Jamie') count 0 tree.data[1] Jamie
visitingNode (14, 'Robert') count 0 tree.data[1] Robert
visitingNode (25, 'Layla') count 0 tree.data[1] Layla
visitingNode (23, 'Stephanie') count 0 tree.data[1] Stephanie
visitingNode (75, 'Jay') count 0 tree.data[1] Jay
visitingNode (74, 'John') count 0 tree.data[1] John
visitingNode (93, 'Barbara') count 0 tree.data[1] Barbara
Number of names beginning with 'W' or 'w': 1

请注意，if tree.data[1][0].upper() == 'W':足以测试“W”和“W”两种情况，并且向下分支到根本不存在的节点（当.left为None或.right为None）是没有意义的。这使得“countNodes（）”的代码稍微短一些，并且更容易理解。你知道吗