大家好，欢迎来到IT知识分享网。
【数据结构】树—中序遍历
文章目录
一、什么是中序遍历？
二、中序遍历详解
这是一棵二叉查找树。
以该树为例，如何进行中序遍历？请看我一步步的画图演示。
左根右，指的是遍历的顺序，先遍历左节点，再遍历根节点，最后遍历右节点。
以下图为例，我们进行中序遍历：
10是根节点，先查10的左节点，查到了5节点。
将5当作暂时的根节点，先查5的左节点，查到了3节点。
将3当作暂时的根节点，先查3的左节点，3没有左节点，于是返回至3节点，输出3。
3的左节点、3本身都已经遍历完成，接下来查3的右节点，查到了4节点
将4当作暂时的根节点，先查4的左节点，4没有左节点，于是返回至4节点，输出4。
4的左节点、4本身都已经遍历完成，接下来查4的右节点，4没有右节点，于是返回至4节点。
此时4的左节点、4本身、4的右节点都已经遍历完成，返回其上一级节点：3节点。
此时3的左节点、3本身、3的右节点都已经遍历完成，返回其上一级节点：5节点。
此时5的左节点已经遍历完成，输出5。
5的左节点、5本身都已经遍历完成，接下来查5的右节点，查到了9节点。
将9当作暂时的根节点，先查9的左节点，9没有左节点，于是返回至9节点，输出9。
此时21的左节点、21本身、21的右节点都已经遍历完成，返回其上一级节点：18节点。
此时18的左节点、18本身、18的右节点都已经遍历完成，返回其上一级节点：10节点。
此时根节点10的左节点、根节点本身、根节点的右节点都已经遍历完成，这棵树的中序遍历完成。
遍历结果：
[3，4，5，9，10，18，19，21，33，59]
我们可以发现，二叉查找树经过中序遍历后，会变得有序，当然，这个顺序是依靠二叉查找树的排序规则来进行的。如果排序规则是左边大，右边小，那么经过中序遍历后的序列会是倒序的。
总结
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/109730.html
