一：构造链式二叉树(—)_1.构建如下图二叉树,2.要求使用括号表示法输入二叉树并转化为二叉树的链式存储结

1：由二叉树的括号表示法构造链式二叉树

//由二叉树的括号表示， 创建二叉树，并返回根节点的指针 
void CreateBTree(  BTNode *&root, char str[])//参数：传入根节点的指针，二叉树的括号表示 
{
	//flag标记其后处理的节点; 若是父节点（此刻为栈顶元素)的左儿子（flag=1）， 若是是右儿子（flag=2）
	int j=0, flag=0, top=-1; 
	BTNode *p=NULL; 
	while( str[j]!='\0')
	{
		switch( str[j] )
		{
		case '(':flag=1; top++; stack[top]=p; break;//若遇到左括号,则把前面刚刚创建的那个节点入栈， flag=1 
		case ',':flag=2; break;//若遇到逗号，说明其后创建的节点为右孩子节点， flag=2
		case ')':top--; break;//若遇到右括号，说明栈顶结点的左右孩子处理完毕， 栈顶结点出栈
			
		default://遇到元素
			p=new Node;//创建新节点
			p->data=str[j]; p->left=p->right=NULL;//为新建节点赋值：且此时栈顶结点是p的父节点 
			
			if( root==NULL ) //如果根节点为空
			{
				root=p;
			}
			else 
			{
				switch( flag )
				{
				case 1:stack[top]->left=p;break;//flag=1说明p为栈顶元素左儿子
				case 2:stack[top]->right=p;break;//p为栈顶元素右儿子
				}
			}	 
		}
		
		j++;
	}
}

函数返回二叉树的根节点；

BTNode *CreateBTree(char str[], int i)//参数：二叉树的顺序存储，该处理的节点标号 ; 
{
	BTNode *b;
	if(i> MAXsize)//MAXsize表示二叉树顺序存储时，数组的最大下标
		return NULL;
	if( str[i]=='#' ) return NULL;//当节点不存在时， 返回NULL
 
	b=new BTNode;//创建节点
	b->left=CreateBTree(str, 2*i);//递归创建左子树
	b->right=CreateBTree(str, 2*i+1);//递归创建右子树
 
	return b;//返回根节点
}