根据输入字符建树

「爱情、让人受尽委屈。」 2022-08-02 04:49 137阅读 0赞

根据给出的字符串建树  
如a(b(c,d),e(f,g))  
a为根节点，b，e分别为a的左右孩子....

// build_tree.cpp : 定义控制台应用程序的入口点。
    //
    
    /*
    根据给出的字符串建树
    如a(b(c,d),e(f,g))
    a为根节点，b，e分别为a的左右孩子....
    
    
    */
    
    
    #include "stdafx.h"
    #include<stack>
    #include<iostream>
    using namespace std;
    
    
    struct biNode{
    	char value;
    	biNode*lNode;
    	biNode*rNode;
    };
    
    biNode*root = new biNode;
    //startpos为父节点binode后面紧跟的'('在字符串中的位置，endpos为'('对应的')'的位置
    //递归建树
    biNode*create_tree(biNode* binode,char*str,int startpos,int endpos)
    {
    	_ASSERT(endpos - startpos > 3);
    	biNode*lnode = new biNode;
    	biNode*rnode = new biNode;
    	lnode->value = str[startpos + 1];
    	binode->lNode = lnode;
    	if (endpos - startpos == 4)
    	{
    		rnode->value = str[endpos-1];
    		binode->rNode = rnode;
    		return root;
    	}
    	//a(b(c,d),e(f,g))
    	stack<int>aa;
    	int kk = endpos - 1;
    	if (str[endpos - 1] == ')')
    	{
    		aa.push(kk);
    		--kk;
    
    		while (!aa.empty() || (str[kk] - 'a' < 0 || str[kk] - 'z'>25))
    		{
    			if (str[kk] == ')')
    				aa.push(kk);
    			if (str[kk] == '(')
    				aa.pop();
    			--kk;
    		}
    	}
    	rnode->value = str[kk];
    	binode->rNode = rnode;
    	//_ASSERT(str[kk - 1] = ',');
    	if (str[startpos + 2] == '(')
    		create_tree(lnode, str, startpos + 2, kk - 2);
    	if (str[kk + 1] == '(')
    		create_tree(rnode, str, kk + 1, endpos-1);
    
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	char*str = "a(b(c,d),e(f,g))";
    	root->value = str[0];
    	create_tree(root, str, 1, 15);
    
    	system("pause");
    	return 0;
    }