题目介绍

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:
第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:
在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

Preorder: 4 1 3 2 6 5 7

分析过程

直接用题目所给的示例来分析：

1.首先根据后序遍历确定根节点

2.在中序遍历中找到根节点对应的下标

先处理父亲节点

TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd,
	vector<int>& postorder, int postorderBegin, int postorderEnd) {
	int rootValue = postorder[postorderEnd - 1];
	    TreeNode* root = new TreeNode(rootValue);	//创建父亲节点
	for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) {
		if(inorder[delimiterIndex] == rootValue) { //找到中序遍历中父亲节点对应的下标
			break;
		}
	}
}

3.计算分割区间的左右位置

计算中序遍历的左边区间边界，再计算右边区间边界，对应二叉树的先序序列创建。

root->left = traversal(inorder, inorderBegin, delimiterIndex,
    	postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
root->right = traversal(inorder, delimiterIndex + 1, inorderEnd,
    	postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);

4.终止条件

1. 当后序区间的区间长度为零时

返回nullptr

if(postorderBegin == postorderEnd) return nullptr;

2. 区间长度为1

不用额外计算区间了，区间里只有一个值，直接返回root

if(postorderEnd - postorderBegin == 1) return root;

函数代码实现

TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd, 
	vector<int>& postorder, int postorderBegin, int postorderEnd) {
    if(postorderBegin == postorderEnd) return nullptr;
    
    int rootValue = postorder[postorderEnd - 1];
    TreeNode* root = new TreeNode(rootValue);   //创建父亲节点
    
    if(postorderEnd - postorderBegin == 1) return root;
    
    int delimiterIndex;     //分割位置的下标
    for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) {
    	if(inorder[delimiterIndex] == rootValue) {	//找到中序遍历中父亲节点对应的下标
     		break;
     	}
	}
    
    root->left = traversal(inorder, inorderBegin, delimiterIndex,
    	postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
    root->right = traversal(inorder, delimiterIndex + 1, inorderEnd,
    	postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);
    
    return root;
}

完整代码

如下：

#include<bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int value):val(value), left(nullptr), right(nullptr) {}
};
TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd)
{
    if(postorderBegin == postorderEnd) return nullptr;
    
    int rootValue = postorder[postorderEnd - 1];
    TreeNode* root = new TreeNode(rootValue);   //创建父亲节点
    
    if(postorderEnd - postorderBegin == 1) return root;
    
    int delimiterIndex;     //分割位置的下标
    for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) if(inorder[delimiterIndex] == rootValue) break;
    
    root->left = traversal(inorder, inorderBegin, delimiterIndex, postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
    root->right = traversal(inorder, delimiterIndex + 1, inorderEnd, postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);
    
    return root;
}
void Preorder(TreeNode* node) {
    if(node == nullptr) return;
    cout << " " << node->val;
    Preorder(node->left);
    Preorder(node->right);
}
int main()
{
    int n;
    cin >> n;
    vector<int> inorder(n);
    vector<int> postorder(n);
    for(int i = 0; i < n; ++i) cin >> postorder[i];
    for(int i = 0; i < n; ++i) cin >> inorder[i];
    cout << "Preorder:";
    Preorder(traversal(inorder, 0, n, postorder, 0, n));
    return 0;
}

总结

后序遍历和中序遍历的容器可以放在主函数外面，这样函数在传参的时候可以少传两个参数，代码会简洁一点。

c语言下的线索二叉树的前序遍历建立，中序遍历线索化，中序遍历输出结果

结点和树数据准备

typedef char ElemType;

//线索存储标志位
//Link表示指向左右孩子的指针
//Thread表示指向前驱后继的线索
typedef enum {Link, Thread}PointerTag;

typedef struct BiThrNode
{
	char data;
	struct  BiThrNode* lchild, * rchild;
	PointerTag ltag;
	PointerTag rtag;
}BiThrNode, *BiThrTree;

BiThrTree pre;

前序遍历输入数据
//创建一颗二叉树，约定用户遵照前序遍历的方式输入数据

void CreateBiTree(BiThrTree* T)
{
	char c;
	scanf("%c", &c);
	if (' ' == c)
	{
		*T = NULL;
	}
	else
	{
		*T = (BiThrNode*)malloc(sizeof(BiThrNode));
		(*T)->data = c;
		(*T)->ltag = Link;
		(*T)->rtag = Link;

		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

//中序便利线索化

void InThreading(BiThrTree T)
{
	if (T)
	{
		//递归左孩子线索化
		InThreading(T->lchild);

		//结点处理
		//如果该节点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点
		if (!T->lchild)
		{
			T->ltag = Thread;
			T->lchild = pre;
		}

		if (!pre->rchild)
		{
			pre->rtag = Thread;
			pre->rchild = T;
		}

		pre = T;

		//递归右孩子结点化
		InThreading(T->rchild);
	}
}

//前序遍历建立线索二叉树之前需要先初始化头结点Pre

void InOrderThreading(BiThrTree *p, BiThrTree T)
{
	*p = (BiThrTree)malloc(sizeof(BiThrNode));
	(*p)->ltag = Link;
	(*p)->rtag = Thread;
	(*p)->rchild = *p;
	if (!T)
	{
		(*p)->lchild = *p;
	}
	else
	{
		(*p)->lchild = T;
		pre = *p;
		InThreading(T);
		pre->rchild = *p;
		pre->rtag = Thread;
		(*p)->rchild = pre;
	}
}

//访问数据节点的函数

void visit(char c)
{
	printf("%c", c);
}

//中序遍历二叉树，迭代法

void InOrderTraverse(BiThrTree T)
{
	BiThrTree p;
	p = T->lchild;

	while (p != T)
	{
		while (p->ltag == Link)
		{
			p = p->lchild;
		}

		visit(p->data);

		while (p->rtag == Thread && p->rchild != T)
		{
			p = p->rchild;
			visit(p->data);
		}

		p = p->rchild;
	}
}

//测试函数

void func2()
{
	BiThrTree P, T = NULL;
	CreateBiTree(&T);
	InOrderThreading(&P, T);
	printf("中序遍历输出结果为：\n");
	InOrderTraverse(P);
	printf("\n");
}

运行结果：

此处的输入为：
abcd___e__fg__h__h_i__
中序遍历的结果应该是：
dcbeagfhi
和运行截图一致
每个_都是空格，纸上的二叉树是这样的：

分析二叉树遍历的性质

根据后序和中序遍历输出先序遍历：

由上述性质，易做：

题目

code：

#include<iostream>
using namespace std;
const int N = 110;

void make_a(int *c,int *b,int n){
         if(n == 0) return;  
         int x = c[n-1];
         int i;
         for(i=0;i<n;i++)
               if(b[i] == x) break;
         cout << " " << x;
         make_a(c,b,i);
         make_a(c+i,b+i+1,n-i-1);   // 后缀是从c+i开始，是因为后缀删除的根节点是最后一个节点，并不是第i个节点，所以后缀时仍要用第i个节点，但是不需要用最后一个节点
                                    // 中缀要把第i个结点删除，所以中缀表达式是从i+1个元素开始的；（即后缀每次删最后元素，中缀删掉是中间元素）
}

int main(){
    int b[N],c[N];  // b->中缀    c->后缀
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> c[i];
    for(int i=0;i<n;i++)
        cin >> b[i];
    cout << "Preorder:";
    make_a(c,b,n);
    return 0;
}

attention：

分析后缀、中缀有差别（因为元素的位置不同）
后缀是从第i个元素（即元素c+i）开始，是因为后缀删除的根节点是最后一个节点，并不是第i个节点，所以后缀时仍要用第i个节点，但是不需要用最后一个节点
中缀要把第i个结点删除，所以中缀表达式是从i+1个元素（即元素b+i+1）开始的；（即后缀每次删最后元素，中缀删掉是中间元素）

ps

补充：树的计数

已知先序序列和中序序列可确定一棵唯一的二叉树；

已知后序序列和中序序列可确定一棵唯一的二叉树；

已知先序序列和后序序列不能确定一棵唯一的二叉树。

improve： 根据前序和中序遍历输出先序遍历 -> 传送门