欢迎访问我的博客地址 : 博客地址
树(tree)是一类比较重要的非线性的数据结构。之所以叫“树”，是因为它看起来像是一棵倒挂的树，根朝上，叶朝下。
树，是一种递归定义的数据结构。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y9lj6v67-1660706484179)(https://git.poker/quinhua/pics/blob/main/markdown/tgberfg8uh.1xtlsnca9f4w.jpg?raw=true)]
以上图为准，下面介绍相关概念：
根节点(root)，例如图中的R。二叉树（Binary tree）是指树中节点的度不大于2的有序树，当节点数为0时，是一棵空树，否则为非空树。它是数据结构中的重点研究对象。
有如下特征或性质：
下图是一个以节点A为根的二叉树：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fAzMjVev-1660706484181)(https://git.poker/quinhua/pics/blob/main/markdown/ju8ujgy6yg.737w0sh849c0.jpg?raw=true)]
还记得前面我说的树是一种递归定义的数据结构吗？带着这种思想来学习二叉树树的遍历吧。
前序遍历(Pre-Order Traversal)的次序为：根 -> 左 -> 右。
根 -> 左 -> 右的次序遍历A的右子树即可。最后可以得到前序遍历的结果：A -> U -> T -> I -> S -> N -> X, 也即是从A出发，沿着这棵树的外围绕了一圈，但重要的思想还是：树是递归定义的数据结构。
当先序遍历一棵二叉树时，根节点总是在第一个。
中序遍历(In-Order Traversal)的次序为：左 -> 根 -> 右。
最后可以得到中序遍历的结果：T -> U -> I -> A -> N -> S -> X。当中序遍历一棵满而二叉树(比如上图中的树)时，根节点总是在结果的中间。
后序遍历(Post-Order Traversal)的次序为：左 -> 右 -> 根。
最后可以得到后序遍历的结果：T -> I -> U -> N -> X -> S -> A。后序遍历一棵二叉树，根节点总是在最后一个。
层次遍历很简单，按照层次，从上到下，从左到右。
层次遍历的结果是：A -> U -> S -> T -> I -> N -> X.
/* 树的节点 */
typedef struct tree_node {
/* 左孩子指针 */
struct tree_node *left;
/* 右孩子指针 */
struct tree_node *right;
/* 关键字 */
char key;
}tree_node;
这个结构体定义了指向树的节点的左右指针，以及一个char类型的关键字, key。
/* 创建一个节点 */
tree_node *tree_create_node(char key)
{
tree_node *node = (struct tree_node*)malloc(sizeof(struct tree_node));
if(node==NULL) return NULL;
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
上面的方法，接收一个关键字(key)作为参数，然后使用创建一个二叉树的节点并初始化，最后返回指向该节点的指针。
/* 创建一棵二叉树 */
tree_node *tree_create()
{
char str;
tree_node *current;
scanf("%c", &str);
if('#' == str)
{
current = NULL;
}
else {
current = tree_create_node(str);
current->left = tree_create();
current->right = tree_create();
}
return current;
}
递归法创建一颗二叉树。
#表示空节点，按照先序遍历的次序，生成二叉树。注意，使用该函数时，用户一次输入一颗完整的二叉树。 比如：
ABD##E##CF##G##
按道理，递归创建，该函数会被自己多次调用，我们就应该输入多次，以表示节点的字符。但由于我们在最开始一次输入完了，所以每次scanf函数都会从缓冲区读取一个字符并执行程序。
最后我们成功创建了一颗如下的二叉树：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bNEz3Rdj-1660706484182)(https://git.poker/quinhua/pics/blob/main/markdown/cde4rfde3.2c8ph4zo8ntw.jpg?raw=true)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NUWl0ee3-1660706484183)(https://git.poker/quinhua/pics/blob/main/markdown/de4rfde45tf.6ubza0j33f40.jpg?raw=true)]
这里函数不仅可以遍历一颗完整的二叉树，还可以遍历以参数节点为根节点的子树。
看这段程序，只需要记住树的基本哲学是递归，以及对应的遍历次序即可。
/* 前序遍历 */
void preorder_traverse1(tree_node *node)
{
if(node != NULL) {
printf("%c\t", node->key);
preorder_traverse1(node->left);
preorder_traverse1(node->right);
}
}
/* 中序遍历 */
void inorder_traverse1(tree_node *node)
{
if(node != NULL) {
inorder_traverse1(node->left);
printf("%c\t", node->key);
inorder_traverse1(node->right);
}
}
/* 后序遍历 */
void postorder_traverse1(tree_node *node)
{
if(node != NULL) {
postorder_traverse1(node->left);
postorder_traverse1(node->right);
printf("%c\t", node->key);
}
}
非递归法主要是利用了栈来实现(模拟递归，其实函数的递归本身就是栈实现的)，这里我们直接用前面章节实现的栈就可以。
代码中别忘了把之前写好的
stack.h与stack.c放入当前目录中，并且写好头文件包含：
#include "stack.h"
非递归法前序遍历二叉树的思路：
沿着这个思路就很容易实现非递归前序遍历：
/* 前序遍历2 */
void preorder_traverse2(tree_node *node)
{
stack *stack = stack_create();
tree_node *current = node;
while (current != NULL || stack->length)
{
if(current != NULL) {
printf("%c\t", current->key);
stack_push(stack, current);
current = current->left;
} else {
current = stack_pop(stack);
current = current->right;
}
}
stack_release(stack);
}
非递归中序遍历也是用栈来实现，思路大致相同：
/* 中序遍历2 */
void inorder_traverse2(tree_node *node)
{
stack *stack = stack_create();
tree_node *current = node;
while (current != NULL || stack->length)
{
if(current != NULL) {
stack_push(stack, current);
current = current->left;
} else {
current = stack_pop(stack);
printf("%c\t", current->key);
current = current->right;
}
}
stack_release(stack);
}
非递归后序遍历略有不同，这里用的是较为简单的思路：双栈。
第一个栈用根 -> 右 -> 左的顺序非递归遍历二叉树，利用第二个栈把结果反过来，就是后序遍历的顺序左 -> 右 -> 根，妙不？
/* 后序遍历2 */
void postorder_traverse2(tree_node *node)
{
stack *s = stack_create();
stack *stack = stack_create();
tree_node *current = node;
while (current != NULL || stack->length)
{
if(current != NULL) {
stack_push(s, &(current->key));
stack_push(stack, current);
current = current->right;
} else {
current = stack_pop(stack);
current = current->left;
}
}
while (s->length)
{
printf("%c\t", *(char *)stack_pop(s));
}
stack_release(s);
stack_release(stack);
}
层次遍历一颗二叉树，比较简单，利用队列。这里也用前面章节写好的就行。
代码中别忘了把之前写好的
queue.h与queue.c放入当前目录中，并且写好头文件包含：
#include "queue.h"
层次遍历的基本思路：
/* 层次遍历 */
void level_traversel(tree_node *root)
{
/* 创建一个队列 */
queue *queue = queue_create();
if(root != NULL)
{
queue_push_data(queue, root);
}
while (queue->length)
{
tree_node *current = queue_pull_data(queue);
printf("%c\t", current->key);
if(current->left) queue_push_data(queue, current->left);
if(current->right) queue_push_data(queue, current->right);
}
/* 队列用完后，释放 */
queue_release(queue);
}
测试函数写在main函数中。
int main() {
/* ABD##E##CF##G## */
tree_node *root = tree_create();
printf("\n前序遍历1：");
preorder_traverse1(root);
printf("\n前序遍历2：");
preorder_traverse2(root);
printf("\n\n中序遍历1：");
inorder_traverse1(root);
printf("\n中序遍历2：");
inorder_traverse2(root);
printf("\n\n后序遍历1：");
postorder_traverse1(root);
printf("\n后序遍历2：");
postorder_traverse2(root);
printf("\n\n层次遍历0：");
level_traversel(root);
printf("\n");
return 0;
}
编译命令：
# gcc *.c && ./a.out
输入：
ABD##E##CF##G##
输出：
前序遍历1：A B D E C F G
前序遍历2：A B D E C F G
中序遍历1：D B E A F C G
中序遍历2：D B E A F C G
后序遍历1：D E B F G C A
后序遍历2：D E B F G C A
层次遍历0：A B C D E F G