C语言 二叉树构造问题

发布网友 发布时间：2022-04-24 05:54

我来回答

共1个回答

热心网友 时间：2023-10-03 15:00

int findMidMid(char mid[], int midBegin, int midEnd, char root)
{
for (int i = midBegin; i <= midEnd; i++)
if (root == mid[i])
return i;
}
int findFirstMid(char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midMid);
{
if (midBegin == midMid)
return firstBegin;
int curMidPos = firstBegin;
for (int i = midBegin; i < midMid; i++)
for (int j = firstBegin + 1; j <= firstEnd; j++)
{
if ((first[j] == mid[i]) && (j > curMidPos))
curMidPos = j;
}
return curMidPos;
}
//构建二叉树
TreeNode * BuildTree（char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midEnd）
{
TreeNode *root = new TreeNode();
root->value = first[firstBegin]; //前序的第一个元素即为根结点
//中序序列中找到根的位置，其左边为左子树，右边为右子树
int midMid = findMidMid(mid, midBegin, midEnd, first[firstBegin]);
//找到中序序列中左子树所有节点在前序序列中的最后位置，此时该位置的右边为右子树
int firstMid = findFirstMid(first, firstBegin, firstEnd, mid, midBegin, midMid);
if (midMid != midBegin) //如果树的根结点有左子树
root->left = BuildTree(first, firstBegin+ 1, firstMid , mid, midBegin, midMid - 1);
else
root->left = NULL;
if (midMid != midEnd) //如果树的根结点有右子树
root->right = BuildTree(first, firstMid + 1, firstEnd, mid, midMid + 1, midEnd);
else
root->right = NULL;
return root;
}
//遍历二叉树输出度1的结点
void findDegreeOne(TreeNode *root)
{
if (root == NULL)
return;
if ((root->left == NULL && root->right != NULL) ||
(root->left != NULL && root->right == NULL) )
printf("%c ", root->value);
findDegreeOne(root->left);
findDegreeOne(root->right);
}追问for (int i = midBegin; i <= midEnd; i++)
这有错误

热心网友 时间：2023-10-03 15:00

int findMidMid(char mid[], int midBegin, int midEnd, char root)
{
for (int i = midBegin; i <= midEnd; i++)
if (root == mid[i])
return i;
}
int findFirstMid(char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midMid);
{
if (midBegin == midMid)
return firstBegin;
int curMidPos = firstBegin;
for (int i = midBegin; i < midMid; i++)
for (int j = firstBegin + 1; j <= firstEnd; j++)
{
if ((first[j] == mid[i]) && (j > curMidPos))
curMidPos = j;
}
return curMidPos;
}
//构建二叉树
TreeNode * BuildTree（char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midEnd）
{
TreeNode *root = new TreeNode();
root->value = first[firstBegin]; //前序的第一个元素即为根结点
//中序序列中找到根的位置，其左边为左子树，右边为右子树
int midMid = findMidMid(mid, midBegin, midEnd, first[firstBegin]);
//找到中序序列中左子树所有节点在前序序列中的最后位置，此时该位置的右边为右子树
int firstMid = findFirstMid(first, firstBegin, firstEnd, mid, midBegin, midMid);
if (midMid != midBegin) //如果树的根结点有左子树
root->left = BuildTree(first, firstBegin+ 1, firstMid , mid, midBegin, midMid - 1);
else
root->left = NULL;
if (midMid != midEnd) //如果树的根结点有右子树
root->right = BuildTree(first, firstMid + 1, firstEnd, mid, midMid + 1, midEnd);
else
root->right = NULL;
return root;
}
//遍历二叉树输出度1的结点
void findDegreeOne(TreeNode *root)
{
if (root == NULL)
return;
if ((root->left == NULL && root->right != NULL) ||
(root->left != NULL && root->right == NULL) )
printf("%c ", root->value);
findDegreeOne(root->left);
findDegreeOne(root->right);
}追问for (int i = midBegin; i <= midEnd; i++)
这有错误