引入

其中，中序遍历可以唯一确定二叉树，而前序遍历和后序遍历无法唯一确定二叉树。

---

定义

二叉树的遍历是指按一定规律对二叉树中的每个结点进行访问且仅访问一次。

其中，二叉树的基本结构由根结点、左子树和右子树组成

typedef struct BTNode { char data; struct BTNode * lchild; struct BTNode * rchild; }BTNode

---

先序遍历（DLR）

若二叉树为空，则空操作，否则依次执行如下操作：

（1）访问根结点； （2）按先序遍历左子树； （3）按先序遍历右子树。

void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*先序遍历左子树*/ PreOrder(root ->RChild); /*先序遍历右子树*/ } }

使用先序遍历查找指定结点

// 不剪枝 BTNode *search(BTNode *p,int key) { if(p!=NULL){ if(p->data==key) return p; else{ search(p->lchild,key); search(p->rchild,key); } } return NULL; // 如果树是空树，则返回NULL，即查找失败 } // 剪枝 BTNode *search(BTNode *p,int key) { BTNode *q； if(p!=NULL){ if(p->data==key) return p; else{ q=search(p->lchild,key); // 到左子树中查找 if(q==NULL) // 在左子树中没找到才到右子树中查找 search(p->rchild,key); } } return NULL; // 如果树是空树，则返回NULL，即查找失败 }

---

中序遍历（LDR）

若二叉树为空，则空操作，否则依次执行如下操作：

（1）按中序遍历左子树 （2）访问根结点 （3）按中序遍历右子树

void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } }

---

后序遍历（LRD）

若二叉树为空，则空操作，否则依次执行如下操作：

（1）按后序遍历左子树； （2）按后序遍历右子树； （3）访问根结点。

void PostOrder(BiTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root->data); /*访问根结点*/ } }

使用后序遍历求表达式的值

int comp(BTNode *p) { int A,B; if(p!=NULL) { if(p->lchild!=NULL&&p->rchild!=NULL) // 如果当前结点的左子树和右子树非空，则为表达式（即当前结点为运算符），用后序遍历方式求值 { A=comp(p->lchild); // 左子树的值 B=comp(p->rchild); // 右子树的值 return op(A,B,p->data) // 得出当前结点的值 } else return p->data-'0'; // 如果当前结点的左子树和右子树为空，则当前结点为数值 } else return 0; // 如果为空树，则表达式的值为0 }

---

层次遍历

要进行层次遍历，需要建立一个循环队列。

（1）先将二叉树头结点入队列， （2）队头结点出队，并访问该结点 （3）出队结点的左右子树的根结点依次入队。

void level(BTNode *p) { int front,rear; BTNode *que[maxSize]; // 定义一个循环队列 front=rear=0; BTNode *q; // 用于保存出队的结点 if(p!=NULL) { rear=(rear+1)%maxSize; que[rear]=p; // 根结点入队 while(front!=rear) // 当队列不空时，进行循环 { front=(front+1)%maxSize; // 队头结点出队，访问 q=que[front]; printf("%c",q->data); if(p->lchild!=NULL) // 将出队结点的子结点入队 { rear=(rear+1)%maxSize; que[rear]=q->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%maxSize; que[rear]=q->rchild; } } } }