精华内容
下载资源
问答
  • 树的后根遍历相当于
    千次阅读
    2021-03-15 16:32:49

    DFS递归实现与树的先序遍历递归实现的相似处

    在考研复习时复习到图的深度遍历时,参考书中有一句话———图的DFS遍历类似于树的先序遍历,书中给的DFS遍历是以递归方式实现的,于是作者贴出了树的先序遍历的递归代码让读者互相比较,确实可以看出一些相似之处,那就是二者算法思想其实都是,先访问根结点(图中是DFS遍历的起始点),然后递归处理它们的“子部分”,图中的“子部分”指的是这个顶点的其余邻接点,树中的这个“子部分”则是结点的左右子树。

    DFS非递归遍历与树的先序遍历非递归实现的相似处

    通过对两种算法的递归实现从而找到其相似之处或许有些困难,那么就让我们比较这两种遍历的非递归实现代码,看看能否使我们更清晰的找出二者的相似之处

    以下是DFS遍历的非递归实现代码

    void DFSfei(AGraph* p,int v,int visit[maxsize])
    {
        Arcnode *q=NULL;//用来记录某个顶点的邻接点
        int stack[maxsize],top=-1,k;//k用来记录栈顶元素
        stack[++top]=v;
        visit[v]=1;
        visit(v);
        while(top!=-1)
        {
            k=stack[top];
            q=p->adjlist[k].first;
            while(q!=NULL&&q->adjvex==1)//找q的第一个没被访问过的邻接点,若找不到则因q为NULL退出,证明与q相连的边已处理完毕
            {
                q=q->next;
            }
            if(q==NULL)
            {
                top--;
            }
            else
            {
                stack[++top]=q;
                visit(q->adjvex);
                visit[q->adjvex]=1;
            }
            
        }
    }
    

    以下是树的先序遍历非递归实现代码

    void xianxu(BTnode *tree)
    {
        if(tree)
        {
        BTnode * stack[maxsize],p=NULL;
        int top=-1;
        stack[++top]=tree;
        while(top!=-1)
        {
            p=stack[top--];
            visit(p);//访问某个节点
            if(p->rchild!=NULL)
            {
                stack[++top]=p->rchild;
            }
            if(p->lchild!=NULL)
            {
                stack[++top]=p->lchild;
            }
        }
        }
    }
    

    通过上面的比较可以说很清晰了,二者的算法流程近乎相同,那就是根节点入栈(起始节点入栈)➡️依次出栈一个元素,出栈时并访问,然后检查左右子树(邻接点)是否存在,存在则依次入栈➡️重复第二步直到栈空。

    更多相关内容
  • 文章目录[总结] 二叉树、、森林三者遍历...从左到右对森林中的每一棵进行【先根遍历】 中序遍历 第二次经过结点的时候访问 的度不一定,一般不说中序遍历,但非要谈,请看下面的分析 森林的中序、后序,只...

    原文链接:https://www.yuque.com/cppdev/algo/eq0fve

    [总结] 二叉树、树、森林三者遍历比较

    【三种遍历方法对比】

    二叉树森林
    先序遍历第一次经过该结点就访问根访问在前,先访问根结点,后访问其他结点从左到右对森林中的每一棵树进行【先根遍历】
    中序遍历第二次经过结点的时候访问树的度不一定,一般不说中序遍历,但非要谈,那就是第二次经过该结点时进行访问森林的中序、后序,只是许多地方说法不一样,实则是一个东西
    后序遍历第三次经过结点的时间访问先遍历子树,再访问根结点(先访问子树是空的结点)从左到右对森林中的每一棵树进行【后根遍历】

    【树、森林用二叉链表的形式存储(二叉链表的形式)时,其遍历对应着二叉树的遍历方式是什么?】

    • 若树是用二叉链表的形式存储,那么树的后根遍历,即可对该二叉链表进行中序遍历即可
    森林树、森林用二叉链表的形式存储(孩子兄弟表示法)
    先根遍历先序遍历先序遍历
    后根遍历中序遍历、后序遍历中序遍历

    树的中序遍历问题

    【二叉树的中序遍历】二叉树遍历的时候都一共有三次经过结点,第二次经过时就是中序遍历(因为度为2,所以有中序遍历)

    【树的中序遍历问题】树的度不一定,一般不说中序遍历
    在这里插入图片描述

    展开全文
  • 解题 来解题 这题 其实用试的是很快的~ 还是用这个例子 【1】普通的后序遍历 后序遍历 左右中(左 )—— 翻译得详细些就是—— 最开始 遍历到(还有左子树的)最深处的节点 【1】先访问该节点的左子树 2...

    一棵树的后序遍历和这棵树对应的二叉树的()相同。
    A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历

    嗯 就这么道题

    拆分下题目就是
    一棵树的后序遍历 == 这棵树拆成二叉树的中序遍历
    下面来解题

    1.解题

    来解题
    这题
    其实用试的是很快的~
    还是用这个例子

    【1】普通树的后序遍历

    在这里插入图片描述

    后序遍历 左右中(左后 右后 根)—— 翻译得详细些就是——

    最开始 遍历到(还有左子树的)最深处的节点

    【1】先访问该节点的左子树

    2

    【2】然后访问其余子树(以同样规则访问其余子树—先左后其他)

    56 3 - 4

    【3】最后访问根

    1

    得到结果 2 5634 1

    【2】二叉树的中序遍历

    在这里插入图片描述

    最开始 遍历到(还有左子树的)最深处的节点

    【1】先访问该节点的左子树

    2

    【2】访问该左子树的右子树

    56 3 4

    【3】最后访问根
    1

    同样得到结果 2 5634 1

    一棵树的后序遍历和这棵树对应的二叉树的(B)相同。
    A.先序遍历 B.中序遍历 C.后序遍历 > D.层次遍历

    好的我得到答案了(逃)

    2.更省空间的二叉树表示法

    下面来看看为啥二叉树更节省空间~

    一天一个小知识:二叉树表示法(即左孩子右兄弟表示法)更加节省空间
    (下面解释了 为啥这个表示法叫“左孩子右兄弟表示法~”)
    为啥?
    三叉树中每个节点都存储3个指针域(因为是三叉树嘛 时刻准备着连三个孩子)
    造成有效指针域(指向明确节点的)非常少!
    在这里插入图片描述
    像这个三叉树就有6*3个指针域 但是有效指针域只有5个 浪费13个。

    做个转换
    二叉树
    在这里插入图片描述
    是的 普通树到二叉树的转换就是那么简单
    保留所有左子树的结构 之前是兄弟的 变成右儿子就好了
    咳咳接下来来看看二叉树的效率
    6*2个指针域 同样是5个的有效指针域 浪费了7个指针域。
    很明显 比多叉树要香嘛!!

    其中k元n叉树中的k和n越大 转换成二叉树越省空间!
    n元k叉树浪费的空间——kn -(n-1)
    n元2叉树浪费的空间——2n - (n-1)

    展开全文
  • 二叉树先根、中根、后根遍历

    万次阅读 多人点赞 2017-10-14 17:39:19
    二叉树先根、中根、后根遍历根遍历: ABCDEFGH 中根遍历:CBEDFAGH 后根遍历 : CEFDBHGA

    二叉树先根、中根、后根遍历




    先根遍历: ABCDEFGH


    中根遍历:CBEDFAGH


    后根遍历 : CEFDBHGA




    展开全文
  • 2.后根遍历(若非空) 先依次访问根结点的每棵子树,再访问根结点。遍历的时候也需要遵循先子树根的规则。相当于二叉树的后序遍历。 举个例子 经常有小伙伴搞不清为什么的遍历和二叉树遍历的区别。其实...
  • 与二叉树的转换与遍历

    多人点赞 热门讨论 2021-10-22 08:52:51
    、森林与二叉树之间有一个自然的对应关系,即任何一棵或一个森林都可唯一地对应于一棵二叉树,而任何一棵二叉树也能唯一地对应于一个森林或一棵。 话不多说,就让我们抓紧开始吧~ 今日学习目标: 把“与...
  • 1. 遍历简介:作为非线性数据结构,在我们取出数据时就需要设计遍历,所谓遍历,就是按照一定的规则性,将数据结构中的所有数据全部依次访问,而二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点...
  • 与二叉树的转换、遍历

    万次阅读 2017-05-05 16:08:08
    和二叉树不同,可以有0到n个孩子,所以实现起来很麻烦,但我们可以借助的孩子兄弟表示法把转换成二叉树。 在孩子兄弟表示法中,某个结点的第一个孩子结点的指针是二叉树中其左孩子结点指针,右兄弟结点指针是...
  • java 的各种遍历

    千次阅读 2020-07-04 21:42:25
    是一个有n个有限节点组成一个具有层次关系的集合,每个节点有0个或者多个子节点,没有父节点的节点称为节点,也就是说除了节点以外每个节点都有父节点,并且有且只有一个。 的种类比较多,有二叉树,红黑...
  • 数和二叉树的转化2、后根遍历3、层序遍历(广度优先遍历)二、森林的遍历1、先序遍历1.**对的先序遍历 等同 依次对各个进行先根遍历**2.将森林和二叉树的先序遍历是一样的2、中序遍历1.对森林的中序遍历 等同...
  • //将节点加入字符串,相当于树的后续遍历架构 post += pre[idx]; return post; } int main() { cin >> in >> pre; //节点在前序中的下标,中序序列的左右端点 cout (0, 0, in.size() - 1) ; ...
  • js前端算法--- 深度优先遍历 广度优先遍历 实现
  • 通过比较二叉树的先根遍历,中根遍历后根遍历的非递归算法可以发现:这三个算法的实现是极其相似的(如同它们递归算法的也很相似一般)。 1:都用到了栈来暂存节点。 2:都是两个while的嵌套循环。 ...
  • 、森林与其对应的二叉树的遍历方法的对应关系

    万次阅读 多人点赞 2018-05-04 20:04:48
    给定一棵,可以找到唯一一棵二叉树与之对应,同样,森林也与一棵存在一一对应关系。与二叉树,森林与二叉树的转化如下图所示,(a)(b)(c)为三棵树,并构成一个森林,(d)(e)(f)分别为(a...先根遍历...
  • 二叉树的遍历——层次遍历

    千次阅读 2019-10-13 20:10:19
    这个过程和BFS很像,因为BFS进行搜索总是以广度作为第一关键词,而对应到二叉树中广度又恰好体现在层次上,因此层次遍历相当于是对二叉树从结点开始的广度优先搜索,基本思路如下: ①将结点ro...
  • Python 遍历

    千次阅读 2020-12-06 15:03:20
    二叉树的遍历 递归和非递归实现 N叉遍历实现
  • 的孩子兄弟表示法和二叉树的二叉链表示法可以看出,的孩子兄弟表示法实质上是二叉树的二叉链表存储形式,第一个孩子指针和有兄弟指针分别相当于二叉链表的左孩子指针和右孩子指针。所以从物理结构上看,的右...
  • 二叉树的遍历 二叉树的遍历分为两类,一类是深度优先遍历,一类是广度优先遍历。 左孩子结点一定要在右孩子结点之前访问。 深度优先遍历 二叉树的深度优先遍历方式有三种,先根(序)遍历、中根(序)...1、先根遍历
  • 遍历递归算法

    2020-05-02 15:27:06
    (1) 的先序遍历算法: 代码: Status PreOrderTraverseTree(GenTree tree, void (*Visit)(TElemType data)){ if(!tree) return OK; Visit(tree->data); //访问结点 for(i = 0; i < MAX_DEGR...
  • 文章目录一、二叉树的中序遍历1、递归法(推荐)2、迭代法(了解)---中序遍历3、迭代法(了解)---前序遍历4、迭代法(了解)---后序遍历二、N叉遍历1、递归法2、迭代法三、N叉的层序遍历 一、二叉树的中序...
  • 广度优先搜刮是从结点入手下手沿着的宽度搜刮遍历,也就是按条理的去遍历;从上往下对每一层顺次接见,在每一层中,从左往右(也能够从右往左)接见结点,接见完一层就进入下一层,直到没有结点能够接见为止。 ...
  • 和森林的遍历

    千次阅读 多人点赞 2019-03-14 08:30:25
    和森林的遍历 ...2、根(后序)遍历:即先依次后根遍历根的每棵子树,然后访问根结点 3、另外还有一种层序遍历,这种遍历就是自上向下,自左向右按层次进行遍历即可 根据上面的两种遍历定义可得上图...
  • 遍历【PTA】

    2021-11-01 12:45:51
    第二行给出其遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。 输出格式: 在一行中输出该的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。 输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7...
  • java实现红黑及其各种遍历方式

    千次阅读 2020-10-20 14:05:50
    红黑的性质 1.节点是红色或黑色 2.节点是黑色 3.所有叶子都是黑色。(叶子是NUIL节点) 4.每个红色节点的两个子节点都是黑色。(从每个叶子到的所有路径上不能有两个连续的红色节点) 5.从...
  • 1) 有一个特殊的节点,成为节点,节点没有前驱节点 2)除根节点外,其余节点被分为n个互不相交的集合,每个集合又类似一个 3)是递归定义的 概念 节点的度:一个节点含有的子树的个数称为该节点的度 的度...
  • 的三种遍历方式

    2021-09-03 16:19:01
    其中遍历子树的时候,子树的遍历方式也是按大树的遍历方式来进行的,比如我采用前序遍历遍历顺序是左右,那么我每颗子树遍历节点的时候也是按照父亲-左-右这种方式来遍历,如下图 前序遍历:ABDGHCEIF 可以看到...
  • 遍历看DFS和BFS

    2020-02-07 16:02:55
    1.深度优先搜索(DFS)与先根遍历 (1)对所有DFS求解过程,都可以把它画成树的形式,此时搜索时的死...(2)对的DFS遍历过程就是的先根遍历过程(先访问根节点,再从左至右依次访问所有子树) 2.广度优先搜...
  • 转自:的深度优先遍历需要用到额外的数据结构--->栈;而广度优先遍历需要队列来辅助;这里以二叉树为例来实现。importjava.util.ArrayDeque;public classBinaryTree {static classTreeNode{intvalue;TreeNode ...
  • 形结构是一类重要的非线性数据结构,其中以和二叉树最为常用。二叉树的链式存储结构是一类重要的数据结构。 二叉树是每个结点最多只有两个子树的有序。二叉树常被用作二叉查找和二叉堆或是二叉排序。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,760
精华内容 20,304
关键字:

树的后根遍历相当于