【数据结构】二叉树（一）遍历

导言

前面以及有了堆的基础，现在来学习二叉树。二叉树的学习和前面的数据结构很不一样，前面我们主要学习用数据结构储存数据，以及实际手搓数据结构的增删查改；而学习二叉树主要是为我们以后学搜索二叉树以及后面的AVL树等数据结构做准备，我们主要学习遍历二叉树，学一下二叉树的结构。

二叉树的遍历

二叉树由结点组成，一个父节点最多有两个子节点

相信大家基本上都在学校学习过二叉树的遍历，但是其中的具体细节不一定清楚明白。

二叉树的遍历根据访问根节点的顺序分为三种

前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历：先访遍历左子树，然后遍历右子树，最后访问根节点。

前序遍历

接下来我们来手动测试一下前序遍历

前置说明

这里我们来定义一下二叉树的结构

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct BinaryTreeNode
{int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

在测试的我们可以自己手搓一个二叉树测试用例出来

BTNode* BuyNode(int x)
{BTNode* node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* b1 = BuyNode(1);BTNode* b2 = BuyNode(2);BTNode* b3 = BuyNode(3);BTNode* b4 = BuyNode(4);BTNode* b5 = BuyNode(5);BTNode* b6 = BuyNode(6);b1->left = b2;b1->right = b4;b2->left = b3;b4->left = b5;b4->right = b6;return b1;
}

这样我们就得到了一个二叉树

接下来用代码实现前序遍历，用递归实现。如果是NULL输出N并返回（注意return 不会直接结束程序，而是结束这次函数调用，如果是递归实现，可能还有很多次函数调用），否则输出data.

//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

调用关系图（逻辑图）：

 栈帧开辟销毁情况：

代码运行结果

 中序遍历

遍历的顺序不同就是访问头节点的顺序不同，中序遍历就是访问左子树后才访问头节点

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

我们先来看看运行结果

调用关系图（逻辑图）：

 

后序遍历

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}

执行结果：

调用关系图（逻辑图）：