首页 > 代码库 > 如何在网络中传输二叉树(C++源代码实现)

如何在网络中传输二叉树(C++源代码实现)

 

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

 

需求:

实现两个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 ]