【数据结构】二叉树的遍历方式：前中后序遍历（递归与非递归堆栈方法实现）、层序遍历

编程入门行业动态更新时间:2024-10-28 14:23:52

二叉树的遍历方式有很多种：前序遍历、中序遍历、后序遍历以及层序遍历等，遍历也可分递归与非递归方式，下面将用以下这颗二叉树进行各个遍历方式的讲解：

———————————————————————— 下面是正文 —————————————————————————

一.先序遍历（递归方式）

先序遍历的遍历顺序为：中左右。

按照此顺序对上述二叉树进行遍历的步骤为：

先访问主结点：

再访问左结点：

理论上是要访问该结点的左结点，但是该结点的左结点不存在，所以访问其右节点：

后来，访问该结点的左结点，没有，再访问右结点，也没有，所以以“1”为主结点的左边遍历结束，开始遍历右边结点：

访问左结点：

然后访问其左结点，没有，所以访问其右结点：

最后访问结点“3”的右结点，没有，结束遍历，所以前序遍历最后输出：

代码使用递归的方式进行遍历，代码量少，但是占用空间资源大：

void Preorder(Node* n)
{if (n){printf("%d ", n->data);Preorder(n->left);Preorder(n->right);}
}

二.中序遍历（递归）

中序遍历的遍历顺序为：左中右。

按照此顺序对上述二叉树进行遍历的步骤为：

先访问左结点：

再访问结点 “2” 的左结点，但是没有，所以左边遍历结束，输出中结点 “2” ，再访问右结点，输出“5”：

然后主结点 “1” 的左节点遍历完成，访问中结点，也就是自己，输出 “1” ：

开始访问 “1” 的右结点 “3” ：

左结点存在，所以访问其左结点：

再访问 “6” 的左结点，但是不存在，所以访问中结点，也就是自己，输出“6”，访问右结点：

身为右结点的“13” 即没有左结点也没有右结点，所以输出自己，跳回到 “3” ：

理论上访问完“3”的左结点后开始访问其右结点的，但是不存在，所以输出自己 “3” ，最后得出中序遍历的结果：

代码如下（递归方法）：

void Middle_order(Node* n)
{if (n){Middle_order(n->left);printf("%d ", n->data);Middle_order(n->right);}
}

三.后序遍历（递归）

后序遍历的遍历顺序为：左右中。

按照此顺序对上述二叉树进行遍历的步骤为：

先访问左结点：

再访问“2”的左结点，没有，所以访问右结点“5”：

访问“5”的左右结点，没有，所以输出自己，箭头指回“2”：

至此“1”的左边结点遍历完成，开始遍历右边结点，箭头指向“3”：

访问其左结点“6”：

随后再访问“6”的左结点，没有，所以访问其右结点“13”：

“13”没有左右结点，所以输出自己，箭头指回“6”：

输出“6”，箭头指回“3”，输出“3”，主结点“1”的右结点也遍历完成，最后输出中结点，也就是自己“1”：

最后得出中序遍历的结果：

代码如下（递归方法）：

void Post_order(Node* n)
{if (n){Post_order(n->left);Post_order(n->right);printf("%d ", n->data);}
}

四.前中后序非递归堆栈方法

使用堆栈的方法可以避免递归过程中遇到的空间资源浪费的问题，前中后序的堆栈方法都相类似，所以下面以中序遍历为例子进行讲解，堆栈的核心思想是遍历的结点存在，则压入栈中，不存在，则将栈中数据压出，第一步是先创建一个空栈：

按照先序遍历的顺序是中左右，所以先将主结点 “1” 压入栈中：

随后访问其左结点 “2”，将其压入栈中：

再访问“2” 的左结点，没有，所以从栈中压出一个数据“2”：

随后访问右结点“5”，存在，所以将其压入栈中：

随后访问“5”的左结点，不存在，所以从栈中压出一个数据：

再访问“5” 的右结点，没有，所以再次从栈中压出一个数据：

至此结点“1” 的左结点遍历完成，开始遍历其右结点“3”，压入栈中：

然后访问其左结点“6”，压入栈中：

再访问其左结点，不存在，所以压出栈中一个数据：

访问其右结点“13”，压入栈中：

访问“13”的左结点，不存在，从栈中压出一个数据：

最后访问“13”的右结点，不存在，所以压出栈中的数据：

最后输出中序遍历后的结果：

中序遍历代码如下：

void Stack_Middle_order(Node* n)
{Node* N = n; //创建二叉树Stack S = CreateStack(100); //创建栈while (N || !IsEmpty(S)){while (N){Push(S, N); //压栈N = N->left;}if (!IsEmpty(S)) //判断栈堆是否为空{N = Pop(S); //出栈                printf("%d ", N->data);N = N->right;}}
}