根据输入的二叉树后序序列(以单个字符作为一个结点的信息)和中序序列,来构
造一棵二叉树,然后输出该树的前序序列,以及该树中所有度为 1 的结点。
以单个字符作为一个结点的信息,构 造一棵二叉树,然后输出该树中所有度为 1 的结点。
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- 天际的海浪 2022-07-04 22:03关注
你题目的解答代码如下:#include<stdio.h> #include<stdlib.h> #define max 50 typedef char Elemtype; Elemtype pre[max], in[max], post[max]; typedef struct BTNode{ Elemtype data; struct BTNode *lchild, *rchild; }BTree; /* according to the postorder and inorder travelsal sequences to create a binary tree */ BTree* create(Elemtype postL, Elemtype postR, Elemtype inL, Elemtype inR){ if(postL > postR) return NULL; BTree *root; root = (BTree*)malloc(sizeof(BTree)); root->data = post[postR]; //后序遍历序列的最后一个结点就是当前树的根结点 int k; for(k = inL; k <= inR; k++){ if(in[k] == post[postR]) //寻找当前树的根节点在中序遍历序列中的位置 break; } int numLeft = k - inL; //root的左子树的结点总数 root->lchild = create(postL, postL + numLeft - 1, inL, k - 1); //root的左孩子所在的区间:中序 in[inL, k-1] //后序post[postL, postL + numLeft - 1] root->rchild = create(postL + numLeft, postR - 1, k + 1, inR); return root; //递归返回根结点地址 } /* preorder traversal bases on user-defined stack*/ void preorderstack(BTree *root){ BTree *stack[max]; //自定义顺序栈 int top = -1; //栈顶指针 stack[++top] = root; //根结点进栈 BTree *p; while(top != -1){ p = stack[top--]; //出栈,访问根 printf("%c", p->data); if(p->rchild != NULL) //若右孩子存在,让它进栈 stack[++top] = p->rchild; //注意,先让右孩子入栈 if(p->lchild != NULL) //若左孩子存在,让它进栈 stack[++top] = p->lchild; } } /* level-order traversal bases on user-defined stack*/ void levelorder(BTree *root){ BTree *queue[max]; //自定义顺序循环队列 int front =0, rear = 0; //队头/尾 rear = (rear +1) % max; queue[rear] = root; //根结点进队 BTree *p; while(front != rear){ front = (front + 1)%max; p = queue[front]; printf("%c", p->data); if(p->lchild != NULL){ rear = (rear + 1) % max; queue[rear] = p->lchild; } if(p->rchild != NULL){ rear = (rear + 1) % max; queue[rear] = p->rchild; } } } int main(){ int n; //树的结点个数 printf("Total number of nodes: "); scanf("%d", &n); getchar(); printf("Postorder: "); for(int i = 0; i < n; i++){ scanf("%c", &post[i]); } getchar(); printf("Inorder: "); for(int i = 0; i < n; i++){ scanf("%c", &in[i]); } BTree *root = create(0, n - 1, 0, n - 1); printf("Preorder: "); preorderstack(root); printf("\nLevelorder: "); levelorder(root); return 0; }
如有帮助,请点击我的回答下方的【采纳该答案】按钮帮忙采纳下,谢谢!
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 孟德尔随机化结果不一致
- ¥15 深度学习残差模块模型
- ¥50 怎么判断同步时序逻辑电路和异步时序逻辑电路
- ¥15 差动电流二次谐波的含量Matlab计算
- ¥15 Can/caned 总线错误问题,错误显示控制器要发1,结果总线检测到0
- ¥15 C#如何调用串口数据
- ¥15 MATLAB与单片机串口通信
- ¥15 L76k模块的GPS的使用
- ¥15 请帮我看一看数电项目如何设计
- ¥23 (标签-bug|关键词-密码错误加密)