128-根据给定的字符串,建立二叉树

一、根据给定字符串str = "ABC##DE##F##G#H##"建立对应的二叉树（其中‘#’代表空）

1、树的节点结构为

typedef char ElementType;
typedef struct BTNode
{
	BTNode* LeftNode;//左孩子结点
	BTNode* RightNode;//右孩子结点
	ElementType data;//数据域
}BTNode;
1
2
3
4
5
6
7

2、二叉树的建立

BTNode* BuyNode()//申请一个BTNode*结点
{
	BTNode* s = (BTNode*)calloc(1,sizeof(BTNode));
	if (s == nullptr)//判断指针是否为空
	{
		exit(1);//为真直接退出
	}
	return s;//不为空返回s
}
BTNode* CreateBTree(const char*& str)//注意是以引用传入
{
	//之前的函数已经判断过str是否为空,所以这边str一定不为空
	BTNode* s = nullptr;
	if (*str != '#')//解引用判断字符是否为'#'
	{
		s = BuyNode();//如果字符!='#'就新申请一个节点
		s->data = *str;//将字符赋值给结点的数据域
		s->LeftNode=CreateBTree(++str);//递归调用,创建右左孩子结点
		s->RightNode=CreateBTree(++str);//递归调用,创建右孩子结点
	}
	return s;//返回根节点
}

BTNode* BuildBTree(const char* & str)//传入字符串str
{
	//判断str是否为空,如果为空直接返回nullptr
	if (str == nullptr || strlen(str) <= 0)return nullptr;
	//不为空说明有数据,调用上面的CreateBTree函数,最后返回一个根节点
	else return CreateBTree(str);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30