精华内容
下载资源
问答
  • 对一棵二叉树进行层次遍历
    2020-12-20 11:20:22

    满意答案

    根据 层次遍历序列ABCDEFG, 中序遍历序列BAFGDCE, 得到的二叉树是:

    A

    /  \

    B    C

    / \

    D   E

    /

    F

    \

    G

    先序遍历序列: ABCDFGE

    中序遍历序列: BAFGDCE

    后序遍历序列: BGFDECA

    层次遍历序列: ABCDEFG

    如果是如下形状的二叉树,则

    层次遍历序列仍然是ABCDEFG,但是,中序遍历序列是BAFDGCE (D,F,G的结构不同了)

    A

    /  \

    B    C

    / \

    D   E

    / \

    F   G

    // C代码测试程序

    // 输入先序扩展序列: AB##CDF#G###E##

    // 输出4种遍历结果

    // 先序遍历序列: ABCDFGE

    // 中序遍历序列: BAFGDCE

    // 后序遍历序列: BGFDECA

    // 层次遍历序列: ABCDEFG

    //

    // 二叉树示意图:

    //     A

    //   /  \

    //  B    C

    //      / \

    //     D   E

    //    /

    //   F

    //    \

    //     G

    //

    #include 

    #include 

    #define OK 1

    #define OVERFLOW -2

    typedef int Status;

    typedef char TElemType;

    typedef int bool;

    typedef struct BiTNode

    {

    TElemType data;

    struct BiTNode *lchild;

    struct BiTNode *rchild;

    }BiTNode, *BiTree;

    typedef BiTNode * QElemType;

    typedef struct QNode

    {

    QElemType data;

    struct QNode * next;

    }QNode, *QueuePtr;

    typedef struct

    {

    QueuePtr front;

    QueuePtr rear;

    }LinkQueue;

    Status InitQueue_L(LinkQueue *Q)

    {

    (*Q).front = (QueuePtr) malloc (sizeof(QNode));

    if ((*Q).front == NULL)

    return OVERFLOW;

    (*Q).front->next = NULL;

    (*Q).rear = (*Q).front;

    return OK;

    }

    bool QueueEmpty_L(LinkQueue Q)

    {

    return (Q.front == Q.rear);

    }

    Status EnQueue_L(LinkQueue *Q, QElemType e)

    {

    QNode *s = (QNode *) malloc (sizeof(QNode));

    s->data = e;

    s->next = NULL;

    (*Q).rear->next = s;

    (*Q).rear = s;

    return OK;

    }

    Status DeQueue_L(LinkQueue *Q)

    {

    QNode *q = (*Q).front->next;

    (*Q).front->next = q->next;

    if (q->next == NULL)

    (*Q).rear = (*Q).front;

    free(q);

    return OK;

    }

    //创建二叉树: 先序扩展序列 + 递归法

    void CreateBiTree(BiTree *T)

    {

    char input;

    scanf("%c",&input); //输入数据

    if(input == '#')    //'#'是空节点

    {

    *T = NULL;

    }

    else

    {

    *T=(BiTree)malloc(sizeof(BiTNode));

    if(*T == NULL)

    {

    printf("\n分配动态内存时出错.\n");

    exit(1);

    }

    (*T)->data=input;

    CreateBiTree(&((*T)->lchild));

    CreateBiTree(&((*T)->rchild));

    }

    }

    void PreOrder(BiTree T) //先序遍历

    {

    if(T != NULL)

    {

    printf("%c",T->data);

    PreOrder(T->lchild);

    PreOrder(T->rchild);

    }

    }

    void InOrder(BiTree T) //中序遍历

    {

    if(T != NULL)

    {

    InOrder(T->lchild);

    printf("%c",T->data);

    InOrder(T->rchild);

    }

    }

    void PostOrder(BiTree T) //后序遍历

    {

    if(T != NULL)

    {

    PostOrder(T->lchild);

    PostOrder(T->rchild);

    printf("%c",T->data);

    }

    }

    void LevelOrder(BiTree T) //层序遍历

    {

    LinkQueue Q;

    BiTree p = T;

    if(p == NULL)

    {

    return;

    }

    InitQueue_L(&Q);

    EnQueue_L(&Q, p);

    while( !QueueEmpty_L(Q) )

    {

    p = Q.front->next->data;

    DeQueue_L(&Q);

    printf("%c",p->data);

    if(p->lchild != NULL)

    {

    EnQueue_L(&Q, p->lchild);

    }

    if(p->rchild != NULL)

    {

    EnQueue_L(&Q, p->rchild);

    }

    }

    }

    int main()

    {

    BiTree T;

    CreateBiTree(&T);

    printf("先序遍历序列: ");

    PreOrder(T);

    printf("\n");

    printf("中序遍历序列: ");

    InOrder(T);

    printf("\n");

    printf("后序遍历序列: ");

    PostOrder(T);

    printf("\n");

    printf("层次遍历序列: ");

    LevelOrder(T);

    printf("\n");

    return 0;

    }

    00分享举报

    更多相关内容
  • 二叉树层次遍历

    千次阅读 2020-11-24 21:15:58
    我们可以使用个队列来进行层次遍历,根据队列先进先出的特点,可以有如下所示的过程来对一二叉树进行层次遍历: 接下来用代码实现上述过程: void LevelOrder(BtNode* ptr) { if (ptr == NULL) { ...

    二叉树除了先序遍历、中序遍历、后序遍历以外还有层次遍历,比如说下面这颗二叉树的层次遍历的结果为:ABGCDHEF

    在这里插入图片描述
    我们可以使用一个队列来对它进行层次遍历,根据队列先进先出的特点,可以有如下所示的过程来对一颗二叉树进行层次遍历:

    在这里插入图片描述

    接下来用代码实现上述过程:

    void LevelOrder(BtNode* ptr)
    {
    	if (ptr == NULL)
    	{
    		return;
    	}
    	queue<BtNode*> que;
    	que.push(ptr);
    	while (!que.empty())
    	{
    		ptr = que.front();
    		que.pop();
    		cout << ptr->data << " ";
    		if (ptr->leftchild != NULL)
    		{
    			que.push(ptr->leftchild);
    		}
    		if (ptr->rightchild != NULL)
    		{
    			que.push(ptr->rightchild);
    		}
    	}
    	cout << endl;
    }
    

    从运行结果可以看到我们完成了二叉树的层次遍历:

    在这里插入图片描述
    接着我们在介绍另外一种遍历方式,“S”型遍历,如下面一颗二叉树遍历的结果,图解如下:

    在这里插入图片描述
    最终遍历结果为AGBCDHFE。

    我们可以通过两个栈来实现这样的遍历,代码如下:

    void SorderTree(BtNode* ptr)
    {
    	if (ptr == NULL) return;
    	stack<BtNode*> lst;
    	stack<BtNode*> rst;
    	lst.push(ptr);
    	while (!lst.empty() || !rst.empty())
    	{
    		while (!lst.empty())
    		{
    			ptr = lst.top();
    			lst.pop();
    			cout << ptr->data << " ";
    			if (ptr->leftchild != NULL)
    			{
    				rst.push(ptr->leftchild);
    			}
    			if (ptr->rightchild != NULL)
    			{
    				rst.push(ptr->rightchild);
    			}
    		}
    		while (!rst.empty())
    		{
    			ptr = rst.top();
    			rst.pop();
    			cout << ptr->data << " ";
    			if (ptr->rightchild != NULL)
    			{
    				lst.push(ptr->rightchild);
    			}
    			if (ptr->leftchild != NULL)
    			{
    				lst.push(ptr->leftchild);
    			}
    		}
    	}
    }
    

    运行结果如下:

    在这里插入图片描述
    我们所要求的“S”型遍历结果也出来了。

    展开全文
  • 给定二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7],  3  / \  9 20  / \  15 7 返回其自底向上的...
  • 层次遍历二叉树是大家再熟悉不过的二叉树操作了,看到这个算法通常会联想到队列,没错,叨叨Chen设计的层次遍历算法也是用到了队列(先进先出),下面一起进入算法游乐场吧。It's show time!Punchline--------------...

    0a91a833a4bf0bb4c4e06abdcda746eb.png

    Today,叨叨Chen继续给大家分享算法啦。层次遍历二叉树是大家再熟悉不过的二叉树操作了,看到这个算法通常会联想到队列,没错,叨叨Chen设计的层次遍历算法也是用到了队列(先进先出),下面一起进入算法游乐场吧。

    It's show time!

    Punchline-------------------------------------------------------------------

    Task:用户以广义表的形式输入二叉树,以此创建二叉树,再通过层次遍历算法将二叉树输出,输出的结点之间用空格表示,行末不需要多余的空格。

    Input:输入一行,以广义表的形式表示的二叉树。

    Output:输出也是一行,为该二叉树按层次遍历的结果序列,每个元素之间用空格隔开,行末不需要多余的空格。

    Realize:

    1. 创建二叉树(createTree):根据广义表的形式创建二叉树,那么会联想到用栈的方法;
    2. 层序遍历输出二叉树(Layerprint):一层一层从左至右读取、获取数据,思路如下,
    • 初始化队列,如果树不为空,则先将根结点入队,判断队列是否为空,进入循环;
    • 在循环里,出队,读取数据;
    • 输出空格,但需要判断情况,有三种情况:(1)当前队列不为空;(2)队列为空,但是出队列的结点有左孩子;(3)队列为空,但是出队列的结点有右孩子;【(2),(3)的情况可以举个例子更形象,比如当你将根结点入队后,紧接着又出队列读取数据,此时队列是空的,但是如果其有孩子,那么就应该继续输出空格。】
    • 如果根结点有左孩子,则左孩子入队列;如果根结点有右孩子,则右孩子入队列,进入下一次循环。

    ----------------------------------------------------------------------Time---

    //加载库;这里不再多说了,详细情况请看叨叨Chen的往期文章。

    #include

    note:这里使用宏定义来设置Max的值,是为了限制输入的广义表形式的最大长度。当然读者可以使用“const int Max=40;”,叨叨Chen使用宏定义是为了更加熟悉宏定义的本质含义——替换思想。

    //定义树的结点(Node),链式队列的结点(QNode,Queue,可以这么理解,QNode是队列里存储元素值域和指针域的结构体,Queue是存储了两个指向QNode的指针的结构体,具体细节可自行查阅链式队列的资料。)

    typedef 

    note:

    • 为了更清楚理解结构体的相互使用,叨叨Chen这里没有使用结构体嵌套的方法,读者可以自己设计一下。这里可以很清楚的看到,QNode的结点里是存放的Node(树结点)类型的。
    • 从工程的角度来说,读者可以将头文件和定义的结构体放在头文件(xxx.h)里,在源文件里加载头文件(#include"xxx.h";)即可。

    //实现Task的功能如下:

    //根据二叉树的广义表形式创建二叉树
    

    //主函数

    int 

    note:这里有读者会觉得cin.getline()没必要,但是请思考一个问题,如果用户只输入一个空格呢,这时候,如果用cin,鼠标会一直闪烁,不会进入程序的下一步,就没办法得到树为空的反馈。

    嘿嘿嘿~快乐的时光总是短暂的,又到了。。。。。。

    欢迎读者提出批评和建议,叨叨Chen会采取好的建议追加在文章后面,大家一起学习喔!

    2020.10.09------------------------------------------------------------------It still comes---


    展开全文
  • 二叉树层次遍历算法

    千次阅读 2021-10-15 08:03:10
    层次遍历是把树看成从上到下的若干层:根结点在第层,根结点的孩子在第二层,根结点的孩子的孩子在第三层,然后依次类推,从上到下层来访问,每层从左到右依次访问,每个结点只访问次 如何实现?...

    前面学的二叉树的遍历是把二叉树看作3个部分:根,左子树,右子树,然后我们以此来访问3个部分

    而层次遍历是把树看成从上到下的若干层:根结点在第一层,根结点的孩子在第二层,根结点的孩子的孩子在第三层,然后依次类推,从上到下一层一层来访问,每一层从左到右依次访问,每个结点只访问一次

    如何实现?

    思路:用队列

    先将根结点入队,接下来就不断从队伍中去出队一个结点,同时,如果他有左右孩子,就分别将他的左右孩子入队,这就是访问顺序:首先是根结点,然后是他的左右孩子,左右孩子后面是他的左孩子的左右孩子,右孩子的左右孩子......

    例子:

    将a出队的同时,将他的两个孩子b,f入队

    b出队的同时将c,d入队.....

    这就是层次遍历的思路:先从根节点开始,依次是他的左右孩子,到左右孩子时,再分别把左右孩子的孩子继续入队,然后再将下一层入队,一层一层入队,再按入队的顺序一个一个出队

    算法:

     

    用顺序循环队列。用数组data[MaxSize]来存放队中的元素,另外我们有两个指针分别表示队头和队尾

    首先初始化这个队列,InitQueue(qu)

     

    然后将根节点b入队qu

    再从队列中出队元素,出队前判断队列是否为空!QueueEmpty

    若为空,就将队头元素用出队deQueue(qu,p)

    输出他的值p->data,

     

    若存在左孩子,就将左孩子入队

     

    若存在右孩子,就将右孩子入队

    当队列中没有元素时,循环结束

    用到了队列初始化,入队,判断队空,出队操作

     

    展开全文
  • 二叉树的概念以及结构 二叉树是n(n>=0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者由个根节点和两互不相交的、分别称为根节点的左子树和右子树组。...层次遍历 ...
  • 利用队列对二叉树进行层次遍历

    千次阅读 2018-03-01 13:25:59
    利用队列对二叉树进行层次遍历,需要实现:1队列数据结构,并实现出队,入队,判断队列是否为空三个函数操作2二叉树数据结构,并实现创建二叉树层次遍历二叉树两个函数操作层次遍历的算法思想及代码如下图所示/*...
  • 102.二叉树层次遍历 107. 二叉树的层序遍历 II 199. 二叉树的右视图 637. 二叉树的层平均值 429. N叉树的层序遍历 515. 在每个树行中找最大值 116. 填充每个节点的下个右侧节点指针 117. 填充每个节点的下个...
  • ①初始化个辅助队列 ②根结点入队 ③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话) ④重复③直至队列为空 ①初始化个辅助队列
  • 7-1 二叉树层次遍历 (25 分) 编写程序,要求实现(1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 ...
  • C语言实现二叉树层次遍历

    千次阅读 多人点赞 2020-07-27 21:29:07
    进行层次遍历时构建个辅助队列,先将二叉树根节点入队,然后出队,访问出队结点,若它有左子树,将左子树根节点入队,然后出队,访问出队结点…,右子树也同样如此,循环往复直到队列为空。 2.代码 #include<...
  • 二叉树的层级遍历 二叉树的层级遍历:简单地讲就是从二叉树的根节点开始,层递进,逐层遍历二叉树的每个元素 ....
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2 解题思路: 已知后序序列和中序序列...
  • 二叉树层次遍历(C语言实现)

    万次阅读 多人点赞 2019-05-10 21:53:21
    思路:层次遍历就是层遍历,这棵二叉树层次遍历序列为5 2 11 3 6 4 8,先上到下,先左到右。实现层次遍历用队列比较方便,因为是先进先出(FIFO)。首先把5入队,然后再输出队首元素,并且把队首元素的左...
  • 首先创建一棵搜索二叉树,搜索二叉树的代码在我之前的博客已经贴出来了,这里我就不细讲了,感兴趣的小伙伴可以去翻翻之前的博客或者是网上搜索其他人写的搜索二叉树代码都是可以的,原理上差别不大应该: ...
  • 层次遍历二叉树

    2014-10-24 12:14:16
    层次遍历二叉树
  • 二叉树层次遍历 编写程序,要求实现 (1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 struct BiNode...
  • 二叉树层次遍历(c++)

    千次阅读 2020-08-13 00:33:41
    层次遍历 :对于二叉树,从根结点开始,按从上到下,从左到右的顺序访问每个结点 思路 使用队列 1,将根结点入队 2,队不为空时循环:出列个结点,打印它 ①有左孩子,将左孩子入队 ②有右孩子,将右孩子...
  • 给定二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20  / \  15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] 想法和...
  • 题目1 原创文章 81获赞 40访问量 3万+ 关注 私信 展开阅读全文 作者:Leadingme
  • 二叉树层次遍历详解

    2022-06-30 22:01:26
    二叉树层次遍历
  • 题目描述:(使用链队列进行操作) 从键盘输入个字符串,其中#表示空。 例:右图输入为 Sample Input HDB#A##C##G#FE### 使用队列将二叉树分层输出。 Sample Output HDGBCFAE 思路: 先根节点入队,然后...
  • 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树存储结构 2.求二叉树的先序遍历 3.求二叉树...
  • Java 二叉树层次遍历

    千次阅读 2020-06-06 16:28:41
    Java 二叉树层次遍历

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,595
精华内容 21,038
热门标签
关键字:

对一棵二叉树进行层次遍历