前些日子有朋友遇到这个问题来问我，我觉得有点意思，便实现了代码，写篇文章做个总结，与网友分享。

需求：

实现两个API，在客户端：传入一个二叉树的根结点指针，输出可以在网络中传输的ASCII串。在服务器端：根据传入的ASCII串来解析生成一个二叉树，返回二叉树的根结点指针。

思路：

看到这个问题，首先想到的是二叉树补全法，将这课二叉树补全，变成一颗完全二叉树，再使用数组进行存储，写入文件中。这样做需要在节点中增加一个属性，标记是否为补全的节点。这种方法不太合理，因为使用了补全操作，对于一颗很不规则的二叉树，将会占用非常大的存储空间，并且修改了二叉树的属性。

我们从而二叉树的表示下手，如何表示一颗二叉树？除了把各结点用指针连起来，直接表示出二叉树的结构，还有其他的方式能表示出二叉树的方式么？

回顾二叉树的定义，二叉树是一个嵌套结构，我们可以用集合来表示嵌套结构。

例如：

可用三元组来表示：[a b c] 我们用先序遍历的方式来表示。

我们规定保证[]之内至少有三个元素，即空缺的孩子结点用特殊符号表示。

例如：[a b $] 表示一颗根结点元素为a，左孩子结点元素为b,无右孩子结点的二叉树。

单个结点的二叉树，直接用空格与其他二叉树隔开即可，不用[]来包含

例如:

 [ a b [ c [ d f g ] [ e h i ] ] ]

这样，只要把二叉树转换成如此规则的字符串，就可以很方便的在网络中传输了。

在服务器端再把获得的格式字符串解析成二叉树即可。

一个二叉树森林：

例如：

A  [A [ B C [ D E $ ] ] $ ]  [ A $ B ]

树与树之间用空格隔开。 单结点的树不用括号。

思路很简单，但实现起来不是那么容易的。下面我们就来编码实现。

第一部分：

从二叉树森林转换成格式字符串

为了写一个更加通用的函数，我们实现二叉树森林到字符串的转化。

函数接口为：

int  BinaryTreesToFormateString(const vector<TreeNode*>&binaryTreesVec, string& formateStrRet)

参数binaryTreesVec为二叉树森林中各树的根结点指针。

参数formateStrRet为返回的格式字符串。

我们对二叉树进行先序遍历即可，由于二叉树的深度可能很大，用递归遍历效率较低，故我们用迭代的方式进行先序遍历。

先序遍历的过程：

1、 从根结点开始，沿着左链接方向遍历，直至遇到左链接为空的结点（把沿途遇到的父结点地址压入栈中）。

2、 改变遍历方向，重复1过程，直到遇到左右链接都为空的叶结点。

3、 弹栈，取出弹出栈的父结点的右链接，从1过程开始重复。

但是我们如何在先序遍历中把二叉树的边界括号[ ]添加进去呢？

我们观察发现，每个父结点之前都加括号[，因为是先序遍历，父结点是这颗子树第一个被访问到的。但什么时候加右括号]呢？

在访问到右叶结点时。但访问到右结点加的这个右括号，只是其与其父结点组成的最小的二叉树的右边界，还有其上层二叉树的右边界，上上层二叉树的右边界……

所谓“打包操作”，就是把初步生成的格式字符串，加上右括号]，比如，刚才我们初步生成了 [A [ B C [ D E $  打包操作后变为：[ A [ B C [ D E $ ] ]

（从后往前扫，发现有三个元素，且之前是左括号[，故正好这三个元素可以组成一个子二叉树，在其后添加右括号]。 加完右括号之后，我们再检查是否还有应该添加的右括号。

我们把配对的子二叉树看作是一个结点，即把[ D E $ ]看作是一个结点，这样B C [ D E $ ] 为三个元素，可以组成一个子树，在其后添加右括号，[ B C [ D E $ ] ]。 再把这样一颗子树看作一个结点，其前(包括它自己)共有2个结点，无法组成一颗二叉树，故无需再添加右括号了。 打包操作结束。）

不知道我有没有说清楚整个过程，还是不太明白的朋友，可在下面留言。^_^

若遍历指针遍历到某结点的右链接为NULL，那么就开始打包操作。（因为可以确定起码一颗小子树遍历完毕。）

【源代码】

//把二叉树森林转换为格式字符串 ( 注意我们的格式是前序遍历。 )
int  BinaryTreesToFormateString(const vector<TreeNode*>& binaryTreesVec, string& formateStrRet)
{
	TreeNode* workPtr = NULL ;
	stack<TreeNode*> nodeNodeStack ;
	int nullLinkType = 0 ; //空链接类型，0表示workPtr=NULL造成的空链接，1表示是左空链接，2表示是右空链接

	//二叉子树格式串容器（保存各步骤逐渐生成的二叉树，最后会整合成一棵整二叉树）
	vector<string> biSubTreeStrVec ; //因为要打包操作，所以不能直接把值放到formateStrRet中

	for (vector<TreeNode*>::const_iterator i = binaryTreesVec.begin(); 
         i != binaryTreesVec.end(); ++i)
    {
		workPtr = *i ;
		nullLinkType = 0 ;

		//workPtr是单结点的二叉树
		if (workPtr->lchild == NULL && workPtr->rchild == NULL)
		{
			formateStrRet += workPtr->value ;
			formateStrRet += " " ;
			continue ;
		}

		while(workPtr != NULL || !nodeNodeStack.empty())
		{
			if(workPtr != NULL)
			{
				//workPtr是左孩子叶结点(在左链接上的叶结点)
				if (nullLinkType == 1 && workPtr->lchild == NULL && workPtr->rchild == NULL)
				{
					//把结点值打印到vector<string>中
					biSubTreeStrVec.push_back(workPtr->value) ;
					workPtr = NULL ;
					nullLinkType = 0 ;
				}
				//workPtr是右孩子叶结点(在右链接上的叶结点)
				else if (nullLinkType == 2 && workPtr->lchild == NULL && workPtr->rchild == NULL)
				{
					biSubTreeStrVec.push_back(workPtr->value) ;
					Pack(biSubTreeStrVec) ; //打包操作
					workPtr = NULL ;
					nullLinkType = 0 ;
				}
				//其它情况--即workPtr为父结点
				else 
				{
					biSubTreeStrVec.push_back("[") ;
					biSubTreeStrVec.push_back(workPtr->value) ;
					nodeNodeStack.push(workPtr) ;

					workPtr = workPtr->lchild ;
					nullLinkType = 1 ; //标记workPtr指向的为左链接
				}					
			}
			else //workPtr == NULL
			{
				//workPtr是左空链接
				if (nullLinkType == 1)
				{
					biSubTreeStrVec.push_back(NULLNODEVAL) ;////打印空标记
				}
				//workPtr是右空链接
				else if (nullLinkType == 2)
				{
					biSubTreeStrVec.push_back(NULLNODEVAL) ;
					Pack(biSubTreeStrVec) ; //打包操作
				}

				workPtr = nodeNodeStack.top() ;
				nodeNodeStack.pop() ;//弹出栈顶元素 
				workPtr = workPtr->rchild ; //改变处理结点的方向 
				nullLinkType = 2 ; //标记workPtr指向的为右链接
			}
		}//while

		//把本次生成的二叉树字符串打印到结果中
		for (vector<string>::const_iterator j = biSubTreeStrVec.begin(); 
             j != biSubTreeStrVec.end(); ++j)
		{
			formateStrRet += *j ;
			formateStrRet += " " ;
		}

		biSubTreeStrVec.clear() ;
	}//for

	return 0 ;
}

//打包操作--把biSubTreeStrVec中存的结点打包成一棵子二叉树就尽量打包成一棵子树
int Pack(vector<string>& biSubTreeStrVec)
{
	do
	{
		int cnt = 0 ;
		string subBiTreeFormateStr ;

		for (vector<string>::const_iterator iVec = biSubTreeStrVec.end()-1;
		     *iVec != "[" ; iVec--)
		{
			cnt++ ;
		}
		if (cnt != 3)
			break ;

		for ( ; iVec != biSubTreeStrVec.end(); iVec++)
		{
			subBiTreeFormateStr += *iVec ;
			subBiTreeFormateStr += " " ;
		}
		subBiTreeFormateStr += "] " ;

		for (int i = 0 ; i < 4; i++)
		{
			biSubTreeStrVec.pop_back() ;
		}
		biSubTreeStrVec.push_back(subBiTreeFormateStr) ;
		if (biSubTreeStrVec.size() == 1)
			break ;

	} while (1) ;

	return 0 ;
}

第二部分：

解析格式字符串，生成二叉树森林。

函数接口为：

int  FormateStringToBinaryTrees(constvector<string>& wordsVec, vector<TreeNode*>& treesVecRet)

参数wordsVec：把格式字符串分割成一个个单词的集合。

参数treesVecRet：为返回的二叉树森林的根结点集合。

解析字符串的过程：

我们设置两个栈，一个存括号，称为markStack。一个存二叉树的结点地址，称为nodePtrStack。

若当前扫描到的字符为左括号[，则把左括号[压入markStack中。

若当前扫描到的字符为数据，则构造一个结点，把结点地址压入nodePtrStack中。

若当前扫描到的字符为右括号]，则表示一颗子树的终结，故弹nodePtrStac栈来构造这颗子树。把nodePtrStac栈弹三次，构造成一颗子树。然后把新构造的子树根结点压栈。（把这个子树看作是一颗大子树的一个结点） 然后再弹markStack栈把这颗子树的左括号[弹出。

若nodePtrStack为空时，则一颗完整的二叉树生成完毕。

【源代码】

//把格式字符串转换成二叉树森林
//此程序只能检测到一般的格式错误，对于其他的一些错误格式不能识别，健壮性较差,以后若用到此代码，需完善。
int FormateStringToBinaryTrees(const vector<string>& wordsVec, vector<TreeNode*>& treesVecRet)
{
    stack<string> markStack ;
    stack<TreeNode*> nodePtrStack ;

    string markStackPopTmp ;    //标记栈弹栈操作的废弃值

    TreeNode* rootNodePtr = NULL ;   //根结点指针
    TreeNode* newNodePtr = NULL ;    //新生成结点指针

    TreeNode* lchildPtr = NULL ;     //左孩子指针
    TreeNode* fatherPtr = NULL ;     //父指针
    TreeNode* rchildPtr = NULL ;     //右孩子指针

    //我们遵循的原则是先压markStack栈，再压nodePtrStack，若发现不同步，则填充空值。
    for (vector<string>::const_iterator i = wordsVec.begin(); 
         i != wordsVec.end(); ++i)
    {
        if (*i == "[")
        {
            markStack.push(*i) ;
        }

        else if (*i == "]") //遇到"]"表示一颗子树的终结，故弹栈来构造这颗子树
        {
            //构造子树，并把构造好的子树根结点压栈
            if (nodePtrStack.size() >= 3)
            {
                rchildPtr = nodePtrStack.top() ;
                nodePtrStack.pop() ;
                lchildPtr = nodePtrStack.top() ;
                nodePtrStack.pop() ;
                fatherPtr = nodePtrStack.top() ;
                nodePtrStack.pop() ;
            }
            else
            {   //报告出错
                cout << " # " << fatherPtr->value << " # " ;
                cout << "[] Formate Error!\n" << endl ;
                return -1 ;
            }

            fatherPtr->lchild = lchildPtr ;
            fatherPtr->rchild = rchildPtr ; 
            if (markStack.top() == "[")
            {
                markStack.pop() ;
                if (!nodePtrStack.empty())
                {
                    nodePtrStack.push(fatherPtr) ;  //把新构造的子树根结点压栈
                }
                else //若结点指针栈为空，则表示此颗二叉树生成完毕，把根结点fatherPtr存储在treesVecRet
                {
                    treesVecRet.push_back(fatherPtr) ;
                }
            }
            else 
            {    //报错("["与"]"不配对)
                cout << " # " << fatherPtr->value << " # " ;
                cout << "[] Pair Error!\n" << endl ;
                return -1 ;
            }

            //弹栈到最后发现，符号栈markStack为空，但结点栈中还有值，格式错误
            if (markStack.empty() && !nodePtrStack.empty())
            {
                cout << " # " << fatherPtr->value << " # " ;
                cout << "[] Formate Error!\n" << endl ;
                return -1 ;
            }
        }//if(*i == "]")

        else //当前值为结点中的键值
        {
            //构造新结点，并把其结点指针压栈
            if (*i == NULLNODEVAL) //若是空标记，则此为空结点NULL
                newNodePtr = NULL ;
            else
                newNodePtr = new TreeNode(*i) ;
            nodePtrStack.push(newNodePtr) ;

            if (markStack.empty()) //若向结点指针栈压栈时，mark栈为空，说明此为单节点树。
            {
                treesVecRet.push_back(nodePtrStack.top()) ;
                nodePtrStack.pop() ;
            }
        }

    }//for

    //若到最后两个栈中还有不为空的，则说明输入格式有误
    if (!markStack.empty() || !nodePtrStack.empty())
    {
        cout << "Formate Error!\n" << endl ;
        return -1 ;
    }

    return 0 ;
}

第三部分：测试

int main(void)
{
    ifstream dataFile(".\\test.txt") ;
    if (!dataFile)
    {
        cout << "Can't open the data file!" << "\n";
        exit(0) ;
    }
    
    //分割字符串
    vector<string> wordsVec ;
    ExtractWordsFromFile(dataFile, wordsVec) ;

    //生成二叉树森林
    vector<TreeNode*> binaryTreesVec;
    FormateStringToBinaryTrees(wordsVec, binaryTreesVec) ;

    cout << "格式字符串生成的二叉树森林:" << endl ;
    //检测结果--打印出此二叉树森林
    for (vector<TreeNode*>::const_iterator i = binaryTreesVec.begin(); 
         i != binaryTreesVec.end(); ++i)
    {
	cout << "先序遍历：" ;
        PreOrderTraverse(*i) ;
        cout << endl ;
		
	cout << "中序遍历：" ;
        InOrderTraverse(*i) ;
        cout << endl ;
	cout << "--------" << endl ;
    }

    //由二叉树森林生成格式字符串
    string biTreeForestStr ;
    BinaryTreesToFormateString(binaryTreesVec, biTreeForestStr) ;

    cout << "二叉树森林生成的格式字符串:" << endl ;
    cout << biTreeForestStr << endl ;

    return 0 ;
}


//从文件中提取字符串
int ExtractWordsFromFile(ifstream& inputFile, vector<string>& wordsVecRet)
{
    string aLineString ;
    string wordTmp ;
    while(getline(inputFile, aLineString)) 
    {
        stringstream strin(aLineString);

        while (strin >> wordTmp)
        {
            wordsVecRet.push_back(wordTmp) ;
        }
    }

    return 0 ;
}

//中序遍历整个二叉树
void InOrderTraverse(TreeNode* T)
{
    if(T != NULL)
    {
        InOrderTraverse(T->lchild) ;
        cout << T->value << "   ";
        InOrderTraverse(T->rchild) ;
    } 
}

//前序遍历整个二叉树
void PreOrderTraverse(TreeNode* T)
{
    if(T == NULL)//树为空 
    {
        return ;
    }
    else
    {
        cout << T->value << "   ";
        PreOrderTraverse(T->lchild) ;
        PreOrderTraverse(T->rchild) ;
    } 
}

test.txt中数据为：

A  [A [ B C [ D E $ ] ] $ ]  [ A $ B ]