二叉链表的中序遍历代码

二叉链表的中序遍历通常会采用递归或栈的方法，以下是使用递归的Python代码示例：

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

def inorder_traversal(root):
    if root is not None:
        # 先递归遍历左子树
        inorder_traversal(root.left)
        # 然后访问根节点
        print(root.val, end=" ")
        # 最后遍历右子树
        inorder_traversal(root.right)

# 示例：
# 构建一个简单的二叉链表
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 中序遍历
inorder_traversal(root)  # 输出: 4 2 5 1 3

相关问题

二叉链表非递归中序遍历C语言代码

以下是二叉链表非递归中序遍历的C语言代码：

void inorderTraversal(BiTree T) {
    if (T == NULL)
        return;

    Stack S;
    initStack(&S);
    BiTree p = T;
    while (p || !isEmpty(S)) {
        if (p) {
            push(&S, p);
            p = p->lchild;
        } else {
            pop(&S, &p);
            visit(p);
            p = p->rchild;
        }
    }
}

其中，`BiTree`是二叉树结构体类型，包含左右子树指针；`Stack`是栈结构体类型，包含栈元素数组和栈顶指针；`initStack()`是初始化栈函数；`push()`是入栈函数；`pop()`是出栈函数；`visit()`是遍历到节点时的操作函数。

二叉链表中序遍历加括号代码C语言

在C语言中，二叉链表的中序遍历通常用于生成其对应的表达式字符串，特别是当节点值代表运算符和操作数时。给二叉树添加括号使其满足中缀表达式的规范（即先左后右），可以遵循“前序遍历”的规则，即“左、根、右”，但是需要一些额外的逻辑来确定何时插入括号。

这里是一个简单的例子，假设二叉链表的结构如下：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

中序遍历并添加括号的伪代码会是这样的：

void inorder_with_parens(TreeNode* root, char* result, int open, int close) {
    if (root == NULL) return;

    // 中序遍历左子树
    inorder_with_parens(root->left, result, open + 1, close);

    // 添加当前节点和左括号
    result = insert_at(result, open++, "(");

    // 添加当前节点
    result = append_to_string(result, to_string(root->val));

    // 如果不是最后一个节点，遍历右子树并添加右括号
    if (root->right != NULL) {
        inorder_with_parens(root->right, result, open, close);
        result = insert_at(result, close--, ")");
    }
}

char* inorder_traversal_with_parens(TreeNode* root) {
    int open = 0, close = 0;
    char* result = "";

    inorder_with_parens(root, &result, open, close);

    return result;
}

函数`insert_at`负责在字符串中间插入括号，`append_to_string`则是追加字符到结果字符串。注意，这个过程假设已经实现了`to_string`将整数值转换成字符串以及处理递归结束条件（`close >= open`）。