前序遍历和中序遍历重建二叉树-创新互联

对于二叉树，在此我不做过多讲解，如有不懂，请参照一下链接点击打开链接

 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;    
    }

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。