实习题目：唯一的确定一棵二叉树

一、上机实习题目与要求

问题描述

如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。

基本要求

已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：

（1）构造一棵二叉树；

（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3）对该二叉树进行后序遍历，输出后序遍历序列。

（4）用凹入法输出该二叉树。

二、数据结构设计

选择二叉链表的二叉树作为存储结构。

这个题主要是构建一颗二叉树以及进行对应的遍历与输出函数，因此数据结构类型肯定选择二叉树。一般来说，形态剧烈变化的二叉树不适合使用数组存储，相比较而言二叉链表更加灵活，便于树形态的改变。这个题不管是选择数组还是二叉链表都差不多，没有太大差别，但是二叉链表的存储结构便于以后程序的拓展，可以更轻松得增加其他功能，因此最终选择了二叉链表。

三、源代码

stdfax.h

#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


using namespace std;
#endif // !SYDFAX_H_INCLUDE

BinTree.h

#ifndef POSTFIX_H_INCLUDED
#define POSTFIX_H_INCLUDED
#include "stdfax.h"

const int N = 100;
struct BinTreeNode
{
    char data;
    BinTreeNode* leftChild, * rightChild;
};

//前序遍历  
void preOrder(BinTreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    cout << root->data;
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}

//中序遍历  
void inOrder(BinTreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    inOrder(root->leftChild);
    cout << root->data;
    inOrder(root->rightChild);
}

//后序遍历
void postOrder(BinTreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->data;
}

//根据前序遍历和中序遍历创建二叉树
//参数pre为前序序列，参数in为中序序列，n为序列长度
BinTreeNode* CreateBinTree(string pre, string in, int n)
{
    int i = 0;
    int n1 = 0, n2 = 0;
    int m1 = 0, m2 = 0;
    BinTreeNode* node = NULL;            //node为创建的新二叉树
    char leftpre[N], rightpre[N];        //分别为左子树和右子树的前序序列的内容
    char leftin[N], rightin[N];            //分别为左子树和右子树的中序序列的内容
    if (n == 0)                            //序列长度为0时说明没有序列返回空
    {
        return NULL;
    }
    node = new BinTreeNode;
    if (node == NULL)
    {
        return NULL;
    }
    //前序序列的第一个元素一定为根结点
    node->data = pre[0];
    //根据根结点将中序序列分为左子树和右子数
    for (i = 0;i < n;i++)
    {
        if ((i <= n1) && (in[i] != pre[0]))
        {
            leftin[n1++] = in[i];
        }
        else if (in[i] != pre[0])
        {
            rightin[n2++] = in[i];
        }
    }
    //树的前序序列的长度等于中序序列的长度
    //且前序遍历是先左子树再右子树,无论前序还是中序,左子树和右子树的长度都是固定的
    //从i=1开始 前序遍历的第一个是根 
    for (i = 1;i < n;i++)
    {
        if (i < (n1 + 1))    //n1为左子树的长度
        {
            leftpre[m1++] = pre[i];
        }
        else
        {
            rightpre[m2++] = pre[i];
        }
    }
    node->leftChild = CreateBinTree(leftpre, leftin, n1);
    node->rightChild = CreateBinTree(rightpre, rightin, n2);
    return node;
}

//用凹入法输出该二叉树
void Print(BinTreeNode* root, int n)
{
    int i;
    if (root == NULL) return;
    Print(root->rightChild, n + 1);
    for (i = 0; i < n; i++) cout << "   ";
    if (n >= 0)
    {
        cout << root->data << endl;
    }
    Print(root->leftChild, n + 1);
}
#endif // !POSTFIX_H_INCLUDED

main.cpp

#include "stdfax.h"
#include "BinTree.h"

int main()
{
    string preNode;
    string inNode;
    int n = 0;
    BinTreeNode* root = NULL;
    cout << "请输入前序序列:";
    cin >> preNode;
    cout << "请输入中序序列:";
    cin >> inNode;
    n = inNode.length();
    root = CreateBinTree(preNode, inNode, n);
    if (root != NULL) cout << "二叉树构建成功。" << endl;
    //证明构造的正确性，将前序遍历与中序遍历与原序列分别对比，检查是否一致
    cout << "前序序列:";
    preOrder(root);
    cout << endl;
    cout << "中序序列:";
    inOrder(root);
    cout << endl;
    //后序遍历的结果
    cout << "后序序列:";
    postOrder(root);
    cout << endl;
    cout << "该二叉树为：" << endl;
    Print(root, n);
    system("pause");
    return 0;
}