106.【C语言】数据结构之二叉树的三种递归遍历方式

目录

1.知识回顾

2.分析二叉树的三种遍历方式

1.总览

2.前序遍历

3.中序遍历

4.后序遍历

5.层序遍历

3.代码实现

1.准备工作

2.前序遍历函数PreOrder

测试结果

3.中序遍历函数InOrder

测试结果

4.后序遍历函数PostOrder

测试结果

4.底层分析

---

1.知识回顾

在99.【C语言】数据结构之二叉树的基本知识文章中提到:任何一棵树都由两部分构成:根和子树,子树又由根和子树构成

因此看见二叉树要本能地做出反应:拆成三部分:根,左子树和右子树,直到遇到空树(叶节点)则停止拆分

 

2.分析二叉树的三种遍历方式

1.总览

前序遍历

中序遍历

后序遍历

层序遍历(要借助队列,本文暂时不讲其代码实现)

下面三种遍历方式都基于上面这张图分析

2.前序遍历(也称先序遍历)

定义:按根-->左子树-->右子树的顺序遍历

遍历顺序:

1(根)-->2(根)-->3(根)-->NULL(3的左子树)-->NULL(3的右子树)-->NULL(2的右子树)-->4(根)-->5(根)-->NULL(5的左子树)-->NULL(5的右子树)-->6(根)-->NULL(6的左子树)-->NULL(6的右子树)

备注:图中每个方框都代表一棵子树

3.中序遍历

定义:按左子树-->根-->右子树的顺序遍历

这里有一个易错点也是关键点:中序遍历中第一个访问的一定为空!!!!

虽然1的左节点为2,但不能访问2(即不可访问root->data),按中序遍历的定义,要先访问2的左子树;虽然2的左节点为3,但不能访问3,按中序遍历的定义,先访问3左子树;3的左子树为NULL,其没有子树,因此开始访问根(即3),再访问根的右子树NULL,再回归......

左子树访问完才能访问根

遍历顺序:NULL(3的左子树)-->3-->NULL(3的右子树)-->2(根)-->NULL(2的右子树)-->1(根)-->NULL(5的左子树)-->5(根)-->NULL(5的右子树)-->4(根)-->NULL(6的左子树)-->6(根)-->NULL(6的右子树)

备注:图中每个方框都代表一棵子树  

4.后序遍历

定义:按左子树-->右子树-->根的顺序遍历

和中序遍历一样,也有一个易错点也是关键点:和中序遍历一样,先访问左子树,因此后序遍历中第一个访问的也一定为空!!!!

遍历顺序:NULL(3的左子树)-->NULL(3的右子树)-->3(根)-->NULL(2的右子树)-->2(根)-->NULL(5的左子树)-->NULL(5的右子树)-->5(根)-->NULL(6的左子树)-->NULL(6的右子树)-->6(根)-->4(根)-->1(根)

备注:图中每个方框都代表一棵子树   

5.层序遍历

定义:按层的方式遍历(,设n为树的深度,h==1-->h==2-->h==3-->...-->h==n)

遍历顺序:1-->2-->4-->3-->5-->6

h==1为第一层,只有1;h==2为第二层,有2和4;h==3为第三层,有3,5和6;

3.代码实现

1.准备工作

用结构体去定义一个二叉树,其成员变量有:数值域data,结构体指针变量left和right,分别指向其对应的左子树和右子树(写入Tree.h)

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

定义完二叉树后还要开辟空间函数BuyNode和建立树的函数(写入Tree.c)

BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

建立指定的二叉树,见下图

 

BTNode* CreateTree()
{//写入各个节点的数据域BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//设置left和right指针node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;//返回根节点的指针return node1;
}

递归返回的条件:遇到空树(NULL)

2.前序遍历函数PreOrder

按根-->左子树-->右子树的顺序遍历,

即printf("%d ",root->data);-->PreOrder(root->left);-->PreOrder(root->right);

void PreOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按根-->左子树-->右子树的顺序遍历printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树)

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{BTNode* root = CreateTree();PreOrder(root);return 0;
}

和前面的图完全符合

3.中序遍历函数InOrder

:按左子树-->根-->右子树的顺序遍历,

即InOrder(root->left);-->printf("%d ", root->data);-->InOrder(root->right);

void InOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按左子树-->根-->右子树的顺序遍历InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树) 

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{BTNode* root = CreateTree();InOrder(root);return 0;
}

 

 和前面的图完全符合

4.后序遍历函数PostOrder

按左子树-->右子树-->根的顺序遍历,

即PostOrder(root->left);-->PostOrder(root->right);-->printf("%d ", root->data);

void PostOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按左子树-->右子树-->根的顺序遍历PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树) 

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{BTNode* root = CreateTree();PostOrder(root);return 0;
}

和前面的图完全符合

4.底层分析

每调用一次PreOrder或InOrder或PostOrder函数就压入栈区,返回时出栈

在E41.【C语言】练习:斐波那契函数的空间复杂度的计算及函数调用分析文章中讲过了函数调用的堆栈分析,这里不再赘述

附一张PreOrder的调用图

附一张InOrder的调用图