二叉树的创建（数据结构） C语言版_创建二叉树

目录

一.二叉树的存储结构

二.二叉树的创建

三.二叉树的遍历

1.先序遍历

2.中序遍历

3.后序遍历

4.层序遍历

---

一.二叉树的存储结构

二叉树的基本存储结构如下所示

leftchild:存储左孩子节点的地址

rightchild:存储右孩子节点的地址

data：当前节点存储的信息

/*节点结构*/
typedef struct node
{
	char a;
	struct node* leftchild, * rightchild;
}Bitree;
1
2
3
4
5
6

二.二叉树的创建

创建一棵二叉树的关键在于如何将一个一个的节点按照树的脉络连接起来，在这里我们选择用一棵最小的满二叉树来说明

我们需要首先创建根节点，并且向里面保存数据，然后接着在向左孩子里面输入数据，最后是右孩子，其实这种从根节点开始，依次访问左节点，右节点的方式叫做先序（先序是针对根节点的操作来说的）

对于一个最小的满二叉树我们的做法是这样，那对于下面二叉树我们的做法是什么呢？

创建这样的一个二叉树需要什么步骤呢？ 首先创建A节点，然后是B,C节点，在B节点的下方只有一个节点所以我们在创建一个D节点？如果这样做的话，我们就不知道在某一个节点的下面是否存在一个节点或者是两个节点抑或是没有节点，所以对于这样的问题，我们所采取的措施，是对于每一个非叶节点，如果没有两个节点，则零一节点置空，那么对于节点来说，就都是两个节点，新的问题出现了，那怎么去置空呢？ 那我们就在输入数据的时候对于没有数据的节点，输入‘#’，如果等于字符等于‘#’，就返回NULL。

在这里我们依然采用递归的算法

void create(Bitree** T)
{
	char a;
	scanf_s("%c", &a);
	if (a == '#')
		(*T) = NULL;
	else
	{
		(*T) = (Bitree*)malloc(sizeof(Bitree));
		(*T)->a = a;
		create(&(*T)->leftchild);
		create(&(*T)->rightchild);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三.二叉树的遍历

1.先序遍历

先序遍历中的先序依然是对于树的根节点的操作顺序，其顺序为

1.访问根节点

2.前序遍历根节点的左子树

3.前序遍历根节点右子树

void xian(Bitree* T)
{
	if (T)
	{
		printf("%c", T->a);
		xian(T->leftchild);
		xian(T->rightchild);
	}
}
1
2
3
4
5
6
7
8
9

2.中序遍历

1.前序遍历根节点的左子树

2.访问根节点

3.前序遍历根节点右子树

void zhong(Bitree* T)
{
	if (T)
	{
		zhong(T->leftchild);
		printf("%c", T->a);
		zhong(T->rightchild);
	}
 }
1
2
3
4
5
6
7
8
9

3.后序遍历

1.后序遍历根节点的左子树

2.后序遍历根节点右子树

3.访问根节点

void hou(Bitree* T)
{
	if (T)
	{
		hou(T->leftchild);
		hou(T->rightchild);
		printf("%c", T->a);
	}
}
1
2
3
4
5
6
7
8
9

4.层序遍历

层序遍历是将一个二叉树从上到下，从左到右一层一层的把所有的数据都显示出来，在所有未被访问的节点的集合中，排列在已访问节点集合中最前面的节点的左子树最先被访问，然后是该节点的的右子树的根节点，如果将所有已被访问的节点放在一个队列中，那么所有未被访问节点的次序姐可以由存在队列中一访问节点的出对次序决定

其算法为：

1.初始化一个队列

2.将根节点指针入队列

3.当队列非空时，循环执行a-c的步骤

a.出队列取得一个节点指针，访问该节点

b.若该节点的左子树非空，则将该结点的左孩子指针入队列

c.若该节点的右子树非空，就将该节点的右孩子指针入队列

4.结束

具体代码如下

队列的子函数

void initiate(Q** O)
{
	(*O) = (Q*)malloc(sizeof(Q));
	(*O)->front = NULL;
	(*O)->last = NULL;
}

/*入队列*/
void append(Q* O, Bitree* p)
{
	Node* q;
	q = (Node*)malloc(sizeof(Node));
	q->p = p;
	q->next = NULL;
	if (O->last != NULL)O->last->next = q;
	O->last = q;
	if (O->front == NULL)O->front = q;
}

void out(Q* O, Bitree** p)
{
	Node* q;
	if (O->front == NULL)
	{
		printf("当前队列无元素！
");
		return;
	}
	else
	{
		(*p) = O->front->p;
		q = O->front;
		O->front = O->front->next;
		if (O->front == NULL)O->last = NULL;
		free(q);
		return;
	}
}
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

层序遍历函数

/*层序遍历*/
void ceng(Bitree* T)
{
	Q* O;
	Bitree* p;
	initiate(&O);
	append(O, T);
	while (O->last)
	{
		out(O, &p);
		printf("%c", p->a);
		if (p->leftchild)append(O, p->leftchild);
		if (p->rightchild)append(O, p->rightchild);
	}
	printf("
");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

函数测试如下所示