二叉树的遍历方式有很多种:前序遍历、中序遍历、后序遍历以及层序遍历等,遍历也可分递归与非递归方式,下面将用以下这颗二叉树进行各个遍历方式的讲解:
———————————————————————— 下面是正文 —————————————————————————
一.先序遍历(递归方式)
先序遍历的遍历顺序为:中左右。
按照此顺序对上述二叉树进行遍历的步骤为:
先访问主结点:
再访问左结点:
理论上是要访问该结点的左结点,但是该结点的左结点不存在,所以访问其右节点:
后来,访问该结点的左结点,没有,再访问右结点,也没有,所以以“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;}}
}
五.层序遍历
层序遍历最简单,就是从上往下进行遍历,如以下二叉树:
使用层序遍历就可以按照顺序进行输出:1,2,3,5,6,13,代码思路可以选择使用队列+递归来实现,根据队列的“先进后出”的特性可以满足层序遍历的需求。
更多推荐
递归,遍历,堆栈,数据结构,与非
发布评论