给出前序遍历和中序遍历求二叉树_已知前序遍历和后序遍历

给出前序遍历和中序遍历求二叉树_已知前序遍历和后序遍历一、基本概念1.先序遍历(NLR)可以确定二叉树的父子结点;2.中序遍历(LNR)可以确定二叉树的左右子树;3.后序遍历(LRN)可以确定二叉树的父子结点;二、结论1.已知先序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,可以得出二叉树的后序遍历;2.已知后序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,进而可以得出二叉树的先序序列;3.综上,必须含有中序遍历(确定…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、基本概念

1.先序遍历(NLR)可以确定二叉树的父子结点

2.中序遍历(LNR)可以确定二叉树的左右子树

3.后序遍历(LRN)可以确定二叉树的父子结点

二、结论

1.已知先序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,可以得出二叉树的后序遍历;

2.已知后序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,进而可以得出二叉树的先序序列;

3.综上,必须含有中序遍历(确定二叉树左右孩子),先序遍历或者后序遍历任选一个(确定二叉树父子结点),就可以确定一棵唯一的二叉树

三、C++代码实现

1.已知先序遍历和中序遍历,打印后序遍历(见函数void postorder(string preorder, string inorder));

2.已知中序遍历和后序遍历,打印先序遍历(见函数void preorder(string inorder, string postorder));

#include<iostream>
#include<string>
using namespace std;
/*
假设根节点在中序遍历中的位置为pos,树的结点数为len,即 len=inorder.length() 
代码:pos = inorder.find(preorder[0]) or pos = inorder.find(postorder[postorder.size()-1]) 
先序遍历(NLR), 根节点编号(0), 左子树编号(1~pos), 右子树编号(pos+1~len-1) 
中序遍历(LNR), 左子树编号(0~pos-1), 根节点编号(pos), 右子树编号(pos+1~len-1)  
后序遍历(LRN), 左子树编号(0~pos-1), 右子树编号(pos~len-2), 根点编号(len-1) 
*/
void postorder(string preorder,string inorder){//由先序遍历+中序遍历序列,递归实现后序遍历 (LRN) 
	int len = preorder.length();
	if(len==0)
		return;
	if(len==1)
	{  //单个结点 
		cout<<preorder[0];
		return;
	}
	int pos=inorder.find(preorder[0]);   // 查找根节点在中序序列中的位置,通过根节点划分左右子树 
    // 类似于后序遍历过程
	postorder(preorder.substr(1,pos), inorder.substr(0,pos));//后序遍历左子树
	postorder(preorder.substr(pos+1,len-pos-1), inorder.substr(pos+1,len-pos-1));//后序遍历右子树,pos从0开始,所以len-pos-1 
	cout<<preorder[0];    //最后输出根节点 
}
void preorder(string inorder, string postorder) //由中序遍历+后序遍历序列,递归实现先序序列 (NLR)
{
	int len = postorder.length();
	if (len == 0) // 空树 
		return;     
	if(len == 1)   // 单个结点
	{
		cout<<inorder[0];
		return ;
	}
	int pos = inorder.find(postorder[len-1]);
    // 类似于先序遍历过程
	cout<<postorder[len-1]; 
	preorder(inorder.substr(0, pos),  postorder.substr(0, pos)); //先序遍历左子树 
	preorder(inorder.substr(pos+1, len-pos-1), postorder.substr(pos, len-pos-1));//先序遍历右子树 
}

int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        postorder(s1,s2);
     	// preorder(s1, s2); 
        cout<<endl;
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195380.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ubuntu20更换国内源_ubuntu更换国内源

    ubuntu20更换国内源_ubuntu更换国内源[Fedora-ftp.sjtu.edu.cn]name=Fedora12-i386baseurl=http://ftp.sjtu.edu.cn/fedora/linux/releases/12/Fedora/i386/os/enabled=1gpgcheck=0gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-fedora[Eve

  • Java安全之Commons Collections1分析(一)

    Java安全之CommonsCollections1分析(一)0x00前言在CC链中,其实具体执行过程还是比较复杂的。建议调试前先将一些前置知识的基础给看一遍。Java安全之Commons

    2021年12月12日
  • html显示毒经,谁能肩负剑三PVE王者之名?哪怕职业再强,这点恐怕都比不上毒经…「建议收藏」

    html显示毒经,谁能肩负剑三PVE王者之名?哪怕职业再强,这点恐怕都比不上毒经…「建议收藏」随着白帝江关的削弱,全民PVE的时代来临,最近打本的人是越来越多了。对于很多入坑pve的萌新来说,一个问题就来了:我玩啥职业?什么职业才是副本里的最强王者?每当面对萌新这样的提问,剑三各大门派“招生办”就立马启动了,为了证明自己才是PVE中的王者,以下几个门派就站了出来,纷纷表示要是说这个,我可就来劲了!玩最帅的气纯,下最强的镇山河首先我要推荐你玩气纯,作为pve中的常青职业,气纯凭着一手“镇山河…

    2022年10月30日
  • journalctl工具基础介绍

    journalctl工具基础介绍journalctl工具是CentOS-7才有的工具Systemd统一管理所有Unit的启动日志。带来的好处就是,可以只用journalctl一个命令,查看所有日志(内核日志和应用日志)。日志的配置文件/etc/systemd/journald.confjournalctl用法查看所有日志(默认情况下,只保存本次启动的日志)journalctl查看内核日志(不显示应用日志)journalctl-k查看系统本次启动的日志

  • emWin 介绍_emwin教程

    emWin 介绍_emwin教程一、emWin介绍emWin是Segger公司针对嵌入式平台开发的稳定、高效的图形软件库,适合用于任何图形LCD的操作应用,并可输出高质量的无锯齿的文字和图形,通过调用emWin提供的函数接口,开发嵌入式图形界面应用变得简单而快捷。二、emwWn、ucGUI、STemWin三者之间的关系1.三者都是Segger公司的产品。2.emwWn是Segger公司图形系统的正式统称。3.uc…

    2022年10月14日
  • linux抓包和分析工具_linux tcpdump 抓包

    linux抓包和分析工具_linux tcpdump 抓包实践中,通常在Linux里用tcpdump命令抓包,然后在Windows里用wireshark软件分析包。较通用的tcpdump命令:tcpdump-ieth0-s0-wpackage.cap注[对eth0进行完整数据包抓取,数据包输入保存到当前目录package.cap中,因为没有-c参数限制,须按Ctrl+C停止抓包]—————–

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号