理解二叉树（创建二叉树）【2】

创建二叉树：
一般创建方式：将每个结点的空指针引出一个虚结点，其只为特定值，比如“#”
示例代码：
先序：ABCDEFGH
中序：CBEDFAGH

BtNode* CBTree1() // ABC##DE##F##G#H##
{
	BtNode* s = NULL;
	ElemType elem;
	cin >> elem;
	if (elem != '#')
	{
		s = Buynode();
		s->data = elem;
		s->leftchild = CBTree1();
		s->rightchild = CBTree1();
	}
	return s;
}

利用先序遍历和中序遍历构建二叉树
示例代码：

BtNode* CreatePI(const char* ps, const char* is, int n)
{
	BtNode* s = NULL;
	if (n >= 1)
	{
		s = Buynode();
		s->data = ps[0];
		int pos = FindIs(is, n, ps[0]);
		if (pos == -1) exit(1);
		s->leftchild = CreatePI(ps + 1, is, pos);
		s->rightchild = CreatePI(ps + pos + 1, is + pos + 1, n - pos - 1);
	}
	return s;
}

理解：
s->leftchild = CreatePI(ps + 1, is, pos);
s->rightchild = CreatePI(ps + pos + 1, is + pos + 1, n - pos - 1);

BtNode* CreateBinartTreePI(const char* ps, const char* is, int n)
{
	if (ps == NULL || is == NULL || n <= 0) return NULL;
	else return CreatePI(ps, is, n);
}

利用中序遍历和后序遍历构建二叉树
中序：[CBEDF] A [GH]
后序：[CEFDB] [HG] A

BtNode* CreateIL(const char* is, const char* ls, int n)
{
	BtNode* s = NULL;
	if (n > 0)
	{
		s = Buynode();
		s->data = ls[n - 1];
		int pos = FindIs(is, n, ls[n - 1]);
		if (pos == -1) exit(1);
		s->leftchild = CreateIL(is, ls, pos);
		s->rightchild = CreateIL(is + pos + 1, ls + pos, n - pos - 1);
	}
	return s;
}

理解
s->leftchild = CreateIL(is, ls, pos);
s->rightchild = CreateIL(is + pos + 1, ls + pos, n - pos - 1);

BtNode* CreateBinaryTreeIL(const char* is, const char* ls, int n)
{
	if (is == NULL || ls == NULL || n <= 0) return NULL;
	else return CreateIL(is, ls, n);
}