python - 如何检查二叉树是否已满？

Question

这里是学生。我编写了一个方法来添加到 BinaryTree 类中，该方法检查二叉树是否已满(类代码的其余部分来自 Python 教科书)。我相信它正在正常工作，但我对编码很陌生，我不知道如何在没有树的视觉的情况下检查所有叶子是否都在同一水平上。谁能看一下 isFullBinaryTree(self) 方法是否正确？快下课了。测试程序似乎有效，但我并不乐观。

我的想法是，如果我为树的每一侧编写一个计数变量，并且两侧的计数相同，那么叶子必须全部位于同一层，这将使其成为一棵完整的树。

完整代码如下:

class TreeNode:
    def __init__(self, e):
        self.element = e
        self.left = None # Point to the left node, default None
        self.right = None # Point to the right node, default None

class BinaryTree:
    def __init__(self):
        self.root = None
        self.size = 0

    # Insert element e into the binary search tree
    # Return True if the element is inserted successfully
    def insert(self, e):
        if self.root == None:
            self.root = self.createNewNode(e)  # Create a new root/Create the node for e as the root
        else:
            # Locate the parent node
            parent = None
            current = self.root
            while current != None:
                if e < current.element:
                    parent = current  # Keep the parent
                    current = current.left  # Go left
                elif e > current.element:
                    parent = current  # Keep the parent
                    current = current.right  # Go right
                else:
                    return False  # Duplicate node not inserted

            # Create a new node for e and attach it to parent
            if e < parent.element:
                parent.left = self.createNewNode(e)
            else:
                parent.right = self.createNewNode(e)
                self.size += 1  # Increase tree size

            return True  # Element inserted

    # Create a new TreeNode for element e
    def createNewNode(self, e):
        return TreeNode(e)

    # Returns true if the tree is a full binary tree
    def isFullBinaryTree(self):
        current = self.root  # Start from the root

        while current != None:
            leftNode = current.left
            rightNode = current.right
            leftCount = 0
            rightCount = 0
            while leftNode != None:
                current = leftNode
                leftNode = current.left
                leftCount += 1  # add 1 because we are moving from current one time
            while rightNode != None:
                current = rightNode
                rightNode = current.right
                rightCount += 1  # add 1 because we are moving from current one time

            if leftCount == rightCount:
                return True
            else:
                return False

        return False



def main():


    numbers = [2, 4, 3, 1, 8, 5, 6, 7, 0]
    intTree1 = BinaryTree()
    for e in numbers:
        intTree1.insert(e)

    print("\nIs intTree1 full? ", end = "")
    print(intTree1.isFullBinaryTree())

    numbers2 = [2, 4, 3, 1, 8, 5, 6, 7]
    intTree2 = BinaryTree()
    for e in numbers2:
        intTree2.insert(e)


    print("\nIs intTree2 full? ", end = "")
    print(intTree2.isFullBinaryTree())


main()

Answer 1

如果你的树看起来像/\，那么我认为它会返回 True，因为你只迭代树的外部，而不检查内部分支的完整性

我建议不要使用循环，甚至计数，而是递归

不过，您需要在 TreeNode 类上实现 isFullBinaryTree 方法才能使其正常工作。

class TreeNode:
    def __init__(self, e):
        self.element = e
        self.left = None # Point to the left node, default None
        self.right = None # Point to the right node, default None

    def isFullBinaryTree(self):
        # check if we are a leaf 
        if self.left is None and self.right is None:
            return True 
        # recursively check the left fullness 
        full_left = self.left.isFullBinaryTree() if self.left else False 
        # recursively check the right fullness 
        full_right = self.right.isFullBinaryTree() if self.right else False
        # return True if checked that both left and right are full 
        return full_left and full_right

一旦执行此操作，BinaryTree 类就可以简单地检查根是否存在以及根 TreeNode 本身是否已满。

例如

def isFullBinaryTree(self):
    return self.root.isFullBinaryTree() if self.root else False