1. 引用

递归构造二叉树的过程中用到了 C++ 语言中的引用 &，引用 & 是变量别名的意思，除了变量名不一样，其他的都是指同一个东西。传参的方式有两种：一种是传值；一种是传址。引用 & 的使用使得传址操作起来更加方便。举例如下

#include <stdio.h>
#include <string.h>

void Mov1(const char* str) {
          
   	//传递字符串指针的值
	str++;
}

void Mov2(const char** str) {
          
   	//传递字符串指针的地址
	(*str)++;
}

void Mov3(const char*& str) {
          
   	//传递字符串指针的引用
	str++;
}

int main() {
          
   
	const char* str = "abcde";
	printf("%s
", str);
	Mov1(str);
	printf("%s
", str);
	Mov2(&str);
	printf("%s
", str);
	Mov3(str);
	printf("%s
", str);
	return 0;
}

程序的输出结果如下：

从结果可以看出，对于字符串指针，当传递该指针的值进行++时，调用函数内部对该指针的修改并不会影响到主函数中的值，这正是传值方式的特点。要想将调用函数对字符串指针的修改带回到主函数里，就需要用到二级指针，也就是传递字符串指针的地址。从上面的结果也可以看出 Mov2 函数，接收了指针的地址，所以在 Mov2 函数内部对指针的修改会被带出来。引用使得这种操作更加方便，Mov3 函数接收了一个 const char *& 类型的参数，该参数正是一个指向字符串常量的指针的引用。将 Mov2 和 Mov3 函数实现进行对比，Mov3 的内部实现确实更加容易理解，代码也更加简洁，二者实现了相同的功能，这正是 C++ 中引入引用概念的目的之一。

2. 创建二叉树

const char *str = "ABC##DE##F##G#H##"

二叉树用一个字符串常量表示，其中 # 表示空树，则上面代表的二叉树如下 下面是一个错误代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//二叉链表的实现
typedef char ElemType;

typedef struct BtNode {
          
   	//二叉树节点类型
	ElemType data;
	struct BtNode* leftchild;
	struct BtNode* rightchild;
}BtNode, *BinaryTree;

BtNode* Buynode() {
          
   	//为新节点申请空间
	BtNode* s = (BtNode*)malloc(sizeof(BtNode));
	if (nullptr == s) exit(1);
	memset(s, 0, sizeof(BtNode));
	return s;
}

void PreOrder(BtNode* ptr) {
          
   	//先序遍历
	if (nullptr != ptr) {
          
   
		printf("%c ", ptr->data);
		PreOrder(ptr->leftchild);
		PreOrder(ptr->rightchild);
	}
}

void InOrder(BtNode* ptr) {
          
   		//中序遍历
	if (nullptr != ptr) {
          
   
		InOrder(ptr->leftchild);
		printf("%c ", ptr->data);
		InOrder(ptr->rightchild);
	}
}

void PastOrder(BtNode* ptr) {
          
   	//后序遍历
	if (nullptr != ptr) {
          
   
		PastOrder(ptr->leftchild);
		PastOrder(ptr->rightchild);
		printf("%c ", ptr->data);
	}
}

BtNode* CreateBtNode(const char* str) {
          
   	//创建节点
	BtNode* s = nullptr;
	if (*str != #) {
          
   
		s = Buynode();
		s->data = *str;
		s->leftchild = CreateBtNode(++str);
		s->rightchild = CreateBtNode(++str);
	}
	return s;
}

BtNode* CreateTreeStr(const char* str) {
          
   	//创建树
	if (nullptr == str || strlen(str) <= 0) return nullptr;
	else return CreateBtNode(str);
}

//测试
int main() {
          
   
	const char* str = "ABC##DE##F##G#H##";
	BinaryTree root = CreateTreeStr(str);
	PreOrder(root);
	printf("
");
	InOrder(root);
	printf("
");
	PastOrder(root);
	printf("
");
	return 0;
}

程序输出结果如下：

结果显示所构造的二叉树如下 原因就在于 CreatBtNode 函数接收的是一个字符串常量指针的值，在递归调用过程中，调用函数内部对指针的修改未能带出来，调试过程如下

需要修改的地方就是将 CreatBtNode 函数的参数改成指针的引用

将
BtNode* CreateBtNode(const char* str)
改成
BtNode* CreateBtNode(const char*& str)

修改后的代码调试过程如下 代码的最终运行结果如下