首页c语言写出由给定的二叉树先序遍历和中序遍历构造二叉树的算法

c语言写出由给定的二叉树先序遍历和中序遍历构造二叉树的算法

时间: 2024-11-28 20:17:36 浏览: 61

在C语言中，从先序遍历和中序遍历重建二叉树通常涉及到递归的方法。这里是一个简单的步骤描述： 1. 先序遍历的第一个元素是根节点，可以作为新树的根。 2. 对于剩下的先序遍历序列，找到根节点对应的值在中序遍历中的位置，这个位置左边的是左子树的节点，右边的是右子树的节点。 3. 使用同样的方法，对左右子树分别进行先序遍历和中序遍历，构建左子树和右子树。以下是伪代码形式： ```c struct TreeNode* buildTree(char* preorder[], char* inorder[], int start, int end) { if (start > end) return NULL; // 获取根节点 int rootVal = preorder[start]; struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = rootVal; // 在中序遍历中找到根节点的位置 int inorderIndex = searchInorder(inorder, start, end, rootVal); // 构建左右子树 root->left = buildTree(preorder, inorder, start + 1, inorderIndex - 1); root->right = buildTree(preorder, inorder, inorderIndex + 1, end); return root; } int searchInorder(char* inorder[], int start, int end, int val) { for (int i = start; i <= end; ++i) { if (inorder[i] == val) return i; } return -1; // 如果没找到，返回-1 } ``` 在这个例子中，`preorder`数组是先序遍历的结果，`inorder`数组是中序遍历的结果，`start`和`end`是遍历范围的起始和结束索引。

阅读全文