1.概览
二叉树的遍历(traversing binary tree)是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个节点被访问依次且仅被访问一次。
注意：
- 从根节点出发，并不一定是从根节点开始遍历，只是从根节点开始逻辑
- 次序表示有一定的规则
- 访问表示可以得到这个结点的信息
二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。
二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为以下四种：
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
2.前序遍历
定义：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
二叉树前序遍历的顺序图示
如图所示，先访问根节点A，然后访问A的左子树B，再访问B的左子树D，再访问D的左子树H，由于H是终端结点，则再访问D的右子树I，访问完了B的左子树，再访问B的右子树，剩下的类推可得到
总结：前序遍历中，遵循根节点->左子树->右子树的顺序来访问结点
3. 中序遍历
定义：若二叉树为空，则空操作返回，否则从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。
二叉树的中序遍历的顺序图示
总结：中序遍历遵循左子树->根节点->右子树的顺序来访问结点
4.后序遍历
定义：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根节点
二叉树的后序遍历的顺序
总结：后序遍历遵循左子树->右子树->根节点的顺序来访问结点
5.层序遍历
定义：若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问
二叉树的层序遍历顺序图示
总结：层序遍历遵循层级递增，同层级中从左至右的顺序访问结点
6.算法：使用前序遍历，建立二叉树并进行遍历，输出各个结点的层次
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
Status createBiTree(BiTree *T){
//接收输入
ElemType c = 0;
scanf("%c",&c);
if ( c == ' ') {
//输入空格便是结束这棵子树
*T = NULL;
return ERROR;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T) -> data = c;
//递归创建
//创建左子树
createBiTree(&((*T)->lchild));
//创建右子树
createBiTree(&((*T)->rchild));
return OK;
}
}
//访问二叉树结点的具体操作
void visit(ElemType c,int level){
printf("data:%c,level:%d",c,level);
}
//前序遍历
Status preOrderTraverse(BiTree T,int level){
if ( !T ) {
return ERROR;
}
visit(T->data, level);
//递归遍历
preOrderTraverse(T->lchild, level+1);
preOrderTraverse(T->rchild, level+1);
return OK;
}
int main(){
int level = 1;
BiTree T = NULL;
createBiTree(&T);
preOrderTraverse(T, level);
return 0;
}
7.二叉树的前序、中序、后序遍历的递归与非递归实现
二叉树遍历的非递归实现需要借助栈来实现(由于栈LIFO的特性)，我们先建立一个树的结点栈，如下所示:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTreeStack{
BiTNode *base;//栈底
BiTNode *top;//栈顶
int stackSize;
}BiTreeStack;
Status initStack(BiTreeStack *s){
s->base = (BiTNode *)malloc(sizeof(BiTNode) * STACK_INIT_SIZE);
if (!s->base) {
return ERROR;
}
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
return OK;
}
Status Push(BiTreeStack *s,BiTNode node){
if (s->top - s->base >= s->stackSize) {
s->base = (BiTNode *)realloc(s->base, sizeof(BiTNode)*(s->stackSize + STACKINCREMENT));
if (!s->base) {
return ERROR;
}
s->top = s->base + s->stackSize;
s->stackSize += STACKINCREMENT;
}
*(s->top) = node;
(s->top)++;
return OK;
}
Status Pop(BiTreeStack *s,BiTNode *node){
if (s->top - s->base == 0) {
return ERROR;
}
*node = *(--(s->top));
return OK;
}
int StackLength(BiTreeStack *s){
return (int)(s->top - s->base);
}
void visitNode(BiTree node){
printf("data:%c",node->data);
}
前序遍历
前序遍历的递归实现比较简单，遵循根节点-左子树-右子树的顺序即可
//递归
Status PreorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
visitNode(T);
PreorderTraversalRecursive(T->lchild);
PreorderTraversalRecursive(T->rchild);
return OK;
}
非递归实现我们需要创建一个栈，先把二叉树的根节点压入栈，访问后，再依次压入右结点，再压入左结点，这样访问的时候就遵循了根节点-左子树-右子树的顺序
//非递归
Status PreorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode node = *T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
Push(stack, node);
while (StackLength(stack) != 0) {
Pop(stack, &node);
visitNode(&node);
//先把右子树根节点压入栈
if (node.rchild) {
Push(stack, *(node.rchild));
}
//再把左子树根节点压入栈
if (node.lchild) {
Push(stack, *(node.lchild));
}
}
return OK;
}
中序遍历
中序遍历的递归实现比较简单，遵循左子树-根节点-右子树的顺序即可
//递归
Status InorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
InorderTraversalRecursive(T->lchild);
visitNode(T);
InorderTraversalRecursive(T->rchild);
return OK;
}
中序遍历的非递归实现稍微麻烦一点，我们需要先从根节点出发，逐个将左子树压入栈，由于我们知道叶子结点是没有子树的，那么我每次每次访问的就当做是根节点，我们判断它是否有右子树，有右子树的话，就重复之前步骤，将左子树依次加入到栈中，这样也就遵循了中序遍历左子树-根节点-右子树的顺序
//非递归
Status InorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode *p = T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
//将左子树都压入栈
while (p) {
Push(stack, *p);
p = p->lchild;
}
//开始遍历
while (StackLength(stack)) {
//每一个出栈的结点我们都当做根节点
Pop(stack, p);
visitNode(p);
//判断有无右子树
if (p->rchild) {
p = p->rchild;
Push(stack, *p);
while (p->lchild) {
p = p->lchild;
Push(stack, *p);
}
}
}
return OK;
}
后序遍历
后序遍历的递归实现也比较简单，遵循左子树-右子树-根节点的顺序即可
//递归
Status PostorderTraversalRecursive(BiTree T){
if (!T) {
return ERROR;
}
PostorderTraversalRecursive(T->lchild);
PostorderTraversalRecursive(T->rchild);
visitNode(T);
return OK;
}
后序遍历的非递归实现看上去是最麻烦的，不过我们仍然可以用按照后序遍历左子树-右子树-根节点的思路来进行思考：
- 对于每一个结点，如果它是非叶子结点，且它的左孩子和右孩子都不是上一次访问的结点的情况下，循环将它的左子树压入栈，这样就确定了访问的顺序
- 将栈顶结点推出，判断结点是否有右孩子且右孩子不是之前访问的结点的情况下，将右孩子压入栈
- 栈顶结点推出，不符合2的条件下，访问结点，并存储新访问结点的指针，然后将出栈新节点有用于比较
//非递归
Status PostorderTraversalNotRecursive(BiTree T){
if (!T) {
return ERROR;
}
BiTNode *p = T;
//记录上一次访问的结点
BiTNode *pre = T;
BiTreeStack s;
BiTreeStack *stack = NULL;
initStack(&s);
stack = &s;
while(p || StackLength(stack)){
if(p != NULL && pre != p->lchild && pre != p->rchild){ //结点不为空且左孩子和右孩子都不是上一次访问的,入栈左子树
Push(stack, *p);
p = p->lchild;
}
else{
Pop(stack, p);
if(p->rchild != NULL && pre != p->rchild){ //右子树不为空且右孩子没有访问过，入栈右子树结点
Push(stack, *p);
p = p->rchild;
Push(stack, *p);
}
else{
//访问到最后的右子树的结点后，退栈
visitNode(p);
pre = p;
Pop(stack, p);
}
}
}
return OK;
}
网友评论