sdut 2137 数据结构实验之求二叉树后序遍历和层次遍历

2024-03-04 03:38

本文主要是介绍sdut 2137 数据结构实验之求二叉树后序遍历和层次遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数据结构实验之求二叉树后序遍历和层次遍历

Time Limit: 1000MS  Memory Limit: 65536KB
Submit  Statistic  Discuss
Problem Description

 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。

Input

 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列。

Output

每组第一行输出二叉树的后序遍历序列,第二行输出二叉树的层次遍历序列。

Example Input
2
abdegcf
dbgeafc
xnliu
lnixu
Example Output
dgebfca
abcdefg
linux
xnuli
Hint
Author
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <malloc.h>
using namespace std;
char pre[51],in[51];
typedef struct btree
{char date;btree *lchild,*rchild;
}btree;
btree *root;
btree *createbtree(char pre[],char in[],int n)
{btree *b;for(int i=0;i<n;++i){if(in[i]==pre[0]){b=(btree*)malloc(sizeof(btree));b->date=pre[0];b->lchild=createbtree(pre+1,in,i);b->rchild=createbtree(pre+i+1,in+i+1,n-i-1);return b;}}return NULL;
}
void postbtree()//非递归
{stack<btree *>Stack;btree *p=root;do{while(p!=NULL){Stack.push(p);p=p->lchild;}bool flag=true;btree *r=NULL;while(!Stack.empty()&&flag){p=Stack.top();if(p->rchild==r){Stack.pop();cout<<p->date;r=p;}else{flag=false;p=p->rchild;}}}while(!Stack.empty());cout<<endl;
}
void levelorder()
{btree *b=root;queue<btree*>Queue;Queue.push(b);while(!Queue.empty()){b=Queue.front();Queue.pop();//这个没有返回值cout<<b->date;if(b->lchild!=NULL)Queue.push(b->lchild);if(b->rchild!=NULL)Queue.push(b->rchild);}cout<<endl;
}
int main()
{int n;cin>>n;while(n--){cin>>pre>>in;root=(btree *)malloc(sizeof(btree));root=createbtree(pre,in,strlen(pre));postbtree();levelorder();}return 0;
}
后序的遍历时对应的递归代码(main函数和postorder函数:
void postbtree(btree *root)//递归
{btree *b=root;if(b!=NULL){postbtree(b->lchild);postbtree(b->rchild);cout<<b->date;}
}
int main()
{int n;cin>>n;while(n--){cin>>pre>>in;root=(btree *)malloc(sizeof(btree));root=createbtree(pre,in,strlen(pre));postbtree(root);cout<<endl;levelorder();}return 0;
}

这篇关于sdut 2137 数据结构实验之求二叉树后序遍历和层次遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/771892

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

STM32(十一):ADC数模转换器实验

AD单通道: 1.RCC开启GPIO和ADC时钟。配置ADCCLK分频器。 2.配置GPIO,把GPIO配置成模拟输入的模式。 3.配置多路开关,把左面通道接入到右面规则组列表里。 4.配置ADC转换器, 包括AD转换器和AD数据寄存器。单次转换,连续转换;扫描、非扫描;有几个通道,触发源是什么,数据对齐是左对齐还是右对齐。 5.ADC_CMD 开启ADC。 void RCC_AD

HNU-2023电路与电子学-实验3

写在前面: 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能,设计 8 重 3-1 多路复用器。 3.分析模型机的功能,设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理,设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器; 2.用 VERILOG 语言设计模型机的 8 重 2-1 多

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索