热心网友
回答时间：2023-08-10 08:11
9二叉树的遍历（1）遍历：遍历（traverse）一个有限结点的集合，意味着对该集合中的每个结点访问且仅访问一次。（2）三种遍历方式先序遍历（VLR）：先序就是先访问结点元素，然后是左，然后是右。若二叉树不为空
访问根结点；
先序遍历左子树；
先序遍历右子树。
先序遍历序列：
A
B
D
C
E
F
template
void
BinaryTree
::PreOrder(){
PreOrder(root);}template
void
BinaryTree
::PreOrder(BTNode
*
t){
if(t)
{
cout<<(t->element);
PreOrder(t->lChild);
PreOrder(t->rChild);
}}
中序遍历（LVR）若二叉树不为空
中序遍历左子树；
访问根结点；
中序遍历右子树。
中序遍历序列：B
D
A
E
C
F
template
void
BinaryTree
::InOrder(){
InOrder(root);}template
void
BinaryTree
::InOrder(BTNode
*
t){
if(t)
{
InOrder(t->lChild);
cout<<(t->element);
InOrder(t->rChild);
}}
后序遍历
（LRV）若二叉树不为空
后序遍历左子树；
后序遍历右子树；
访问根结点。后序遍历序列：D
B
E
F
C
A
template
void
BinaryTree
::PostOrder(){
PostOrder(root);}template
void
BinaryTree
::PostOrder(BTNode
*
t){
if(t)
{
PostOrder(t->lChild);
PostOrder(t->rChild);
cout<<(t->element);
}}
收起
热心网友
回答时间：2023-08-10 08:12
遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)，
（2）遍历该结点的左子树(L)，
（3）遍历该结点的右子树(R)。
三种遍历的命名
根据访问结点操作发生位置命名：
①
NLR：前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
②
LNR：中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③
LRN：后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node)、L(Left
subtree)和R(Right
subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历结点的左子树；
(2)访问当前结点；
(3)遍历结点的右子树。
2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)
访问当前结点；
(2)
遍历结点的左子树；
(3)
遍历结点的右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历结点的左子树；
(2)遍历结点的右子树；
(3)访问当前结点。
4．中序遍历的算法实现
用二叉链表做为存储结构，中序遍历算法可描述为：
void
InOrder(BinTree
T)
{
//算法里①~⑥是为了说明执行过程加入的标号
①
if(T)
{
//
如果二叉树非空
②
InOrder(T->lchild)；
③
printf("％c"，T->data)；
//
访问结点
④
InOrder(T->rchild);
⑤
}
⑥
}
//
InOrder
还有什么不明白的请继续追加~
收起
