cyuyan 结构体

二叉树重构可以使用递归的方式来实现。具体步骤如下： 1. 定义一个结构体来表示二叉树节点，包含节点值和左右子树两个指针。 ``` struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` 2. 根据给定的前序遍历和中序遍历序列来重构二叉树。在前序遍历序列中，第一个元素为根节点，根据这个节点在中序遍历序列中找到根节点的位置，然后递归地重构左右子树。 ``` TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) { return NULL; } int rootVal = preorder[0]; TreeNode* root = new TreeNode(rootVal); int rootIdx = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin(); vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIdx); vector<int> rightInorder(inorder.begin() + rootIdx + 1, inorder.end()); vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size()); vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end()); root->left = buildTree(leftPreorder, leftInorder); root->right = buildTree(rightPreorder, rightInorder); return root; } ``` 3. 在主函数中调用 buildTree() 函数，传入前序遍历和中序遍历序列，即可得到重构后的二叉树。 ``` int main() { vector<int> preorder = {1, 2, 4, 5, 3, 6}; vector<int> inorder = {4, 2, 5, 1, 3, 6}; TreeNode* root = buildTree(preorder, inorder); // do something with the reconstructed binary tree return 0; } ```

### 使用C语言实现根据先序序列构建二叉树 为了完成此任务，程序需定义二叉树节点结构体，并编写用于创建、插入节点以及执行前序、中序和后序遍历的函数。此外，还需计算并输出叶子节点数量。 #### 定义二叉树节点结构体 ```c typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; ``` #### 创建新节点 当给定一个值时，可以使用`malloc()`分配内存来创建一个新的TreeNode实例[^1]。 ```c TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*) malloc(sizeof(TreeNode)); newNode->val = value; newNode->left = NULL; newNode->right = NULL; return newNode; } ``` #### 插入节点至二叉排序树 通过递归方式将元素按顺序插入到合适的位置，保持左子树小于根节点而右子树大于等于根节点特性。 ```c void insertBST(TreeNode **root, int key) { if (*root == NULL){ *root = createNode(key); } else{ if (key < (*root)->val) insertBST(&(*root)->left, key); else insertBST(&(*root)->right, key); } } ``` #### 构建二叉树 基于先序序列中的数据依次调用`insertBST`方法构造完整的二叉树。 ```c void buildTreeFromPreorder(TreeNode **root, const int preorder[], size_t n) { for(size_t i=0; i<n ;i++) insertBST(root,preorder[i]); } ``` #### 遍历操作 对于每种类型的遍历（前序、中序、后序），都应设计相应的辅助函数来进行递归访问各个节点。 ```c // 前序遍历 void preOrderTraversal(const TreeNode *node) { if(node != NULL){ printf("%d ", node->val); // 访问当前节点 preOrderTraversal(node->left); // 左子树 preOrderTraversal(node->right); // 右子树 } } // 中序遍历 void inOrderTraversal(const TreeNode *node) { if(node != NULL){ inOrderTraversal(node->left); // 左子树 printf("%d ", node->val); // 当前节点 inOrderTraversal(node->right); // 右子树 } } // 后序遍历 void postOrderTraversal(const TreeNode *node) { if(node != NULL){ postOrderTraversal(node->left); // 左子树 postOrderTraversal(node->right); // 右子树 printf("%d ", node->val); // 当前节点 } } ``` #### 统计叶节点数目的功能 可以通过递归来统计所有不含有任何孩子的节点总数作为叶节点数目。 ```c int countLeaves(const TreeNode *node) { if (node == NULL) return 0; if ((node->left == NULL)&&(node->right==NULL)) return 1; return countLeaves(node->left)+countLeaves(node->right); } ```