二叉树的遍历
二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点有且仅有一次被访问
从定义中提取到核心词汇是 访问和次序 ，由此萌生出了二叉树的遍历方式
前序遍历:
若二叉树为空，则空操作返回，否则，先访问根节点，再访问左子树，最后访问右子树。图中输出的序列是：ABDGHCEIF
前序遍历参考代码
//所涉及的结构体 typedef struct tnode { char data; struct tnode *lchild ,*rchild; }BT;// Binary Tree
void PreOrder(BT *T) { if(T == NULL) return ; else { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } }
中序遍历：
若二叉树为空，则空操作返回，否则从根节点开始，先访问根的左子树，再访问根节点，最后访问根的右子树。图中输出的序列是：GDHBAEICF
中序遍历参考代码
void InOrder(BT *T) { if(T == NULL) return ; else { InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } }
后序遍历：
若二叉树为空，则空操作返回，否则从根节点开始，先访问根的左子树，再访问根的右子树，最后访问根节点。图中输出的序列是：GHDBIEFCA
后序遍历参考代码
void PostOrder(BT *T) { if (T == NULL) return ; else { PostOrder(T->lchild) ; PostOrder(T->rchild); printf("%c",T->data); } }
小总结
从加粗的位置可以看出，前序、中序、后序的区别是什么时候访问根节点。需要注意的是，若二叉树为空的情况一定一定一定要考虑，笔者曾因为比赛忘记这一步特判,流下悔恨的眼泪😭😭😭
层序遍历：
若二叉树为空，则空操作返回，否则从树的第一层。也就是根开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。
层序遍历参考代码
//层序遍历用到了队列这种数据结构 void LevelOrder(BT *T) { int f,r; //队头指针和队尾指针 BT *p,*q[MAX] ; //循环队列，存放结点指针 p = T; if( p != NULL) //二叉树非空 { f = 1; q[f] = p; r = 2; } while(f != r) //当队列不为空 { p = q[f]; printf("%c",p->data); if(p->lchild != NULL) { q[r] = p->lchild; r = (r + 1) % MAX;//更新尾指针r } if(p->rchild != NULL) { q[r] = p->rchild; r = (r+1)%MAX; } f =(f+1)%MAX;//更新头指针f } }
