中后序遍历构建二叉树（DS树）

57 阅读 0 评论 38 点赞

我是靠谱客的博主曾经衬衫，最近开发中收集的这篇文章主要介绍中后序遍历构建二叉树（DS树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题解

一般如果告诉的某种遍历序列是带有空结点位置的，则可以直接由该序列确定二叉树。而这里的序列中只包含有效结点，所以需要两个遍历序列才能够确定二叉树。
确定的方法是：可以将确定整个二叉树的过程视为确定根节点、左子树序列和右子树序列的递归过程。所以对于每个中后序序列，只需要找出其的根节点和左右子树序列就行了。根节点一定位于后序序列的最后面，然后再在中序序列中定位出根节点的位置，在其左边的就是左子树中序序列，右边的就是右子树中序序列，再根据其返回到后序序列中得到左子树后序序列和右子树后序序列。然后递归的过程和正常的构建二叉树没区别。

题目

问题 C: 中后序遍历构建二叉树（DS树）
时间限制: 1 Sec
内存限制: 128 MB
提交: 4
解决: 4
[提交][状态][讨论版]
题目描述
按中序遍历和后序遍历给出一棵二叉树，求这棵二叉树中叶子节点权值的最小值。
输入保证叶子节点的权值各不相同。
输入
测试数据有多组
对于每组测试数据，首先输入一个整数N (1 <= N <= 10000)，代表二叉树有N个节点，接下来的一行输入这棵二叉树中序遍历的结果，最后一行输入这棵二叉树后序遍历的结果
输入一直处理到文件尾(EOF)
输出
对于每组测试数据，输出一个整数，代表二叉树中叶子节点权值最小值
样例输入
7
3 2 1 4 5 7 6
3 1 2 5 6 7 4
8
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
1
255
255
样例输出
1
3
255

代码块

#include <iostream>
using namespace std;
class BiTNode
{
int data;
BiTNode *lchild, *rchild;
friend class BiTree;
};
class BiTree
{
BiTNode *root;
int num;
int minweight;
int *post;
int *in;
void CreateTree(BiTNode *&p, int *post, int *in, int n);
void PreOrderTraverse(BiTNode *p);
public:
BiTree(int n, int *s1, int *s2);
~BiTree();
void CreateTree();
void PreOrder();
};
BiTree::BiTree(int n, int *s1, int *s2)
{
num = n;
minweight = 99999;
post = new int[num];
in = new int[num];
for(int i=0; i<num; i++)
{
post[i] = s1[i];
in[i] = s2[i];
}
}
BiTree::~BiTree()
{
delete []post;
delete []in;
}
void BiTree::CreateTree()
{
CreateTree(root, post, in, num);
}
void BiTree::CreateTree(BiTNode *&p, int *post, int *in, int n)
{
int i, j;
if(n)
{//递归的条件是传入的序列是否为空
int temp = post[n-1];
p = new BiTNode;
p->data = temp;
for(i=0; i<n; i++)
if(in[i]==temp)
break;
int num1 = i;
int num2 = n-i-1;
int in1[num1], in2[num2];
for(j=0; j<n; j++)
{
if(j<i)
in1[j] = in[j];
else if(j>i)
in2[j-i-1] = in[j];
}
int post1[num1], post2[num2];
for(j=0; j<n; j++)
{
if(j<i)
post1[j] = post[j];
else if(j>=i && j<n-1)
post2[j-i] = post[j];
}
CreateTree(p->lchild, post1, in1, num1);
CreateTree(p->rchild, post2, in2, num2);
}
else
p = NULL;
}
void BiTree::PreOrder()
{
PreOrderTraverse(root);
cout<<minweight<<endl;
}
void BiTree::PreOrderTraverse(BiTNode *p)
{
if(p)
{
if(!p->lchild && !p->rchild)
if(p->data<minweight)
minweight = p->data;
PreOrderTraverse(p->lchild);
PreOrderTraverse(p->rchild);
}
}
int main(void)
{
int i, n;
while(cin>>n)
{
int in[n], post[n];
for(i=0; i<n; i++)
cin>>in[i];
for(i=0; i<n; i++)
cin>>post[i];
BiTree myTree(n, post, in);
myTree.CreateTree();
myTree.PreOrder();
}
return 0;
}