如何使用Python实现链表的二叉树的中序遍历操作

2023-04-11 00:00:00 遍历 链表 如何使用

首先，需要定义链表的二叉树数据结构，可以使用节点类实现：

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

其中，val表示节点的值，left和right表示左右子树。接下来，需要构建一棵二叉树，可使用以下代码：

# 构建二叉树
root = TreeNode('p')
root.left = TreeNode('i')
root.right = TreeNode('d')
root.left.left = TreeNode('a')
root.left.right = TreeNode('n')
root.right.left = TreeNode('a')
root.right.right = TreeNode('c')
root.right.right.right = TreeNode('o')
root.right.right.right.right = TreeNode('d')

接着，实现中序遍历的操作。中序遍历是从左子树开始，然后遍历根节点，再遍历右子树。可以使用递归方式遍历整棵二叉树，代码如下：

# 中序遍历
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end='')
        inorder_traversal(root.right)

最后，调用函数完成遍历操作：

# 调用中序遍历函数
inorder_traversal(root)

完整代码如下：

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

# 构建二叉树
root = TreeNode('p')
root.left = TreeNode('i')
root.right = TreeNode('d')
root.left.left = TreeNode('a')
root.left.right = TreeNode('n')
root.right.left = TreeNode('a')
root.right.right = TreeNode('c')
root.right.right.right = TreeNode('o')
root.right.right.right.right = TreeNode('d')

# 中序遍历
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end='')
        inorder_traversal(root.right)

# 调用中序遍历函数
inorder_traversal(root)

输出结果为：aipnacodod

相关文章