2024.04.24_学习日记

Posted on 2024-04-24 In 学习日记 Views:

天气：晴
学习地点：宿舍
学习时长：4h

学习内容

链表

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def creatlist(nums):
    if not nums:  # 如果输入的列表为空
        return None  # 返回空链表
    head = Node(nums[0])  # 创建链表头节点
    cur = head  # 设置当前节点为头节点
    for i in nums[1:]:  # 遍历列表中除头节点外的元素
        cur.next = Node(i)  # 创建新节点并连接到当前节点
        cur = cur.next  # 移动到新节点
    return head  # 返回链表头节点

def printlist(head):
    if not head:  # 如果链表为空
        print('list is empty')  # 打印提示信息
    cur = head  # 设置当前节点为链表头节点
    while cur:  # 遍历链表
        print(cur.val, end=' ')  # 打印当前节点的值
        cur = cur.next  # 移动到下一个节点
    print()  # 换行

def deletenode(head):
    cur = head  # 设置当前节点为链表头节点
    while cur and cur.next:  # 遍历链表直到当前节点为空或者下一个节点为空
        if cur.val == cur.next.val:  # 如果当前节点的值等于下一个节点的值
            cur.next = cur.next.next  # 删除下一个节点
        else:  # 如果当前节点的值不等于下一个节点的值
            cur = cur.next  # 移动到下一个节点
    return head  # 返回链表头节点

while True:  # 循环输入
    try:  # 尝试读取输入
        nums = list(map(int, input().split()))  # 读取整数列表
        n = nums[0]  # 第一个元素表示链表长度
        if n == 0:  # 如果链表长度为0
            print('list is empty')  # 打印链表为空的信息
            continue  # 继续下一次循环
        nums = nums[1:]  # 去除第一个元素，得到链表值列表
        head = creatlist(nums)  # 创建链表
        printlist(head)  # 打印原始链表
        head = deletenode(head)  # 删除重复节点
        printlist(head)  # 打印删除重复节点后的链表
        
    except:  # 处理异常（例如输入结束）
        break  # 结束循环

构造二叉树

class Tree:
    def __init__(self, val=None, left=None, right=None):
        self.val = val  # 节点的值
        self.left = left  # 左子树节点
        self.right = right  # 右子树节点

def buildtree(preorder, inorder):
    if not preorder or not inorder:  # 如果先序或中序列表为空，返回 None
        return None
    rootval = preorder[0]  # 先序遍历的第一个节点为根节点
    idx = inorder.index(rootval)  # 根据根节点的值在中序列表中找到左右子树的分界点
    inorder_left = inorder[:idx]  # 中序列表中根节点左边的部分为左子树的中序遍历结果
    inorder_right = inorder[idx + 1:]  # 中序列表中根节点右边的部分为右子树的中序遍历结果
    preorder_left = preorder[1:idx + 1]  # 根据中序遍历结果确定左右子树的先序遍历结果
    preorder_right = preorder[idx + 1:]
    root = Tree(val=rootval)  # 创建当前根节点
    root.left = buildtree(preorder_left, inorder_left)  # 递归构建左子树
    root.right = buildtree(preorder_right, inorder_right)  # 递归构建右子树
    return root

def postorder(root):
    if not root:  # 如果当前节点为空，返回空列表
        return []
    left = postorder(root.left)  # 递归遍历左子树
    right = postorder(root.right)  # 递归遍历右子树
    return left + right + [root.val]  # 左子树结果 + 右子树结果 + 当前节点值

while True:
    try:
        preorder, inorder = input().split()  # 输入先序遍历和中序遍历结果
        if not preorder or not inorder:  # 如果输入为空，退出循环
            break
        root = buildtree(preorder, inorder)  # 构建二叉树
        res = postorder(root)  # 后序遍历二叉树
        print(' '.join(map(str, res)))  # 打印结果，以空格分隔
    except:
        break

二叉树遍历

class Node:
    def __init__(self, val):
        self.val = val  # 节点的值
        self.left = None  # 左子节点
        self.right = None  # 右子节点

def preorder(root):
    if not root:
        return []  # 如果根节点为空，返回空列表
    left = preorder(root.left)  # 先序遍历左子树
    right = preorder(root.right)  # 先序遍历右子树
    return [root.val] + left + right  # 根节点值 + 左子树结果 + 右子树结果

def inorder(root):
    if not root:
        return []  # 如果根节点为空，返回空列表
    left = inorder(root.left)  # 中序遍历左子树
    right = inorder(root.right)  # 中序遍历右子树
    return left + [root.val] + right  # 左子树结果 + 根节点值 + 右子树结果

def postorder(root):
    if not root:
        return []  # 如果根节点为空，返回空列表
    left = postorder(root.left)  # 后序遍历左子树
    right = postorder(root.right)  # 后序遍历右子树
    return left + right + [root.val]  # 左子树结果 + 右子树结果 + 根节点值

while True:
    try:
        n = int(input())  # 输入节点数量
        nodes = [0] * (1 + n)  # 初始化节点列表
        for i in range(n):  # 遍历节点输入
            val, left, right = input().split()  # 输入节点值、左子节点索引、右子节点索引
            left, right = int(left), int(right)  # 将字符串索引转换为整数
            if not nodes[i + 1]:  # 如果节点列表中当前位置为空
                nodes[i + 1] = Node(val)  # 创建新节点并赋值
            else:
                nodes[i + 1].val = val  # 否则更新节点的值
            if left != 0:  # 如果左子节点索引不为0
                nodes[left] = Node('x')  # 创建新节点作为左子节点
                nodes[i + 1].left = nodes[left]  # 将左子节点连接到当前节点
            if right != 0:  # 如果右子节点索引不为0
                nodes[right] = Node('x')  # 创建新节点作为右子节点
                nodes[i + 1].right = nodes[right]  # 将右子节点连接到当前节点
        root = nodes[1]  # 根节点为节点列表的第一个节点
        pre = preorder(root)  # 先序遍历结果
        ino = inorder(root)  # 中序遍历结果
        post = postorder(root)  # 后序遍历结果
        print(''.join(map(str, pre)))  # 打印先序遍历结果，以空格分隔节点的值
        print(''.join(map(str, ino)))  # 打印中序遍历结果，以空格分隔节点的值
        print(''.join(map(str, post)))  # 打印后序遍历结果，以空格分隔节点的值
    except:
        break  # 结束循环