如何在二叉树中计算以“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

因此，您唯一需要更改的是递归函数行：

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

这样你就可以知道你是否有超过1个以W开头的名字。

Answer 2

就拿基本情况来说，就是没有树，然后返回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 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()‘的代码更短，更容易理解。