swustoj利用二叉树中序及后序遍历确定该二叉树的先序序列(0983)

本文主要是介绍swustoj利用二叉树中序及后序遍历确定该二叉树的先序序列(0983)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果，要求输出其先序遍历结果。

Description

第一行为中序序列
第二行为后续序列

Input

输出为遍历二叉树得到的先序序列

Output

1 2	BFDAEGC FDBGECA

Sample Input

ABDFCEG

Sample Output

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
struct btree
{char st;btree *left, *right;
};btree* build(char *fina,char *mid,int n)//后序，中序，二叉树节点个数
{btree *b;char *p;int k;if (n <= 0)return NULL;b = new btree;b->st = *(fina + n - 1);for (p = mid; p < mid + n; p++){if (*p == *(fina+n-1))break;}k = p - mid;//表示当前根节点b->left = build(fina, mid, k);//左后序，左中序，左子树节点个数b->right = build(fina+k, p + 1, n - 1 - k);//右后序序，右中序，左子树节点个数return b;//返回根节点
}void Printf(btree *root)//先序遍历
{if (root == NULL){return;}cout << root->st;Printf(root->left);Printf(root->right);}int main()
{char zhong[1000];char first[1000];cin >> zhong >> first;btree *root = build(first, zhong, strlen(first));Printf(root);return 0;
}

这篇关于swustoj利用二叉树中序及后序遍历确定该二叉树的先序序列(0983)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！