如何将遍历二叉树的代码实现改写为一个长尾词的？

本文共计840个文字，预计阅读时间需要4分钟。

二叉树的遍历有三种主要方式：先序遍历（根-左-右）、递归法和非递归法，中序遍历（左-根-右）、递归法和非递归法，后序遍历（左-右-根）、递归法和非递归法。

二叉树的遍历

• ​​先序遍历（根--左--右）​​

• ​​递归法​​
• ​​非递归法​​

• ​​中序遍历（左--根--右）​​

• ​​递归法​​
• ​​非递归法​​

• ​​后序遍历（左--右--根）​​

• ​​递归法​​
• ​​非递归法​​

• ​​层序遍历​​

先序遍历（根–左--右）

递归法

void PreOrder(BiTree T){
if(T != NULL){
visit(T); //访问根节点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}

非递归法

void PreOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
vist(p) //访问拍p
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
Pop(S,p); //p出栈
p = p->rchild; //转向右子树遍历
}
}
}

中序遍历（左–根--右）

void InOrder(BiTree T){
if(T != NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}

void InOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
Pop(S,p); //p出栈
visit(p); //访问p
p = p->rchild; //转向右子树遍历
}
}
}

后序遍历（左–右--根）

void PostOrder(BiTree T){
if(T != NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根节点
}
}

void PostOrder(BiTree T){
InitStack(S); //使用栈存储二叉树的节点
BiTree p = T; //p为遍历二叉树的指针
BiTree r = NULL; //记录最近访问的节点
while(p || !IsEmpty(S)){ //二叉树不为空或栈不空是继续循环
if(p != NULL){
Push(S,p); //p节点入栈
p = p->lchild; //继续向左遍历
}
else{
GetTop(S,p); //读取栈顶节点，不出栈
if(p->rchild && p->rchild != r){ //右子树存在，且未被访问
p = p->rchild;
Push(S,p); //p节点入栈
p = p->lchild; //转左遍历
}
else{
Pop(S,p); //p出栈
visit(p); //访问p
r = p; //记录最近一次访问的节点
p = NULL;
}
}
}
}

层序遍历

void LevelOrder(BiTree T){
InitQueue(Q); //使用队列存储二叉树节点
BiTree p;
EnQueue(Q,T); //根节点入队
while(!IsEmpty(Q)){ //队列不空继续循环
DeQueue(Q,p); //队头节点出队
vist(p); //访问队头节点
if(p->lchild != NULL){
EnQueue(Q,p->lchild); //左孩子入队
}
if(p->rchild != NULL){
EnQueue(Q,p->rchild); //右孩子入队
}
}
}