#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<stack> #include<queue> using namespace std; typedef int ElemType; typedef struct BinaryTreeNode { ElemType data; BinaryTreeNode *left, *right; }BinaryTreeNode; //二叉树的创建3 根据先序序列和中序序列创建一个二叉树 先序：DBACEGF 中序：ABCDEFG 令pre[]="DBACEGF" in[]="ABCDEFG" BinaryTreeNode * CreateBinaryTree(ElemType * pre, ElemType *in, int length)//此种创建二叉树的方法本质上是先创建根结点 再创建左子树，再创建右子树 { if (length <= 0 || pre == NULL || in == NULL)////递归出口:长度为0时表示建树完毕 { return NULL; } ElemType rootValue = pre[0]; BinaryTreeNode * root = new BinaryTreeNode();//创建根节点 root->data = rootValue; root->left = root->right = NULL; int leftLength, rightLength, i = 0;//左子树的长度，右子树的长度 ,下面的代码就是找到左右子树的元素，创建左右子树 while (i<length&&in[i] != rootValue) { i++; } leftLength = i; rightLength = length - leftLength - 1;//注意对个一个遍历的序列必定知足rightLength+leftLength+1=length;左子树长度加上右子树长度加一个根结点的长度等于树全部结点的长度。 if (leftLength>0)//创建左子树 { root->left = CreateBinaryTree(pre + 1, in, leftLength);////此处的关键在于寻找右子树后序序列的起始地址，和右子树的中序序列的起始地址 } if (rightLength>0)//创建右子树 { root->right = CreateBinaryTree(pre + length - rightLength, in + length - rightLength, rightLength);////此处的关键在于寻找右子树后序序列的起始地址，和右子树的中序序列的起始地址 // 上一句等价于root->right =CreateBinaryTree(pre+1+leftLength,in+1+leftLength,rightLength); } return root; }