根据前序遍历和中序遍历构建二叉树以及根据中序遍历后序遍历构建二叉树

妖狐艹你老母 2022-08-22 01:30 140阅读 0赞

<pre name="code" class="cpp">/************************************************************************/
    /*   
    算法说明：
    由中序遍历序列可知，第一个节点是根节点，
    由前序遍历序列可知，第一个节点是根节点的左子树节点，而且前序遍历中，根节点左边是左子树，右边是右子树，因此通过中序遍历的根节点可以确定的是：
    根节点在前序遍历中的位置（通过遍历前序遍历序列，比较每一个节点与中序遍历中的第一个节点即根节点可知）；
    左子树的节点数，因为一旦找到前序遍历中根节点的位置，就找到左右子树的分界点，也就是说，前序遍历中根节点左边的都是左子树节点，可以通过遍历知道左子树的节点数；
    同样，右子树的节点数也可以确定。
    通过以上确定的信息，可以划分出前序遍历中的左右子树节点数，根节点位置；
    因此，下面就是进行求根节点左节点和右节点，而根据上述划分，可以知道左子树前序和中序序列起始位置以及长度、右子树前序和中序序列起始位置以及长度，
    这样可以递归按照上述方式同样获得左右子树的根节点。
    
    通过递归可以求得整个树的结构。
    */
    /************************************************************************/
    
    
    struct Node
    {
    	char data;//数据
    	Node *left;//左孩子
    	Node *right;//右孩子
    };  
    
    
    // 由前序和中序遍历序列进行建树， 返回根结点的指针
    Node * PreInCreateTree(int *mid,int *pre,int len)	//n标识s2的长度
    { 
    	if(len==0)
    		return NULL;
    
    	int i = 0;
    	while(*mid != pre[i])
    		++i;
    
    	Node *h=new Node;
    	h->data= *mid;
    	h->left  = PreInCreateTree(mid+1, pre, i);
    	h->right = PreInCreateTree(mid+i+1, pre+i+1, len-i-1);
    	return h;
    }
    
    
    
    // 由中序和后序遍历序列进行建树， 返回根结点指针
    Node * InPostCreateTree(int *mid,int *post,int len)
    {
    	if(len == 0)
    		return NULL;
    	int i=len-1;
    	while(post[len-1] != mid[i])
    		--i;
    	Node *h=new Node;
    	h->data=post[len-1];
    	h->left=InPostCreateTree(mid,post,i);
    	h->right=InPostCreateTree(mid+i+1,post+i,len-i-1);
    	return h;
    }
    
    /************************************************************************/
    /* 
    中序遍历中，根节点总是位于左右子树中间，将左右子树分开。
    后序遍历中，根节点总是在左右子树之后。
    
    重建算法：
    现在说一下重建根节点的过程，其他节点可以递归建立。
    由后序遍历定义可知，后序遍历序列的最后一个元素必定是整个树的根节点，这样就确定了根节点。
    由中序遍历定义可知，在中序遍历中查找根节点，可以确定根节点在中序遍历序列中位置，这样就可以将中序遍历序列分为左右子树，
    一旦确定左右子树，左右子树的长度也就确定了，根据左右子树的长度，在后序遍历序列中，可以确定左右子树的根节点，这样递归下去既可以确定整个树。
    */
    /************************************************************************/