递归求先序排列

tech2022-08-11  133

求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。

输入格式

2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出格式

1行,表示一棵二叉树的先序。

输入输出样例

输入 #1

BADC BDCA

输出 #1

ABCD

解题思路

首先要知道这些遍历的顺序:前序遍历根左右,中序遍历左根右,后序遍历左右根。

所以求前序遍历就是不断的找根节点输出。

以样例为例做一个简单的说明。

中序遍历:BADC,后序遍历:BDCA

根据后序遍历,我们可以知道二叉树的根节点是 A,输出A

知道了根节点,我们就能在中序遍历以根节点为界找到二叉树的左子树为B,右子树为DC

再回到后序遍历,就可以确定B为左子树的根节点,输出B,C为右子树的根节点,输出C

再回到中序遍历,可以确定D为左子树

再回到后序遍历,可以确定D为左子树根节点,输出D

综上,前序遍历为ABCD。

解题步骤可以总结如下:

1.在后序遍历找到根节点,输出

2.借助第一步找到的根节点,结合中序遍历,找出左子树和右子树包含的点

3.重复前两步,直到树为空

完整代码

#include <iostream> using namespace std; string zx,hx; //递归输出 void f(int zl,int zr,int hl,int hr)//中序左边界,中序右边界,后序左边界,后序右边界 { if(zl>zr) return;//树已为空,结束 cout<<hx[hr];//输出根节点 int n=zl; while(zx[n]!=hx[hr])//在中序遍历中以根节点为界,分出左子树和右子树 n++; int numl=n-zl;//左子树的节点个数 f(zl,n-1,hl,hl+numl-1);//递归遍历左子树 f(n+1,zr,hl+numl,hr-1);//递归遍历右子树 } int main() { cin>>zx>>hx; f(0,zx.length()-1,0,hx.length()-1); }
最新回复(0)