先序序列建立二叉树

【题目描述】

   建立如图所示的二叉树，输入先序遍历序列以建立二叉树。输出其后序遍历结果。

【样例】

ABD...CE..F..

【输出】

DBEFCA

递归和结构体实现。具体的注释都在代码里了。

步骤：

1.建立二叉树： 

struct node
{
	char value;//节点值 
	int lc,rc;//左树右树 
}tree[1024];

int cnt;//树的节点数 

int buildBT()
{
	
	char v;
	cin>>v;
	int rt=0;//空结点 
	if(v!='.')//非空结点 
	{
		++cnt;//节点数增加 
		rt=cnt;
		tree[rt].value=v;//存根结点值 
		tree[rt].lc=buildBT();//建立左子树并记录左子树结点位置 
		tree[rt].rc=buildBT();//建立右子树并记录右子树结点位置 
	}
	return rt; 
}

2.遍历二叉树

void rootLast(int rt)
{
    if(rt==0)return;//空结点直接返回 
    rootLast(tree[rt].lc);//后序遍历左子树
    rootLast(tree[rt].rc);//后序遍历右子树
    cout< 
 
运行结果：
 
1.调试结果：
 
 
2.最终运行结果：
 
 
 
 
完整代码：
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

struct node
{
	char value;//节点值 
	int lc,rc;//左树右树 
}tree[1024];

int cnt;//树的节点数 

int buildBT()
{
	
	char v;
	cin>>v;
	int rt=0;//空结点 
	if(v!='.')//非空结点 
	{
		++cnt;//节点数增加 
		rt=cnt;
		tree[rt].value=v;//存根结点值 
		tree[rt].lc=buildBT();//建立左子树并记录左子树结点位置 
		tree[rt].rc=buildBT();//建立右子树并记录右子树结点位置 
	}
	return rt; 
}
void rootLast(int rt)
{
    if(rt==0)return;//空结点直接返回 
    rootLast(tree[rt].lc);//后序遍历左子树
    rootLast(tree[rt].rc);//后序遍历右子树
    cout<