首页 > 其他分享 >二叉树 遍历 hdu-1710-Binary Tree Traversals

二叉树 遍历 hdu-1710-Binary Tree Traversals

时间:2023-09-12 11:37:22浏览次数:41  
标签:Binary hdu 遍历 int 中序 前序 二叉树 include 节点


给出二叉树的 前序遍历 和 中序遍历,求 后序遍历。。


 


算法: 由前序遍历的第一个元素可确定左、右子树的根节点,参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。  


由前序和中序结果求后序遍历结果 树的遍历: 


给你一棵树的先序遍历结果和中序遍历的结果,让你求以后序遍历输出用递归。每次把两个数组分成三个部分,父节点,左子树,右子树,把父节点放到数组里边,重复此步骤直到重建一棵新树,  这时,数组里元素刚好是后序遍历的顺序 关键点: 


中序遍历的特点是先遍历左子树,接着根节点,然后遍历右子树。这样根节点就把左右子树隔开了。而前序遍历的特点是先访问根节点,从而实现前序遍历结果提供根节点信息, 


中序遍历提供左右子树信息,从而实现二叉树的重建



例:

Sample Input

9

1 2 4 7 3 5 8 9 6

4 7 2 1 8 5 9 3 6

Sample Output

7 4 2 8 9 5 6 3 1

递归函数调试好长时间啊。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int i,j,k;

int n;
int a[1010],b[1010];
int c[1010];
struct node
{
	int data;
	node * pl;
	node * pr;
}p[1010];

int pa;
node * dfs(int zhi,int l,int r)
{
	int t=-1;
	for(i=l;i<=r;i++)
		if(b[i]==zhi){
			t=i;
			break;
		}
	if(t==-1)
	{
		return NULL;
	}
	int ans=pa;
	pa++;
	p[ans].data=zhi;
	p[ans].pl=dfs(a[pa],l,t-1);
	if(p[ans].pl!=NULL)
	{
		pa++;
	}
	p[ans].pr=dfs(a[pa],t+1,r);
	if(p[ans].pr==NULL)
		pa--;
	return p+ans; 
}
int flag;
void post(node * pp)
{
	if(pp->pl!=NULL)
		post(pp->pl);
	if(pp->pr!=NULL)
		post(pp->pr);
	if(flag==0){
		printf("%d",pp->data);
		flag=1;
	}
	else
		printf(" %d",pp->data);
}
int main()
{
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&b[i]);
		pa=1;
		node * pp=dfs(a[pa],1,n);
		flag=0;
		post(pp);
		printf("\n");
	}
}




标签:Binary,hdu,遍历,int,中序,前序,二叉树,include,节点
From: https://blog.51cto.com/u_16244339/7443652

相关文章

  • 二叉搜索树(Binary Search Tree,BST)
    二叉搜索树(BinarySearchTree,BST)二叉搜索树(BinarySearchTree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质对于二叉搜索树的每个节点左子树中的所有节点的值都小于该节点的值右子树中的所有节点的值都大于(或等于)该节点的值对于二叉搜索树的任意节点,其......
  • 二叉树(binary tree)
    二叉树(binarytree)二叉树(BinaryTree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点:每个节点最多有两个子节点,分别称为左子节点和右子节点。左子树和右子树也是二叉树,它们的结构与父节点类似。二叉树的顺......
  • hdu1400/acwing 291 Mondriaan's Dream
    题意描述:给定一块n*m的区域,用1*2的长方形填充,长方形可以横着或竖着摆,问一共有多少种填充方案具体思路:题意没什么好说的,简单易懂,很经典的一类状态压缩问题(在棋盘中求填充方案)。观察数据,满足n,m都比较小,但是搜索的复杂度大到无法接受,考虑使用状态压缩求解此类问题......
  • #yyds干货盘点# LeetCode程序员面试金典:翻转二叉树
    题目:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]代码实现:classSolution{publicTreeNodeinvertTree(TreeNoderoot){......
  • 二叉树(顺序存储要维护关系)
                    ......
  • 二叉树的便利
         ......
  • 代码随想录:● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98
     654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树,并且输出这个......
  • Java版剑指offer:平衡二叉树
    Java版剑指offer:平衡二叉树描述输入一棵二叉树,判断该二叉树是否是平衡二叉树。在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树平衡二叉树(BalancedBinaryTree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉......
  • java版本剑指offer:在二叉树中找到两个节点的最近公共祖先
    java版本剑指offer:在二叉树中找到两个节点的最近公共祖先描述给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值o1和o2,请找到o1和o2的最近公共祖先节点。注:本题保证二叉树中每个节点的val值均不相同。示例1输入:[3,5,1,6,2,0,8,#,#,7,4],5,1返回值:3方法一:递......
  • 二叉树遍历
    #include<stdio.h>#include<stdlib.h>//定义typedefstructBiTNode{intdata;//数据域structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//创建新节点boolcreateNode(BiTree&T,intvalue){T=(BiTNode*)malloc(sizeof(BiTNode));......