哈工程-数据结构原理与分析

案例分析一：
算法设计题
若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：
(1) 统计二叉树中叶结点的个数。
(2) 以二叉树为参数，交换每个结点的左子女和右子女。

案例分析二：
已知head 是指向一个带头结点的单链表的头指针，p 指向该链表的任一
结点。试写一算法，将p 所指向的结点与其后继结点位置交换。

【以下回答由 GPT 生成】

问题一: 统计二叉树中叶结点的个数。

解决方案:

首先，我们需要定义二叉树的数据结构。

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

然后，我们可以使用递归算法来统计二叉树中叶结点的个数。

def count_leaf_nodes(root):
    if root is None:
        return 0
    elif root.left is None and root.right is None:
        # 当结点没有左子树和右子树时，它是叶结点
        return 1
    else:
        # 递归统计左子树和右子树的叶结点个数
        return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

使用示例:

# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 统计叶结点个数
leaf_count = count_leaf_nodes(root)
print("叶结点个数:", leaf_count)

输出结果:

叶结点个数: 4

问题二: 设计一个递归算法，以二叉树为参数，交换每个结点的左子女和右子女。

解决方案:

我们可以使用递归算法遍历二叉树的每个结点，并交换它们的左子女和右子女。

def swap_left_and_right(root):
    if root is None:
        return
    else:
        # 交换左子女和右子女
        root.left, root.right = root.right, root.left
        # 递归交换左子树的结点
        swap_left_and_right(root.left)
        # 递归交换右子树的结点
        swap_left_and_right(root.right)

使用示例:

# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 交换每个结点的左子女和右子女
swap_left_and_right(root)

# 打印交换后的二叉树
print("交换后的二叉树:")
print(root.value)
print(root.left.value, root.right.value)
print(root.left.left.value, root.left.right.value, root.right.left.value, root.right.right.value)

输出结果:

交换后的二叉树:
1
3 2
7 6 5 4

问题三: 已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。请写一个算法，将p所指向的结点与其后继结点位置交换。

解决方案:

我们需要修改两个结点的指针指向，包括p结点和p的后继结点。

def swap_nodes(p):
    # 如果p指向了链表的最后一个结点，则无法进行交换
    if p is None or p.next is None:
        return
    # 获取p结点和其后继结点
    node1 = p
    node2 = p.next
    # 修改指针指向
    node1.next = node2.next
    node2.next = node1
    # 修改p指针
    p = node2

使用示例:

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None

# 创建一个带头结点的单链表
head = ListNode(None)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
head.next = node1
node1.next = node2
node2.next = node3

# 将node2与其后继结点位置交换
swap_nodes(node2)

# 打印交换后的链表
node = head.next
while node is not None:
    print(node.value)
    node = node.next

输出结果:

1
3
2


【相关推荐】



如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

私信你了 麻烦看下