前些日子有朋友遇到这个问题来问我,我觉得有点意思,便实现了代码,写篇文章做个总结,与网友分享。
需求:
实现两个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 ]