遍历二叉树详细笔记-EW帮帮网

遍历二叉树

1、定义

（1）遍历的定义
顺着某一条搜索路径巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称为周游）。
注意：“访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值，但要求这种访问不破坏原来的数据结构。

（2）遍历目的：得到树中所有结点的一个线性排列。

（3）遍历方法：若规定先左后右，则只有三种情况：
①DLR——先（根）序遍历；（根左右）
②LDR——中（根）序遍历；（左根右）
③LRD——后（根）序遍历。（左右根）
在这里插入图片描述
由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。

（4）遍历算法的分析
时间效率：O(n)，每个结点只访问一次。
空间效率：O(n)，栈占用的最大辅助空间。

2、先序遍历二叉树

（1）操作定义

若二叉树为空，则空操作；
否则：①访问根结点；②先序遍历左子树；③先序遍历右子树。

（2）算法实现
①代码

Status PerOrderTraverse(BiTree T){
    if(T==NULL) return OK;//空二叉树
    else{
        vist(T);//访问根结点；例如，输出根结点的值cout<<T->date;
        PerOrderTraverse(T->lchild);//递归遍历左子树
        PerOrderTraverse(T->rchild);//递归遍历右子树
    }
}

②递归过程分析
在这里插入图片描述

上述递归中当T为空时，返回到上一层，若上一层没有执行完完整的“根左右”的遍历则继续进行遍历直到T再次为空；若上一层执行完了完整的先序遍历过程则继续返回上一层，直到返回到未执行完毕的部分或者返回到最前面的一层全部执行完毕，则递归程序结束。
递归大概过程（以本题为例）：程序进行到递归时就开始不断调用pre函数直到参数T为空，当参数T为空时，返回到上一层递归调用中继续执行主程序中递归语句后面的语句（即pre(T->lchild);后面的pre(T->rchild)语句），当这个语句执行完后再次返回上一层，重复上述操作直至参数T回到最初的值（即回到第一层递归中，如上图中T回到T指向A结点的时候）。注意：结束整个递归是要在T为最初值时主程序中递归语句后面的语句也执行完毕即整个程序执行完毕。
返回：指的是返回到递归的上一层，如图中第一次返回，返回的是T->L。

3、中序遍历二叉树

（1）操作定义

若二叉树为空，则空操作；
否则：①中序遍历左子树；②访问根结点；③中序遍历右子树。

（2）算法实现

Status InOrderTraverse(BiTree T){
    if(T==NULL) return OK;
    else{
        InOrderTraverse(T->lchild);//递归遍历左子树
        vist(T);//访问根结点
        InOrderTraverse(T->rchild);//递归遍历右子树
}
}

4、后序遍历二叉树

（1）操作定义

若二叉树为空，则空操作；
否则：①后序遍历左子树；②后序遍历右子树；③访问根结点。

（2）算法实现

Status PostOrderTraverse(BiTree T){
    if(T==NULL) return OK;
    else{
       PostOrderTraverse(T->lchild);//递归遍历左子树
       PostOrderTraverse(T->rchild);//递归遍历右子树
       vist(T);//访问根结点
}
}

5、遍历二叉树的非递归算法

（1）中序遍历非递归算法

①二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树，如何找到该结点的根以及右子树。

②基本思想：建立一个栈；根结点进栈，遍历左子树；根结点出栈，输出根结点，遍历右子树。即先入栈再访问再出栈。

③算法实现

Status InOrderTraverse(BiTree T){
    BiTree p;
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S)){
        if(p){Push(S,p);p=p->lchild;}
        else{
            Pop(S,q);
            printf("%c",q->date);//即访问根结点，可以不是打印
            p=q->rchild;}
}
    return OK;
}

上述代码结束循环的条件：p为空，且S为空。因此要考虑两个条件，一个是p一个是S。刚开始时栈S为空、p不为空，循环要继续进行，而结束时如上图中p指向C的右孩子时p为空但是循环还不能结束因为A还没有访问，此时S不为空还有A元素，因此当p为空时要考虑S算法也为空以确保二叉树的结点都访问完成。

注意：StackEmpty(S)表示如果S为空则返回True（1），否则返回False（0）。

（2）先序遍历非递归访问
①先序遍历非递归访问，使用栈即可实现。先序遍历的非递归访问在所有的遍历中算是最简单的了。主要思想就是先将根结点压入栈，然后根结点出栈并访问根结点，而后依次将根结点的右孩子、左孩子入栈（不要记反了），直到栈为空为止。
②算法实现

void preOrderIter(struct node* root)
{
    if(root==NULL) return;
    strack<struct node*>s;
    s.push(root);
    while(!s.empty()){
        struct node *nd=s.top();
        cout<<nd->date<<" ";
        s.pop();
        if(nd->right!=NULL)
            s.push(nd->right);
        if(nd->left!=NULL)
            s.push(nd->left);
    }
    cout<<endl;
}

（3）后序遍历非递归访问

①后序遍历的非递归算法较复杂，使用一个栈可以实现，但是过程很繁琐，这里可以巧妙的用两个栈来实现后序遍历的非递归算法。注意到后序遍历可以看作是下面遍历的逆过程：即先遍历某个结点，然后遍历其右孩子，然后遍历其左孩子。这个过程逆过来就是后序遍历。算法步骤如下：

Push根结点到第一个栈s中。
从第一个栈s中Pop出一个结点，并将其Push到第二个栈output中。
然后Push结点的左孩子和右孩子到第一个栈s中。
重复过程2和3直到栈s为空。
完成后，所有结点已经Push到栈output中，且按照后序遍历的顺序存放，直接全部Pop出来即是二叉树后序遍历结果。

②算法实现

void postOrderIter(struct node *root)
{
    if(!root) return;
    strack<struct node*>s,output;
    s.push(root);
    while(!s.empty()){
        struct node *curr=s.top();
        output.push(curr);
        s.pop();
        if(curr->left)
            s.push(curr->left);
        if(curr->right)
            s.push(curr->right);
    }
    while(!output.empty()){
        cout<<output.top()->date<<" ";
        output.pop();
    }
    cout<<endl;
}

本文含有隐藏内容，请开通VIP 后查看

遍历二叉树详细笔记