189 8069 5689
对于二叉树，在此我不做过多讲解，如有不懂，请参照一下链接点击打开链接
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、虚拟空间、营销软件、网站建设、临湘网站维护、网站推广。
1、在此二叉树的定义：
struct BinaryTreeNode
{
BinaryTreeNode *_Left;
BinaryTreeNode *_Right;
T _data;
public:
BinaryTreeNode(const T& x)
:_Left(NULL)
, _Right(NULL)
, _data(x)
{}
};
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
BinaryTree()
:_root(NULL)
{}
} 2、由前序遍历和中序遍历重建二叉树
思想：
1、二叉树前序遍历中，第一个元素总是根节点的值，
2、中序遍历，左子树的结点的值位于根节点值得左边，
3、右子树的节点的值位于根节点值得右边。
4、如果前序遍历为空或中序遍历为空或结点个数小于等于0，返回NULL；
5、创建根节点，前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点位置
6、分别得知左子树和右子树的前序和中序遍 历序列，重建左右子树。
递归形式实现：
Node * RebuildBinaryTree(T* PrevOrder, T* InOrder, int num)
{
if (PrevOrder == NULL || InOrder == NULL || num <= 0)
{
return NULL;
}
Node* root = new Node(PrevOrder[0]);
// 前序遍历的第一个数据就是根节点数据
//中序遍历，根节点左为左子树，右为右子树
int rootposition = -1;
for (int i = 0; i < num; i++)
{
if (InOrder[i] == root->_data)
{
rootposition = i;
}
}
if (rootposition == -1)
return NULL;
//重建左子树(根节点)递归
int LeftNum = rootposition;
int *PrevOrderLeft = PrevOrder + 1; //前序第二个即为根节点的左子树
int *InOrderLeft = InOrder; //中序第一个 即为其左子树。
root->_Left = RebuildBinaryTree(PrevOrderLeft, InOrderLeft, LeftNum);
//重建右子树(根节点)递归
int RightNum = num - LeftNum - 1;
int *PrevOrderRight = PrevOrder + 1 + LeftNum;
int *InOrderRight = InOrder + LeftNum + 1;
root->_Right = RebuildBinaryTree(PrevOrderRight, InOrderRight, RightNum);
return root;
}