1.构建二叉树

#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

struct BTNode{
	char data;//结点值
	BTNode *lchild,*rchild;//左右孩子结点
};

//构造二叉树
BTNode*CreateBTnode(char *str){
	BTNode *r=NULL;//r表示头节点
	BTNode *st[10000];//模拟栈
	BTNode *p;
	int top=-1,k=0,j=0;//top表示头节点，k表示左右孩子
	char ch;
	while(str[j]!='\0'){
		ch=str[j];
		switch (ch){
			case '(':top++;st[top]=p;k=1;break;//k=1转换到左孩子状态		
			case ')':top--;break;//表明以当前栈顶元素为根的子树处理完毕，出栈
			case ',':k=2;break;//k=2转换到右孩子状态
			default:
				p=new BTNode();
				p->lchild=p->rchild=NULL;
				p->data=ch;//新建一个节点
				if(r==NULL)
					r=p;//若r为空表示当前树是空树，该元素作为根节点
				else {
					switch (k){
						case 1:st[top]->lchild=p;break;
						case 2:st[top]->rchild=p;break;
					}
				}
				break;//退出switch
		}
		j++;//继续扫描字符串
	}
	return r;
}

//先序遍历
void DispBTNode1(BTNode *t){
	if(t!=NULL)
	{
		cout<<t->data;
		DispBTNode1(t->lchild);
		DispBTNode1(t->rchild);
	}
}

int main()
{
	char str[]={"A(B(D,F(,E)),C(G(,H),I))"};
	BTNode *bt=CreateBTnode(str);
	DispBTNode1(bt);
	return 0;
}