15问答网 > 急！！！！用C（非C++）！！！已知二叉树的后序和中序遍历，构造对应的二叉树，并非递归前序遍历该二叉树

急！！！！用C（非C++）！！！已知二叉树的后序和中序遍历，构造对应的二叉树，并非递归前序遍历该二叉树

2025-03-04 05:07:00

推荐回答（2个）

回答1：

#include
#include
#include
struct treenode {/* 二叉树结构 */
struct treenode *left;
struct treenode *right;
char value;
};

struct nodelist {/* 链表结构用于非递归前序遍历该二叉树 */
struct treenode *node;
struct nodelist *next;
};

char *LRD1 = "DEBFCA"; /* 测试数据，后序 */
char *LDR1 = "DBEAFC"; /* 测试数据，中序 */

void dlrtree(struct treenode *root) /* 非递归前序遍历该二叉树 */
{
struct treenode *node = root;
struct nodelist *last = NULL, *tmp = NULL, *ptr;

/*
* 非递归前序遍历方法的思想，构造一个队列（链表）
* 不停的把当前节点的左右子树都放到队列尾部
* 遍历指针从链表头开始逐个移动到链表尾部，就是前序遍历的结果
*/
ptr = (struct nodelist *)malloc(sizeof(struct nodelist));
if (ptr == NULL)
return;
ptr->node = root;
ptr->next = NULL;
last = ptr;
printf("dlrtree:");
while(ptr != NULL)
{
node = ptr->node;
printf("%c", node->value);

if (node->left != NULL)/* 有左子树，则加入到链表尾部 */
{
tmp = (struct nodelist *)malloc(sizeof(struct nodelist));
if (tmp == NULL)
return;
last->next = tmp;
last = tmp;
tmp->next = NULL;
last->node = node->left;
}

if (node->right != NULL)/* 有右子树，则加入到链表尾部 */
{
tmp = (struct nodelist *)malloc(sizeof(struct nodelist));
if (tmp == NULL)
return;
last->next = tmp;
last = tmp;
tmp->next = NULL;
last->node = node->right;
}
tmp = ptr;
ptr = ptr->next; /* ptr指向当前遍历到的节点，处理完当前节点以后，向

后移动，并释放前一个节点内存 */
free(tmp);
}
printf("\n");
}

void replacechar(char *str)/* 用于显示二叉树使用 */
{
int i;
for (i = 0; i < strlen(str); i++)
{
if (str[i] == '+') str[i] = '|';
if (str[i] == '\\') str[i] = ' ';
if (str[i] == '-') str[i] = ' ';
}
}

void displaytree(struct treenode *root, char *deepstr) /* 图形显示一个二叉树 */
{
int l;
char *ptr;
printf("%s%c\n", deepstr, root->value);
l = strlen(deepstr) + 4;
ptr = (char *)malloc(l);
strcpy(ptr, deepstr);
replacechar(ptr);
if (root->left != NULL && root->right != NULL)
{
printf("%s |\n", ptr);
strcat(ptr, " +-");
displaytree(root->left, ptr);
strcpy(ptr, deepstr);
replacechar(ptr);
printf("%s |\n", ptr);
strcat(ptr, " \\-");
displaytree(root->right, ptr);
}
else if (root->left != NULL)
{
printf("%s |\n", ptr);
strcat(ptr, " \\-");
displaytree(root->left, ptr);
}
else if (root->right != NULL)
{
printf("%s |\n", ptr);
strcat(ptr, " \\-");
displaytree(root->left, ptr);
}

return ;

}
/* 根据后序，中序，生成一个二叉树 */
/* lrdlst是后续字串 */
/* ldrlst是中序字串 */
struct treenode *createtree(struct treenode *root, char *lrdlst, char *ldrlst)
{
char *llrd, *lldr;
char *rlrd, *rldr;
int len;
int i, k;
len = strlen(lrdlst);
/* 基本思想，取得当前这个串对应的根节点，然后分别生成左、右子树的后续和中序

字串并递归调用 */

/* 申请左右子树的字串空间 */
llrd = (char *)malloc(len + 1);
lldr = (char *)malloc(len + 1);
rlrd = (char *)malloc(len + 1);
rldr = (char *)malloc(len + 1);

/* 异常处理 */
if (llrd == NULL || lldr == NULL || rlrd == NULL || rldr == NULL)
{
if (llrd != NULL)
free(llrd);
if (lldr != NULL)
free(lldr);
if (rlrd != NULL)
free(rlrd);
if (rldr != NULL)
free(rldr);
return NULL;
}

/* 申请根节点 */
if (root == NULL && strlen(ldrlst) > 0)
{
root = (struct treenode *)malloc(sizeof(struct treenode));
if (root == NULL)
{
free(llrd);
free(lldr);
free(rlrd);
free(rldr);
return NULL;
}
}/* 这是一种错误情况要直接退出 */
else if (root == NULL && strlen(ldrlst) == 0)
{
return NULL;
}
/* 找到根节点 */
root->value = lrdlst[len - 1];

strcpy(lldr, ldrlst);
/* 判断根节点是否有左子树 */
*strchr(lldr, root->value) = 0;
if (strlen(lldr) == 0)
root->left = NULL;
else
{
/* 申请左子树的空间并递归 */
root->left = (struct treenode *)malloc(sizeof(struct treenode));
k = 0;
for (i = 0; i < len; i++)
{
if (strchr(lldr, lrdlst[i]) != NULL)
{
llrd[k++] = lrdlst[i];
}
}
llrd[k] = 0;
createtree(root->left, llrd, lldr);
}
strcpy(rldr, ldrlst);
strcpy(rldr, strchr(rldr, root->value) + 1);
/* 判断右子树情况 */
if (strlen(rldr) == 0)
root->right = NULL;
else
{
/* 同上递归 */
root->right = (struct treenode *)malloc(sizeof(struct treenode));
k = 0;
for (i = 0; i < len; i++)
{
if (strchr(rldr, lrdlst[i]) != NULL)
{
rlrd[k++] = lrdlst[i];
}
}
rlrd[k] = 0;
createtree(root->right, rlrd, rldr);
}
/* 释放临时空间 */
free(llrd);
free(lldr);
free(rlrd);
free(rldr);
return root;
}

int main()
{
struct treenode * r;
r = createtree(NULL, LRD1, LDR1);/* 创建一棵树 */
printf("Tree View\n");/* 显示树 */
displaytree(r, "");
dlrtree(r);/* 前序遍历 */
return 0;;
}

回答2：

输入树的节点，输入1结束 8 8 8 8 8 8 8 8 9 1 中序打印 8->8->8->8->8->8->8->8->9-> 后序打印 9-... //////建立树/////////////////// b_tree creat(int *date,int len) { b_tree root=NULL; in...

最新问答

开关电源纯后级功放真的有这么大功率吗？

如何应对网站反爬虫策略？如何高效地爬大量数据

急！！！！用C（非C++）！！！已知二叉树的后序和中序遍历，构造对应的二叉树，并非递归前序遍历该二叉树

普通轮式和全方位式移动机器人的区别是什么,各自有哪些特点

我家狗得了细小，今天打了针，很精神，但是在家里找到了一颗狗粮，吃了。。一颗狗粮。。。。有影响吗？

女生用什么笔记本电脑好呢？对电脑性能要求不高，牌子要硬，外观好看些的，有的话把具体型号也写上谢谢了

腊肉什么时候做

五菱宏光的刹车偏软，这个问题有没有办法解决

碳晶电热板有辐射吗？会不会有害身体健康！

小米3刷了开发版后可以OTA升级吗？