利用中序和前序遍历确定并生成一颗唯一的树

前言

总所周知，一棵树是可以由其前序遍历与中序遍历或者中序遍历和前序遍历来唯一确定的。因此，我们也就可以利用这个结论，在拥有前序遍历和中序遍历的基础上建立一颗唯一的树。

基本思想

实现这个的基本思想在于找到树的根节点。

当你利用前序遍历的第一个元素，就可以找到这棵树的根节点，而在中序遍历中，根节点的左边则是表示树的左子树，而右边则是表示树的右子树。因此，我们可以利用这点，找到这棵树的左（右）子树的前序与中序的遍历的遍历序列。此时，我们能够将这新的遍历序列看做是一颗新的树，因此，可以利用相同的方法找到子树的根节点。以此类推，便可以找到这棵树的所有的根节点。当这些根节点按照找到的顺序先后连接起来（后找到的根节点自然是子树的根节点），便可以建立一个树了。

代码实现

核心代码

二叉树的数据结构

//二叉树
typedef struct BinaryTree
 {
//<---------------数据域-------------->
    char  data;         //element
    int   index;       //index of node

//<---------------指针域-------------->
    struct BinaryTree* leftChild;  //left child
    struct BinaryTree* rightChild; //right child

}BinaryTree, *pBinaryTree;

利用前序与中序遍历建立二叉树的代码

void createBinaryTree(pBinaryTree &binaryTree, string presequeue, string insequeue) {

    //若二叉树不存在则退出
    if (0 == presequeue.length()) {
        binaryTree = NULL;
        return;
    }

    //根节点，前序遍历的首节点则是根节点
    char rootNode = presequeue[0];
    //从中序遍历中找到该节点的位置
    int index = insequeue.find(rootNode);

    //若寻找不到节点说明输入错误
    if (index<0 && index>insequeue.length()) {
        cout << "输入错误" << endl;
        binaryTree = NULL;
        return;
    }

    //中序遍历中的根节点的左边则是左子树，右边则是右子树
    //因此，可以将这个树分成两个左右孩子的中序遍历的序列
    string leftChildInsequeue = insequeue.substr(0,index);   //左孩子中序排序子序列
    string rightChildInsequeue = insequeue.substr(index + 1);//右孩子中序排序子序列

    //因此可以求出左右子序列的长度
    int leftChildLength = leftChildInsequeue.length();   //左孩子的长度
    int rightChildLength = rightChildInsequeue.length(); //右孩子的长度

    //得知了左右子序列的长度之后，就可以建立左右子序列的前序遍历序列
    string leftChildPresequeue = presequeue.substr(1, leftChildLength); //左孩子前序排序子序列

    string rightChildPresequeue = presequeue.substr(leftChildLength+1); //右孩子前序排序子序列

    //建立树的根节点
    binaryTree = (BinaryTree *)malloc(sizeof(BinaryTree));


    /*由于利用这种方式可以不断的分离出左右孩子的子序列，并且能够找到其根节点.因此，可以利用递归算法，不断的分离这棵二叉树，从而达到一个一个节点的地步由于在分离的途中，不断的寻找二叉树的根节点，因此，利用此方法既可以建立一个唯一确定的二叉树*/

    if (binaryTree != NULL) {

        binaryTree->data = rootNode;//记录信息
        createBinaryTree(binaryTree->leftChild, leftChildPresequeue, leftChildInsequeue);//创建左孩子
        createBinaryTree(binaryTree->rightChild, rightChildPresequeue, rightChildInsequeue);//创建右孩子

    }

}

当然，若是能用迭代的算法自然要比递归的算法要好得多。不过，在这里，笔者也就只贴上了递归的算法，迭代的算法与递归的算法的思想是异曲同工的，有兴趣的读者可以去实现一下哟。

实现结果