1定义二叉树建立函数 createBTselfRoot建立一棵二叉树；2定义递归函数preOrderself Root输出二叉树的先序遍历序列；3定义递归函数postOrderself Root输出二叉树的中序遍历序列；4定义递归函数middleOrderself Root输出二叉树的后序遍历序列；5定义函数levelOrderself Root输出二叉树的层次遍历。6参照层次遍历函数定义一个新函

class TreeNode: def init(self, val): self.val = val self.left = None self.right = None

class BinaryTree: def init(self): self.root = None

def createBT(self, Root):
    val = input("请输入节点值（输入#表示空节点）：")
    if val == "#":
        Root = None
    else:
        Root = TreeNode(val)
        Root.left = self.createBT(Root.left)
        Root.right = self.createBT(Root.right)
    return Root

def preOrder(self, Root):
    if Root:
        print(Root.val, end=" ")
        self.preOrder(Root.left)
        self.preOrder(Root.right)

def postOrder(self, Root):
    if Root:
        self.postOrder(Root.left)
        print(Root.val, end=" ")
        self.postOrder(Root.right)

def middleOrder(self, Root):
    if Root:
        self.middleOrder(Root.left)
        self.middleOrder(Root.right)
        print(Root.val, end=" ")

def levelOrder(self, Root):
    if not Root:
        return
    queue = [Root]
    while queue:
        node = queue.pop(0)
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

def findBt(self, Root, x):
    if Root:
        if Root.val == x:
            print("OK")
            return
        self.findBt(Root.left, x)
        self.findBt(Root.right, x)
    else:
        print("ERROR")

def countNode(self, Root):
    if not Root:
        return 0
    else:
        return 1 + self.countNode(Root.left) + self.countNode(Root.right)

def countLeafNode(self, Root):
    if not Root:
        return 0
    elif not Root.left and not Root.right:
        return 1
    else:
        return self.countLeafNode(Root.left) + self.countLeafNode(Root.right)

if name == "main": bt = BinaryTree() bt.root = bt.createBT(bt.root)

print("先序遍历：", end="")
bt.preOrder(bt.root)
print()

print("中序遍历：", end="")
bt.postOrder(bt.root)
print()

print("后序遍历：", end="")
bt.middleOrder(bt.root)
print()

print("层次遍历：", end="")
bt.levelOrder(bt.root)
print()

x = input("请输入要查找的节点值：")
print("查找结果：", end="")
bt.findBt(bt.root, x)

print("节点个数：", bt.countNode(bt.root))

print("叶子节点个数：", bt.countLeafNode(bt.root)