数据结构—基础知识(11):二叉树的遍历

发布时间:2024年01月24日

数据结构—基础知识(11):二叉树的遍历

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,进而便于遍历。
由二叉树的递归定义可知,遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法,其中“序”指的是根结点在何时被访问。
在这里插入图片描述

先序遍历:ABCDEFGH
中序遍历:BDCEAFHG
后序遍历:DECBHGFA

  1. 先序遍历

    先序遍历的操作过程如下:

    若二叉树为空则什么都不做;否则,①访问根节点;②先序遍历左子树;③先序遍历右子树。

    对应的递归算法:

    void PreOrder(BinTree T)
    {//先序遍历的递归算法
        if(T!=NULL)
        {
            visit(T);//访问根结点
            PreOrder(T->lchild);//递归遍历左子树
            PreOrder(T->rchild);//递归遍历右子树
        }
    }
    

    先序遍历的非递归算法:

    void PreOrder2(BinTree T)
    {//先序遍历的非递归算法
        InitStack(S);BiTree p=T;//初始化栈S;p是遍历指针
        while(p||!IsEmpty(S))//栈不空或p不空时循环
        {
            if(p){//一路向左
                visit(p);Push(S,p);//访问当前结点,并入栈
                p=p->lchild;//左孩子不空,一直向左走
            }
            else{//出栈,并转向出栈结点的右子树
                Pop(S,p);//栈顶元素出栈
                p=p->rchild;//向右子树走,p赋值为当前结点的右子树
            }//返回while循环继续进入if-else语句
        }
    }
    
  2. 中序遍历

    中序遍历的操作过程如下:

    若二叉树为空则什么都不做;否则,①先序遍历左子树;②访问根节点;③先序遍历右子树。

    对应的递归算法:

    void InOrder(BinTree T)
    {//中序遍历的递归算法
        if(T!=NULL)
        {
            InOrder(T->lchild);//递归遍历左子树
            visit(T);//访问根结点
            InOrder(T->rchild);//递归遍历右子树
        }
    }
    

    中序非递归遍历

    void InOrder2(BiTree T)
    {
        InitStack(S); BiTree p=T;//初始化栈S;p是遍历指针
        while(p||!IsEmpty(S))//栈不空或p不空时循环
        {
            if(p){//一路向左
                Push(S,p);//当前结点入栈
                p=p->1child;//左孩子不空,一直向左走
            } 
            else{//出栈,并转向出栈结点的右子树
                Pop(S,p);visit(p);//栈顶元素出栈,访问出栈结点
                p=p->rchild;//向右子树走,p赋值为当前结点的右孩子
            }//返回 while 循环继续进入if-else语句
        }
    }
    
    
  3. 后序遍历

    后序遍历的操作过程如下:

    若二叉树为空则什么都不做;否则,①先序遍历左子树;②先序遍历右子树;③访问根节点。

    对应的递归算法:

    void PostOrder(BinTree T)
    {//后序遍历的递归算法
        if(T!=NULL)
        {
            PostOrder(T->lchild);//递归遍历左子树
            PostOrder(T->rchild);//递归遍历右子树
            visit(T);//访问根结点
        }
    }
    

    后序遍历的非递归算法:

    void PostOrder (BiTree T)
    {
        InitStack(S);
        BiTNode *p=T;
        BiTNode *r=NULL;
        while(p||!IsEmpty(S))
        {
            if(p){//走到最左边
                push(S,p);
                p=p->lchild;
            }
            else{//向右
                GetTop(S,p);//读栈顶结点(非出栈)
                if(p->rchild&&p->rchild!=r)//若右子树存在,且未被访问过
                    p=p->rchild;//转向右
                else{//否则,弹出结点并访问
                    pop(S,p);//将结点弹出
                    visit(p->data);//访问该结点
                    r=p;//记录最近访问过的结点
                    p=NULL;//结点访问完后,重置p指针
                }
            }//else
        }//while
    }
    
文章来源:https://blog.csdn.net/qq_42257631/article/details/135776587
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。