【算法导论】 二叉树的重构

    二叉树的重构是指通过二叉树的遍历结果得到二叉树的构造。

    重构方案：    前序遍历(  PreOrder) + 中序遍历(InOrder)
                         后序遍历(PostOrder) + 中序遍历(InOrder)
                         前序遍历(  PreOrder) + 后续遍历(PostOrder)（只对真二叉树成立）

前序遍历+后序遍历：

    对于一颗二叉树,  其前序遍历可表示为： Root + LeftTree + RightTree
                                  中序遍历可表示为： LeftTree + Root + RightTree

    前序遍历的第一个结果为根节点，通过查找可确定中序遍历中根节点的位置，则可确定左子树和右子树中序遍历下的结果。确定左子树和右子树节点数量，则可确定左子树和右子树前序遍历下的结果。得到左右子树中序和前序遍历结果，则可递归的构造出二叉树。

（下面程序以此作为实例对二叉树进行重构）

#include<stdio.h>

/** BinaryTree DS */
typedef struct BinaryTree
{
	int key;
	BinaryTree *lson;
	BinaryTree *rson;
}BinaryTree;

/** find a key in array A */
int Array_Find( int *A, int begin, int end, int key)
{
	for( int i=begin; i<end; i++) {
		if( key == A[i]) return i;
	}
	
	return -1;
}

/** 重构二叉树, 参数: PreOrder[pbegin ... pend]
  *                     InOrder[ibegin ... iend]
  */
BinaryTree *GetBinaryTree( int *PreOrder, int pbegin, int pend, 
                           int  *InOrder, int ibegin, int iend)
{
	if( pbegin>=pend || ibegin>=iend) return NULL;   // 出口, 无节点情况
	
	BinaryTree *Root = new BinaryTree;         // 分配在堆上, 函数结束时不会消失
	*Root = { PreOrder[pbegin], NULL, NULL};   // 构造根节点
	
	int r = Array_Find( InOrder, ibegin, iend, PreOrder[pbegin]);  // root's position in InOrder
	
	// 确定左子树、右子树 前序、中序遍历结果, 递归求解 */
	Root->lson = GetBinaryTree( PreOrder, pbegin+1, (r-ibegin)+pbegin+1, InOrder, ibegin, r);
	Root->rson = GetBinaryTree( PreOrder, (r-ibegin)+pbegin+1, pend, InOrder, r+1, iend);
	
	return Root;
}

/** 中序遍历 */
void Tree_Print( BinaryTree *Root)    
{
    if( Root==NULL) return;    
  
    printf( "key:   %d\n", Root->key);      //visit tree
    if( Root->lson !=NULL) printf( "lson:  %d\n", Root->lson->key);
    if( Root->rson !=NULL) printf( "rson:  %d\n", Root->rson->key);
	printf( "\n\n");
	
    Tree_Print( Root->lson);    
    Tree_Print( Root->rson);    
}

int main()
{
	int PreOrder[] = { 43, 12, 8, 32, 16, 35, 78, 56, 88, 83, 121, 97};
	int  InOrder[] = { 8, 12, 16, 32, 35, 43, 56, 78, 83, 88, 97, 121};
	
	BinaryTree *Root = GetBinaryTree( PreOrder, 0, 12, InOrder, 0, 12);
	Tree_Print( Root);
	
	return 0;
}

前序遍历+后序遍历：

    真二叉树( Proper Binary Tree) : 所有节点出度为0或2的二叉树，即左子树右子树皆空或皆非空的二叉树。

    真二叉树定义来自邓俊辉教授的慕课，国外称为 满二叉树（Full Binary Tree），注意和国内教材中的满二叉树区别。

    因为当某节点只有一颗子树时，前序遍历结果为 Root + SonTree，后序遍历结果为 SonTree + Root。通过前序遍历和后序遍历无法确定SonTree为左子树和右子树，因此不能还原这种二叉树的结构。

    对于真二叉树来说，前序遍历可表示为： Root + LeftTreeRoot + LeftTree +  RightTreeRoot + RightTree 

                                  后续遍历可表示为：  LeftTree + LeftTreeRoot +  RightTree + RightTreeRoot + Root

    可通过前序遍历确定左子树根节点，通过后序遍历确定右子树根节点，从而确定左右子树前序、后续遍历结果，递归求得二叉树结构。

根据前序、后序判断是否为真二叉树：

    若节点左子树为空，前序遍历前两个节点为 根节点 + 左子树根节点；后序遍历后两个节点为 根节点 + 左子树根节点；两者结果相同，右子树同上。若节点左右子树全为空 或 全不为空，都不会出现节点逆序相同情况。则可通过递归依次判断节点是否为真二叉树。

    下面code忽略了判断是否为真二叉树，当节点只有一颗子树时，都当做左子树进行处理。

/** 重构二叉树, 参数:  PreOrder[pbegin ... pend] 
  *                    PostOrder[tbegin ... tend] 
  */  
BinaryTree *GetBinaryTree( int  *PreOrder, int pbegin, int pend,  
                           int *PostOrder, int tbegin, int tend)  
{  
    if( pbegin>=pend || tbegin>=tend) return NULL;   // 出口, 无节点情况  
      
    BinaryTree *Root = new BinaryTree;         // 分配在堆上, 函数结束时不会消失  
    *Root = { PreOrder[pbegin], NULL, NULL};   // 构造根节点  
      
    if( pbegin+1==pend) return Root;   // 不存在左右子树情况  
    int lr = Array_Find( PostOrder, tbegin, tend, PreOrder[pbegin+1]); // leftsonRoot position in PostOrder
      
    // 确定左子树、右子树 前序、中序遍历结果, 递归求解 */  
    Root->lson = GetBinaryTree( PreOrder, pbegin+1, (lr+1-tbegin)+pbegin+1, PostOrder, tbegin, lr+1);  
    Root->rson = GetBinaryTree( PreOrder, (lr+1-tbegin)+pbegin+1, pend, PostOrder, lr+1, tend-1);  
      
    return Root;  
}
  
/** 中序遍历 */  
void Tree_Print( BinaryTree *Root)      
{  
    if( Root==NULL) return;      
    
    printf( "key:   %d\n", Root->key);      //visit tree  
    if( Root->lson !=NULL) printf( "lson:  %d\n", Root->lson->key);  
    if( Root->rson !=NULL) printf( "rson:  %d\n", Root->rson->key);  
    printf( "\n\n");  
      
    Tree_Print( Root->lson);      
    Tree_Print( Root->rson);      
}