C语言实现二叉树的链式存储

实验目的

（1）能实现二叉树链式存储结构下的创建及遍历算法；
（2）能根据实际问题，设计二叉树存储结构并设计相应算法。

实验内容

（1）二叉树链式存储结构设计及二叉树创建和遍历算法；
（2）实现二叉树中树叶结点的输出和左右子树互换算法。

实验要求

构造一棵二叉树，并进行遍历
要求：

1. 二叉树的构造
   可以输入树的先根序遍历序列，然后进行构造;
   也可采用按层次构造二叉树的方法。

2. 实现二叉树访问的算法（先序、中序、后序）

3. 实现二叉树中树叶结点的输出和左右子树互换算法

注意：
在构造二叉树，输入树的先根序的时候，树的先根序必须是完整的
例如下图的二叉树，在采用先根序构造时，输入的先根序序列为eba###f##

总体上是对完成本次实验题目的设计过程的论述。题目的设计思路、设计过程、相关算法等进行论述说明。包括设计说明（文字）、代码或主要代码及运行结果等。
1

---

实验过程

设计思路

• 叶子节点的输出：当遍历到该节点的后继节点为空，则输出该节点；
  左右子树互换算法，只要当前节点不为空，就交换该节点的左右孩子。

代码实现解释

• 定义二叉树节点，成员有节点信息和左右孩子。

• 定义一个节点输出函数。

• 创建先序遍历存储的二叉树，并返回根节点的指针，采用递归的方式，当输入#返回NULL。

• 递归前序遍历，先打印根节点再打印左右孩子节点。

• 递归中序遍历，先打印左孩子节点再打印右孩子节点。

• 递归后序遍历，先打印左孩子节点再有孩子节点，最后根节点。

• 递归打印叶子节点，判断树是否为空，不为空，看当前节点的左右孩子是否均为空，是打印。

• 递归交换左右子树，直到当前节点为空。

代码实现如下

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

typedef char DataType;

//定义二叉树节点 
struct node 
{
	DataType data;
	struct node *lchild, *rchild;
};

typedef struct node Bitree;
typedef struct node *Ptree;


//输出节点数据
void print(DataType d)
{
	printf("%c ", d);
}


//创建二叉树，并返回根结点指针 
Ptree createBitree()
{
	DataType data;
	Ptree root=(Ptree )malloc(sizeof(struct node));
	data=getchar();
	
	if(data=='#') 
		return NULL;
	else								//按照先序遍历进行存储 
	{
		root->data=data;
		root->lchild=createBitree();
		root->rchild=createBitree();
	}
	return root;
}


// 递归先序遍历二叉树，传入二叉树根结点指针 
int preOrder(Ptree t)
{
	 
	if(t==NULL) return 1;
	
	print(t->data);			// DLR遍历 
	preOrder(t->lchild);
	preOrder(t->rchild);
}

// 中序遍历 
int midOrder(Ptree t)
{
	if(t==NULL) return 1;

	midOrder(t->lchild);
	print(t->data);			// LDR遍历 
	midOrder(t->rchild);
}
 

//后序遍历 
int subsequentOrder(Ptree t)
{
	if(t==NULL) return 1;
	

	midOrder(t->lchild);
	midOrder(t->rchild);
	print(t->data);			// LRD遍历 
}


//打印叶子节点 
int printLeaves(Ptree t)
{
	if(t==NULL) return 0;
	
	if((t->lchild==NULL) && (t->rchild==NULL)) printf("%c ", t->data);
	
	else
	{
		printLeaves(t->lchild);
		printLeaves(t->rchild);
	}
} 

int ChangeLR(Ptree t)
{
	Ptree p;//=(Ptree )malloc(sizeof(struct node)); 不用动态分配也可以 
	if(t==NULL) return;

	p=t->lchild;
	t->lchild=t->rchild;
	t->rchild=p;
	
	ChangeLR(t->lchild);
	ChangeLR(t->rchild);
}


int main()
{
	Ptree t;
	int i=0;
	t=createBitree();	 	//先序遍历进行存储 

	printf("前序遍历： ");
	preOrder(t);
	printf("\n");
	
	printf("中序遍历： ");
	midOrder(t);
	printf("\n");

	printf("后序遍历： ");
	subsequentOrder(t);
	printf("\n");

	printf("打印叶子节点： ");
	printLeaves(t);      //成功打印叶子节点 
	printf("\n");

	printf("左右子树交换后的前序遍历： ");
	ChangeLR(t);
	preOrder(t);
	printf("\n");
	
	return 0;
}

// 输入样例eba###f## 
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

输出结果如下

了解每一行代码，理清思路，很有用哟
喜欢那就点个赞吧，嘿嘿~