大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...