当前位置:首页 > C++知识 > 正文内容

树的遍历

亿万年的星光3年前 (2021-11-27)C++知识18818

在应用树结构解决问题时,往往要求按照某种此项获得树中全部结点的信息,这种操作叫做树的遍历。遍历的方法有很多种。常用的有:

A. 先序遍历:先访问根结点,再从左到右按照先序思想遍历各子树。

B. 后序遍历:先从左到右遍历各个子树,再访问根结点。

C.层次遍历:按层次从小到大逐个访问,同一层次按照从左到右的次序。

D.叶结点遍历:有时把所有的数据信息都存放叶结点中,而其余结点都是用来表示数据之间的某种分支或层次关系,这种情况就用这种方法。


A,B用的思想就是我们常说的“深度优先遍历”

void tral(tree t,int m)
{
    if(t)
    {
        cout<<t->data<<endl;
        for(int i=0;i<m;i++){
            tral(t->child[i],m);
        }
    }

}


C方法实际上就是我们常说的“广度优先搜索”思想如下:若某个结点别访问,则该结点的子结点应记录,等待被访问。顺序访问各层次上结点,直至不再有未访问过的结点,为此,引入一个队列来存储等待访问的子结点,设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下:

const int n=100;
int head,tail,i;
tree q[n];
tree p;
void work()
{
    tail=head=1;
    q[tail]=t;
    tail++; //队尾为空
    while(head<tail){
        p=q[head]
        head++;
        cout<<p->data<<" ";
        for(i=0;i<m;i++)
        if(p->child[d])
        {
            q[tail]=p—>child[i];
            tail++;
        }
    }
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

C++整型的数据范围

数据类型标识符占字节数数值范围数值范围短整型short [int]2(16位)-32768~32767-2^15 到2^15  -1整型[long] int4(32位)-...

【题解】采药的最短路径

【题目描述】少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有...

最小生成树(1)

最小生成树(1)

一、定义一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出...

如何估算时间复杂度

首先:  常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n^2)<Ο(n^3)<…<Ο(2^n)<Ο(n!)时间复杂度可以简单理解为最多执...

【算法】前缀和与差分(3)二维数组前缀和

【算法】前缀和与差分(3)二维数组前缀和

0.前言前面的一篇文章,介绍了一维数组的前缀和,这篇文章中,介绍一下二维数组的前缀和1.定义二维数组的前缀和就是按照二维数组求和。公式如下:那二维前缀和中一个f[i][j]表示的意思就是以(1,1)为...

【题解】士兵训练

【题目描述】某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,...