#include <iostream>

// 定义节点结构
struct Node {
    int data;
    Node* next;
};

// 插入新节点到链表头部
void insertFront(Node* &head, int newData) {
    Node* newNode = new Node;
    newNode->data = newData;
    newNode->next = head;
    head = newNode;
}

// 打印链表内容
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;

    // 插入元素到链表头部
    insertFront(head, 3);
    insertFront(head, 5);
    insertFront(head, 7);

    // 打印链表内容
    std::cout << "链表内容：";
    printList(head);

    return 0;
}

#include <iostream>

// 定义节点结构
struct Node {
    int data;
    Node* next;
};

// 插入新节点到链表尾部
void insertBack(Node* &head, int newData) {
    Node* newNode = new Node;
    newNode->data = newData;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 打印链表内容
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;

    // 插入元素到链表尾部
    insertBack(head, 3);
    insertBack(head, 5);
    insertBack(head, 7);

    // 打印链表内容
    std::cout << "链表内容：";
    printList(head);

    return 0;
}

练习1：某二叉树的先序遍历结点顺序为：ABCDEFG，中序遍历结点顺序为：CBDAFGE，请画出该二叉树，并给出后序序列。

要构造并理解这棵二叉树，我们可以利用先序遍历和中序遍历的特点：

先序遍历 (Pre-order Traversal): 根 -> 左子树 -> 右子树
中序遍历 (In-order Traversal): 左子树 -> 根 -> 右子树
给定：

先序遍历：A B C D E F G
中序遍历：C B D A F G E
构造二叉树：
根节点：

从先序遍历中，第一个节点是根节点 A。
左子树和右子树的划分：

在中序遍历中，根节点 A 将序列分为左子树和右子树。A 左边的序列 CBD 是左子树，右边的序列 FGE 是右子树。
递归构造左子树：

左子树的先序遍历：B C D
左子树的中序遍历：C B D
对于左子树的根节点：

根节点是 B。
在中序遍历中，B 左边的 C 是左子树，右边的 D 是右子树。
继续递归：

对于 B 的左子树：
先序遍历：C
中序遍历：C
根节点是 C，没有左右子树。
对于 B 的右子树：
先序遍历：D
中序遍历：D
根节点是 D，没有左右子树。
递归构造右子树：

右子树的先序遍历：E F G
右子树的中序遍历：F G E
对于右子树的根节点：

根节点是 E。
在中序遍历中，E 左边的 F G 是左子树，没有右子树。
继续递归：

对于 E 的左子树：
先序遍历：F G
中序遍历：F G
根节点是 F。
在中序遍历中，F 右边的 G 是右子树。
对于 F 的右子树：
先序遍历：G
中序遍历：G
根节点是 G，没有左右子树。
构造完成的二叉树如下：
        A
       / \
      B   E
     / \ /
    C  D F
          \
           G
后序遍历 (Post-order Traversal):
后序遍历的顺序为：左子树 -> 右子树 -> 根节点。

对于这棵树：

左子树 B 的后序遍历：C D B
右子树 E 的后序遍历：G F E
整棵树的后序遍历：C D B G F E A
所以，后序遍历的结果是：

C D B G F E A

希望这个解决方案能帮助你更好地理解问题。

基于给定的序列 8, 3, 1, 10, 6, 4, 7, 14, 13 构造一棵二叉搜索树，并实现递归查找功能。

构造二叉搜索树的过程
从左到右依次插入节点：

插入 8，作为根节点。
插入 3，小于 8，放在左子树。
插入 1，小于 8 且小于 3，继续放在 3 的左子树。
插入 10，大于 8，放在右子树。
插入 6，小于 8，但大于 3，放在 3 的右子树。
插入 4，小于 8，大于 3 和 6，放在 6 的左子树。
插入 7，小于 8，大于 3 和 6，放在 6 的右子树。
插入 14，大于 8 和 10，放在 10 的右子树。
插入 13，大于 8 和 10，但小于 14，放在 14 的左子树。
构造出的二叉搜索树如下：

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

cpp
#include <iostream>

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* root, int key) {
  if (root == nullptr) {
    return new TreeNode(key);
  }
  if (key < root->val) {
    root->left = insert(root->left, key);
  } else if (key > root->val) {
    root->right = insert(root->right, key);
  }
  return root;
}

TreeNode* search(TreeNode* root, int key) {
  if (root == nullptr || root->val == key) {
    return root;
  }
  if (key < root->val) {
    return search(root->left, key);
  }
  return search(root->right, key);
}

int main() {
  // 构造二叉搜索树
  int keys[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
  TreeNode* root = nullptr;
  int size = sizeof(keys) / sizeof(keys[0]);
  for (int i = 0; i < size; ++i) {
    root = insert(root, keys[i]);
  }

  // 查找某个值
  int search_key = 7;
  TreeNode* result = search(root, search_key);
  if (result) {
    std::cout << "Found: " << result->val << std::endl;
  } else {
    std::cout << "Not found" << std::endl;
  }

  return 0;
}