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

这篇具有很好参考价值的文章主要介绍了数据结构—基础知识(11):二叉树的遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,进而便于遍历。
由二叉树的递归定义可知,遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法,其中“序”指的是根结点在何时被访问。
数据结构—基础知识(11):二叉树的遍历,数据结构基础知识、概念,数据结构,笔记,经验分享,考研

先序遍历: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);//访问根结点
        }
    }
    

    后序遍历的非递归算法:文章来源地址https://www.toymoban.com/news/detail-827589.html

    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
    }
    

到了这里,关于数据结构—基础知识(11):二叉树的遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)
  • 数据结构--基础知识

    数据结构是计算机科学中研究数据组织、存储和管理的方法和原则。它涉及存储和操作数据的方式,以便能够高效地使用和访问数据。 数组(Array):数组是一种线性数据结构,由相同类型的元素按顺序排列而成。数组具有固定长度,在内存中占据连续的位置。可以通过索引

    2024年02月14日
    浏览(46)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(46)
  • 数据结构基础知识、名词概述

    整体知识框架 1.1.1 数据、 数据元素、 数据项和数据对象 数据 (Data) 是客观事物的符号表示,是所有 能输入到计算机中并被计算机程序处理的符号 的总称 。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、 图像、声音及动画等通过特殊编

    2024年02月15日
    浏览(53)
  • 数据结构—基础知识:哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月21日
    浏览(47)
  • 【数据结构】树的基础知识及三种存储结构

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 把它叫做树是因为它

    2024年02月09日
    浏览(50)
  • 数据结构—基础知识(15):哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月19日
    浏览(48)
  • 【数据结构】C--单链表(小白入门基础知识)

    前段时间写了一篇关于顺序表的博客,http://t.csdn.cn/0gCRp 顺序表在某些时候存在着一些不可避免的缺点: 问题: 1. 中间 / 头部的插入删除,时间复杂度为 O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈 2 倍的增长,势必会有一定的空间

    2024年02月16日
    浏览(51)
  • 【数据结构】栈和队列(栈的基本操作和基础知识)

    🌈个人主页: 秦jh__ https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》 https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 目录  前言 栈 栈的概念和结构 栈的实现 ​编辑 数组栈的实现 总的声明 初始化  插入 删除 取栈顶元素 销毁 判断是否为空

    2024年02月03日
    浏览(54)
  • 【数据结构】—— 队列基础知识以及数组模拟队列的分析、演示及优化

    ❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️ 🧑个人主页:@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力 感谢! 📕该篇文章收录专栏—数据结构 目录 什么是队列? 数组模拟队列 分析 存入队列的步骤 使用数组模拟队列—

    2024年01月19日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包