C语言——二叉树的创建（二叉链表）_#include #include #include

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\n", str);
	Mov1(str);
	printf("%s\n", str);
	Mov2(&str);
	printf("%s\n", str);
	Mov3(str);
	printf("%s\n", str);
	return 0;
}
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

程序的输出结果如下：

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

2. 创建二叉树

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

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

下面是一个错误代码

#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("\n");
	InOrder(root);
	printf("\n");
	PastOrder(root);
	printf("\n");
	return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

程序输出结果如下：

结果显示所构造的二叉树如下

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

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

将
BtNode* CreateBtNode(const char* str)
改成
BtNode* CreateBtNode(const char*& str)
1
2
3
4

修改后的代码调试过程如下

代码的最终运行结果如下