二叉树的基本操作功能

以下是二叉树的基本操作功能的介绍和演示：

1. 建立二叉树：根据输入的数据建立一个二叉树。

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

def createBinaryTree(data):
    if not data:
        return None
    val = data.pop(0)
    if val == '#':
        return None
    node = TreeNode(val)
    node.left = createBinaryTree(data)
    node.right = createBinaryTree(data)
    return node

data = ['A', 'B', 'D', '#', 'G', '#', '#', 'E', 'H', '#', '#', '#', 'C', 'F', '#', '#', 'I', 'K', '#', '#', '#']
root = createBinaryTree(data)

2. 前序遍历：按照根节点、左子树、右子树的顺序遍历二叉树。

def preorderTraversal(root):
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

preorder = preorderTraversal(root)
print("前序遍历结果：", preorder)

3. 中序遍历：按照左子树、根节点、右子树的顺序遍历二叉树。

def inorderTraversal(root):
    if not root:
        return []
    stack = []
    res = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

inorder = inorderTraversal(root)
print("中序遍历结果：", inorder)

4. 后序遍历：按照左子树、右子树、根节点的顺序遍历二叉树。

def postorderTraversal(root):
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

postorder = postorderTraversal(root)
print("后序遍历结果：", postorder)

5. 统计节点个数：采用递归的方式统计二叉树的节点个数。

def countNodes(root):
    if not root:
        return 0
    return 1 + countNodes(root.left) + countNodes(root.right)

count = countNodes(root)
print("二叉树的节点个数：", count)

6. 统计度为1的节点个数：采用递归的方式统计二叉树的度为1的节点个数。

def countDegreeOneNodes(root):
    if not root:
        return 0
    if (root.left and not root.right) or (not root.left and root.right):
        return 1 + countDegreeOneNodes(root.left) + countDegreeOneNodes(root.right)
    else:
        return countDegreeOneNodes(root.left) + countDegreeOneNodes(root.right)

countDegreeOne = countDegreeOneNodes(root)
print("二叉树的度为1的节点个数：", countDegreeOne)

7. 统计叶子节点个数：采用递归的方式统计二叉树的叶子节点个数。

def countLeafNodes(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return countLeafNodes(root.left) + countLeafNodes(root.right)

countLeaf = countLeafNodes(root)
print("二叉树的叶子节点个数：", countLeaf)