二叉树的遍历顺序（二叉树的遍历顺序）
本文目录
二叉树的遍历顺序
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。 线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。在后序线索树中找到结点的后继分三种情况：若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。数据结构定义为：/*二叉线索存储表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指针，Thread(1)：线索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指针*/PointerTag LTag,RTag;/* 左右标志 */}BiThrNode,*BiThrTree;
二叉树遍历前序中序后序
前序遍历（dlr）前序遍历也叫做先根遍历，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。若二叉树为空则结束返回，否则：（1）访问根结点（2）前序遍历左子树（3）前序遍历右子树注意的是：遍历左右子树时仍然采用前序遍历方法。中序遍历（ldr）中序遍历也叫做中根遍历，可记做左根右。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：若二叉树为空则结束返回，否则：（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树。注意的是：遍历左右子树时仍然采用中序遍历方法。后序遍历（lrd）后序遍历也叫做后根遍历，可记做左右根。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：若二叉树为空则结束返回，否则：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根结点。注意的是：遍历左右子树时仍然采用后序遍历方法。如上图所示二叉树前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树遍历结果：a,b,e,f,c,g中序遍历，也叫中根遍历，顺序是左子树，根，右子树遍历结果：e,b,f,a,g,c后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根遍历结果：e,f,b,g,c,a
更多文章：
2025年3月13日 01:40
2025年2月15日 03:10
equals to（A equals B 与 A equals to B 这两个用法都对吗）
2025年3月9日 10:30
toaster oven（电烤箱上Grill、Oven、Toast是什么意思）
2025年3月15日 08:00
2025年3月2日 08:00
用switch语句输出成绩等级（在java里面利用switch case求出成绩所在等级如何做）
2025年2月19日 11:20
使命召唤ol（codol）体验服怎么进去！？codol算不算动视暴雪
2025年3月2日 04:50
2025年3月31日 19:40
2025年4月4日 07:20
2025年3月15日 10:40
16进制转10进制c语言代码（C语言写一个函数，16进制转十进制）
2025年3月13日 13:40
2025年3月13日 03:00
2025年3月13日 18:50
2025年3月4日 08:30
2025年2月10日 05:30
compare with to（怎么区分compare with和compare to）
2025年3月27日 05:10
2025年2月23日 13:20
interesting是什么意思英语（“interesting”怎么读）
2025年2月9日 05:00
condescending（condescending什么意思）
2025年4月2日 09:40
drawable是什么意思（drawablehdpi什么意思）
2025年3月15日 14:30
