数据结构输入字符序列，建立二叉链表，中序遍历二叉树，递归算法

建立二叉链表的算法步骤如下：
1. 定义二叉树结构体；
2. 定义一个栈，用于存储未构建完整的子树；
3. 从根节点开始遍历字符序列；
4. 如果当前字符为左括号，说明根节点还没有构建完整的左子树，将当前节点入栈；
5. 如果当前字符为叶子节点，则将其作为当前根节点的左儿子节点；
6. 如果当前字符为右括号，则说明当前子树已建立完整，需要回溯到根节点。此时从栈顶取出根节点，将其右儿子节点设为当前节点；
7. 重复4-6直到完成遍历。

中序遍历的递归算法如下：
1. 若根节点为空，则返回；
2. 对根节点的左子树进行递归遍历；
3. 输出当前根节点值；
4. 对根节点的右子树进行递归遍历。

实现代码如下：

struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};

void buildTree(TreeNode*& root, string& s, int& i, stack<TreeNode*>& stk) {
if (i == s.size() || s[i] == ')') return;
if (s[i] == '(') {
stk.push(root);
i++;
}
root = new TreeNode(s[i]);
if (!stk.empty() && stk.top()->left == nullptr) {
stk.top()->left = root;
} else if (!stk.empty()) {
stk.top()->right = root;
stk.pop();
}
i++;
buildTree(root->left, s, i, stk);
buildTree(root->right, s, i, stk);
}

void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
cout << root->val;
inorderTraversal(root->right);
}

int main() {
string s = "A(B(C))(D)";
int i = 0;
TreeNode* root = nullptr;
stack<TreeNode*> stk;
buildTree(root, s, i, stk);
inorderTraversal(root);
return 0;
}