精华内容
下载资源
问答
  • 数据结构——二叉树的层次遍历

    千次阅读 2018-11-21 18:43:05
    二叉树的层次遍历 #include<stdio.h> #include<stdlib.h> #include<string.h> #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 typedef struct Node{ //...

    二叉树的层次遍历

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define OK      1
    #define TRUE    1
    #define FALSE   0
    #define ERROR   0
    
    typedef struct Node{        //二叉树的链式存储结点 
    	char data;
    	struct Node *Lchild;
    	struct Node *Rchild;
    }BiTNode,*BiTree;
    
    //先序遍历的递归算法创建二叉树的存储
    void CreateBiTree(BiTree *root){      //形参采用二级指针,实参为结点孩子域地址 
    	char ch;
    	ch=getchar();
    	
    	if(ch=='#')    *root=NULL;
    	else{
    		*root=(BiTree)malloc(sizeof(BiTree));
    	    (*root)->data=ch; 
    	    CreateBiTree(&((*root)->Lchild));
    	    CreateBiTree(&((*root)->Rchild));
    	}
    } 
    
    void Visit(char data){
    	printf("%c",data);
    }
    
    /********队列函数*******/
     typedef struct array{      //定义队列结构 
     	BiTree elem;
     	struct array *next;
     }*PLArray; 
     
     typedef struct Node_D{
     	PLArray  front;   //指向队头 
     	PLArray  rear;    //指向队尾 
     	int len;          //队列实际长度 
     }*pNode;
    void InitArray(pNode &S){    //构造空队列 
    	PLArray q=(PLArray)malloc(sizeof(PLArray)); //申请新结点
    	S=(pNode)malloc(sizeof(pNode)); 
    	S->front=q;
    	S->rear=q;
    	S->front->next=NULL;
    	S->len=0; 
    	
    }
    
    int Push(pNode &S,BiTree e){    //插入数据e为队列的队尾 
    	PLArray p=(PLArray)malloc(sizeof(PLArray));  //申请新结点 
    	p->elem=e;
    	
    	p->next=NULL;
    	S->rear->next=p;   //将结点插入到队尾 
    	S->rear=p;         //修改队尾指针 
    	S->len++; 
    }
    
    int Pop(pNode &S,BiTree &e){    //删除队头元素,,用e返回其删除数据 
    	if(S->front==S->rear)  return FALSE;
    	PLArray p=S->front->next;   //p指向队头
    	e=p->elem;
    	S->front->next=p->next;   //修改头结点的指针域
    	if(S->rear==p) S->rear=S->front;   //最后元素被删除
    	S->len--;
    	return OK ;
    }
    
    int ArrayEmpty(pNode &S){    //判断队列是否为空 
    	if(S->len==0)  return TRUE;
    	else           return FALSE;
    } 
    
    int Refer(pNode &S,BiTree &e) {  //查询队头元素 
    	e=S->front->next->elem;
    }
    
    void LevelOrder(BiTree T){   //层次遍历    
         pNode S;
         InitArray(S);
         BiTree p;
         Push(S,T);
         while(!ArrayEmpty(S)){
         	Pop(S,p);
         	Visit(p->data);
         	if(p->Lchild!=NULL)
         	    Push(S,p->Lchild);
         	if(p->Rchild!=NULL)
    		    Push(S,p->Rchild);    
    	 }
    } 
    
    int main(){
    	BiTree T;
    	CreateBiTree(&T);
    	LevelOrder(T);
    	return 0;
    } 
    
    展开全文
  • 数据结构 二叉树层次遍历 C语言

    千次阅读 多人点赞 2018-12-19 16:21:08
    C语言 数据结构 二叉树层次遍历 原创作者:小林 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define max 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct ...

    C语言 数据结构 二叉树层次遍历

    原创作者:小林
    #include<stdio.h>
    #include<stdlib.h>
    #define max 100

    typedef int ElemType;

    typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    } BiTNode,*BinTree;

    //建立二叉树

    void CreateBinTree(BinTree &T){ //按先序次序输入,构造二叉链表表示的二叉树T
    int num;
    scanf("%d",&num);//输入函数。
    if(num==-1){
    T=NULL;
    }//输入#时为空
    else{
    T=(BinTree)malloc(sizeof(BiTNode));
    T->data=num;
    CreateBinTree(T->lchild);
    CreateBinTree(T->rchild);
    }
    }

    // 遍历二叉树
    void LevleOrder(BinTree T){ //从第一层开始,从左到右

    BinTree Queue[max],p; //用一维数组表示队列,front和rear分别表示队首和队尾指针

    int front,rear;

    front=rear=0;

    if (T) //若树非空
    {

    Queue[rear++]=T; //根结点入队列

    while (front!=rear){ // 队列非空
    p=Queue[front++]; // 队首元素出队列,并访问这个结点
    printf("%d",p->data);

    if (p->lchild!=NULL) Queue[rear++]=p->lchild; //左子树非空,入队列
    if (p->rchild!=NULL) Queue[rear++]=p->rchild;
    }
    }

    }

    //按要求输出二叉树

    int main() {

    BinTree T;

    printf("\n创建二叉树\n");
    CreateBinTree (T);
    printf("\n层次遍历二叉树 并输出遍历结果\n"); LevleOrder(T);

    return 0; }

    例题:
    二叉树的层次遍历
    关于二叉树的遍历方法,除了我们所熟知的先序遍历、中序遍历和后序遍历方法外,还有一种遍历方法,称为层次遍历。所谓层次遍历方法是指从二叉树的根结点开始自上而下,每一层从左到右逐一访问每个结点。例如,若二叉树如下所示。
    在这里插入图片描述

    则该二叉树的层次遍历序列为:1 2 3 5 6 7 10 11 13
    假设二叉树采用二叉链表存储结构,其二叉链表的类型定义如下。
    typedef struct bnode{
    int data; //结点的数据域用大于0的整数表示
    struct bnode *lchild;
    struct bnode *rchild;
    }bnode,*btree;
    要求:
    首先采用先序遍历的方法来创建一棵二叉树,创建时用-1来表示空树。最后输出所创建二叉树的层次遍历序列。
    例如,如果要创建上图所示的二叉树:
    应输入:
    1 2 -1 5 10 -1 -1 11 -1 -1 3 6 -1 13 -1 -1 7 -1 -1
    则输出:
    1 2 3 5 6 7 10 11 13

    运行结果如下:在这里插入图片描述

    展开全文
  • 数据结构-二叉树层次遍历

    千次阅读 多人点赞 2018-10-23 14:57:49
    首先介绍下二叉树的层次遍历即按照顺序对树节点依次访问,如下图: 顺序遍历的结果为:ABCDEFGHIJK 我们可以借助一个队列来实现二叉树的层次遍历;思路如下: 先将二叉树根节点入队,然后出队,访问该节点,...

    首先介绍下二叉树的层次遍历即按照顺序对树节点依次访问,如下图:

    顺序遍历的结果为:ABCDEFGHIJK

    我们可以借助一个队列来实现二叉树的层次遍历;思路如下:

    先将二叉树根节点入队,然后出队,访问该节点,如果有左子树,则将左子树根节点入队;如果有右子树,则将右子树根节点入队。然后出队,对出队节点访问,如此循环

    直到队列为空。

    代码实现:

    
    //
    // Created by Administrator on 2018/6/5.
    //
    /**
     * 层次遍历:通过辅助队列实现二叉树的层次遍历
     */
    #include "stdio.h"
    #include "stdlib.h"
    
    /**
     * 定义一棵树
     */
    typedef struct {
        char data;
        struct BitTreeNode *lchild, *rchild;
    } BitTreeNode, *BitTree;
    
    /**
     * 定义一个队列节点
     */
    typedef struct {
        BitTree data;//节点元素
        struct QNode *next;//节点指向下一个节点的指针域
    } QNode;
    
    /**
     * 定义一个队列:链式队列
     */
    typedef struct {
        //队列的头指针,尾指针:头指针始终指向头节点,尾指针随着元素入队向后移动
        // 如果队列为空则头指针=尾指针同时指向头节点
        QNode *front, *rear;
    } LinkQueue;
    
    /**
     * 前序法创建树
     * @param tree
     * @return
     */
    BitTree createTree(BitTree tree) {
        char c;
        scanf("%c", &c);
        if (c == '#') {
            return 0;
        } else {
            tree = (BitTree) malloc(sizeof(BitTreeNode));
            tree->data = c;
            tree->lchild = createTree(tree->lchild);
            tree->rchild = createTree(tree->rchild);
        }
        return tree;
    }
    
    /**
     * 初始化队列
     * @param q
     */
    void initQueue(LinkQueue *q) {
        q->front = q->rear = (QNode *) malloc(sizeof(QNode));
        q->front->next = NULL;
    }
    
    /**
     * 入队操作
     * @param q
     * @param tree
     */
    void enQueue(LinkQueue *q, BitTree tree) {
        //开辟节点空间
        QNode *s = (QNode *) malloc(sizeof(QNode));
        //节点数据域赋值
        s->data = tree;
        //队列尾指针的指针域指向该节点
        q->rear->next = s;
        //队列尾指针移动到该节点
        q->rear = s;
    }
    
    /**
     * 出队操作
     * @param q
     * @return
     */
    BitTree deQueue(LinkQueue *q) {
        //获取头结点的下一个节点
        QNode *s = q->front->next;
        //获取数据元素
        BitTree tree = s->data;
        //队列头指针的指针域指向出队节点的下一个节点
        q->front->next = s->next;
        if (s == q->rear) {
            //如果出队节点为队列尾指针,则说明该节点为队列的最后一个元素节点
            //将尾指针指向头指针(头指针指向了头结点)
            q->rear = q->front;
        }
        free(s);
        return tree;
    }
    
    void visit(char data) {
        printf("%c", data);
    }
    
    /**
     * 二叉树层次遍历
     * @param tree
     * @param queue
     */
    void levelOrder(BitTree tree, LinkQueue queue) {
        initQueue(&queue);
        BitTree p;
        enQueue(&queue, tree);
        while (queue.front != queue.rear) {
            p = deQueue(&queue);
            visit(p->data);
            if (p->lchild != NULL) {
                enQueue(&queue, p->lchild);
            }
            if (p->rchild != NULL) {
                enQueue(&queue, p->rchild);
            }
        }
    }
    
    int main() {
        LinkQueue queue;
        BitTree tree;
        tree = createTree(tree);
        printf("层次遍历结果:\n");
        levelOrder(tree, queue);
        return 0;
    }

    展开全文
  • 数据结构层次遍历二叉树 C语言版

    千次阅读 多人点赞 2017-08-27 17:18:55
    //层次遍历二叉树并输出结点的算法 #include #include typedef struct NNode { char data; struct NNode *LChild; struct NNode *RChild; } BiTNode,*BiTree; //定义二叉树结点和结点指针 typedef BiTree ...
    //层次遍历二叉树并输出结点的算法
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct NNode
    {
    	char data;
    	struct NNode *LChild;
    	struct NNode *RChild;
    } BiTNode,*BiTree;   //定义二叉树结点和结点指针
    
    typedef BiTree QueueElementType;
    typedef struct Node
    {
        QueueElementType data;
        struct Node  *next;
    } LinkQueueNode;  //定义队列结点
    typedef struct
    {
        LinkQueueNode *front; //队列头结点指针
        LinkQueueNode *rear;  //队列尾结点指针
    } LinkQueue;  //定义队列
    
    int InitQueue(LinkQueue *Q )  //初始化队列
    {
        Q->front=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
        if(Q->front != NULL)
        {
            Q->rear=Q->front;
            Q->front->next=NULL;
            return 1;
        }
        else return 0;//溢出
    }
    
    int EnterQueue(LinkQueue *Q,QueueElementType x) //元素x入链队列 尾插法
    {
        LinkQueueNode * newnode;
        newnode=(LinkQueueNode *) malloc(sizeof(LinkQueueNode));
        if(newnode != NULL)
        {
    
            newnode->data=x;
            newnode->next=NULL;
            Q->rear->next=newnode;
            Q->rear=newnode;
            return 1;
        }
        else return 0;
    }
    
    int DeleteQueue(LinkQueue *Q,QueueElementType *x ) //链队列出队 从开始的头开始取
    {
        LinkQueueNode *p;
        if(Q->front==Q->rear)
            return 0;
        p=Q->front->next;
        Q->front->next=p->next;
        if(Q->rear==p )
             Q->rear=Q->front;  //如果去掉结点p后,队列为空 不要忘记将队列置空
        *x=p->data;
        free(p);
        return 1;
    }
    
    int IsEmpty(LinkQueue *Q) //队列为空返回1  不为空返回0
    {
        if(Q->front==Q->rear ) return 1;
        else return 0;
    }
    
    
    void CreateBiTree(BiTree *bt)  //用先序遍历创建二叉树
    {
    	char ch;
    	ch=getchar();
    	if(ch=='.') (*bt)=NULL;
    	else
    	{
    		*bt=(BiTree)malloc(sizeof(BiTNode));
    		(*bt)->data=ch;
    		CreateBiTree(&((*bt)->LChild));
    		CreateBiTree(&((*bt)->RChild));
    	}
    }
    
    void PreOrder(BiTree root) //先序遍历二叉树
    {
    	if(root!=NULL)
    	{
    		printf("%c",root->data);
    		PreOrder(root->LChild);
    		PreOrder(root->RChild);
    	}
    
    }
    
    int LayerOrder(BiTree bt)   //层次遍历二叉树 成功遍历返回1 失败返回0
    {
        LinkQueue Q;
        BiTree p;
        InitQueue(&Q);
        if(bt==NULL) return 0;
        EnterQueue(&Q,bt);
        while(!IsEmpty(&Q))
        {
            if(DeleteQueue(&Q,&p));
                printf("%c ",p->data);
            if(p->LChild) EnterQueue(&Q,p->LChild);
            if(p->RChild) EnterQueue(&Q,p->RChild);
        }
        return 1;
    }
    
    int main()
    {
        BiTree bt;
    	printf("用先序遍历创建二叉树 请输入树的内容  形式如AB..CD...的格式\n") ;
    	CreateBiTree(&bt);
    
        PreOrder(bt);
        printf("\n");
        if(LayerOrder(bt)) printf("层次遍历成功\n");
        else printf("层次遍历失败\n");
    
        return 0;
    }
    

    展开全文
  • 数据结构例程 二叉树的层次遍历算法
  • 数据结构与算法书籍推荐

    万次阅读 多人点赞 2019-03-16 18:49:31
    学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。 1. 入门级 针对刚入门的同学,建议不要急着去看...
  • 数据结构与算法:为什么要学习数据结构与算法 数据结构与算法到底是什么 数据结构数据结构指的是计算机中数据的组织形式,分为逻辑结构和物理结构两个维度。其中,逻辑结构是对数据组织形式在逻辑上的抽象,物理...
  • 数据结构——二叉树先序、中序、后序三种遍历二叉树先序、中序、后序三种遍历三、代码展示: 二叉树先序、中序、后序三种遍历 先序遍历:3 2 2 3 8 6 5 4 中序遍历:2 2 3 3 4 5 6 8 后序遍历: 2 3 2 4 5 6 8 3 ...
  • -树是非线性的数据结构,树的结点没有固定的编号方式 新的需求 -为通用树机构提供新的方法,快速遍历每一个结点 设计思路(游标) -在树中定义一个游标(GTreeNode<T>*) -遍历开始前将游标指向根节点...
  • 数据结构习题及解析一

    千次阅读 多人点赞 2018-12-20 09:51:36
    数据结构习题解析解析:本题考点是顺序表的基本特点。 顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。...
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...
  • 设计一个利用队列实现二叉树层次遍历的程序。假设二叉树结点的元素数据类型为字符型,二叉树以二叉链表存储。利用二叉树的递归结构性质,通过读取键盘输入的如图所示二叉树的先序序列,建立其二叉链表。
  • 二叉树主要的遍历方式有四种,先序遍历,中序遍历,后序遍历和层次遍历(层次遍历放到下一篇博客单独讲)。 1、先序遍历 a.访问根结点 b.先序遍历左子树 c.后序遍历右子树2、中序遍历 a.先序遍历左子树 b.访问...
  • 本文是数据结构基础系列(6):树和二叉树中第12课时层次遍历算法的例程。【二叉树的层次遍历算法】  实现二叉树的层次遍历算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。  请利用...
  • 数据结构层次 整个Siebel的数据的层次结构分为三个层次,每一个层次都对应了下一个层次的相应的元素,一个层次的改动不影响另一个层次的稳定性,一张表现他们层次的经典图如下:可以看到,一个BC其实对应的就是一个...
  • 数据结构——二叉树的结点的层次

    千次阅读 2018-11-21 18:45:30
    二叉树结点的层次 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; typedef struct Node{ //二叉树的链式存储结点 char data; int depth; struct Node *...
  • preface:主要是最近用层次遍历比较多,先中后序的遍历都有递归与非递归的方式,也比较容易明白,但层次不是很熟悉,自己不是很擅长,故记录下来。 递归与非递归 class TreeNode(object): def __init__(self, x): ...
  • 我们对数据结构的理解达到了什么层次?我们需要达到的层次是什么? 第0层次:“数据结构是什么?” 第0层次是指对数据结构一无所知。我们从来没有听说过数据结构,从来没有注意到对数据进行合理的组织能够大幅度...
  • 对于非递归的先序、中序、后序遍历要用到栈(在之前的博文中已经提到了具体的实现过程),而在层次遍历中要使用到另一种数据结构——队列,这个在之前博文中没有提到,因此在本篇博文中将会给出简单实现。 在本篇博文...
  • 数据结构:线性结构和非线性结构的理解

    万次阅读 多人点赞 2019-03-02 22:54:09
    我们知道数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图: 我们这里主要说一下线性结构和非线性结构 1. 线性结构 线性结构是什么? 数据结构中线性结构指的是数据元素之间存在着“一对一”的...
  • 数据结构~14.二叉树的层次遍历与案例分析

    万次阅读 多人点赞 2020-08-12 14:39:58
    二叉树遍历的深入 本文是上一篇文章的后续,详情点击该链接~ 层次遍历
  • #include<stdio.h> /* EOF(=^Z或F6),NULL */ #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status;...创建二叉树时按层次顺序输入,找到最后一个非空点,按层次顺序输出。
  • 数据层次结构建模

    千次阅读 2018-05-21 17:13:20
    1,在现实世界中,有很多现象存在层次结构,公司的人事职称是典型的层次结果,如下图Sql Server是关系型DB,适合存储二维关系的数据,如何存储具有层次结构数据了?需要使用一个字段ParentID表示上级ID,示例表结构...
  • 数据结构 第12讲 二叉树的层次遍历

    千次阅读 2017-11-14 11:41:03
    数据结构 第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示: 图1 ...
  • 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点开始,首先将根节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作: 1、访问该元素所指向的节点 2、若该元素
  • 二叉树的层次遍历(完整版)

    千次阅读 2020-07-04 16:47:08
    二叉树的层次遍历 二叉树的层次遍历也被称为宽度优先遍历(BFS)。可以用递归实现也可以用队列等数据结构实现,下面介绍以uva的trees on the level 为例介绍BFS的完整代码: ...
  • 数据结构(1)—— 数据结构的三大结构

    万次阅读 多人点赞 2016-09-07 22:49:23
    数据结构分三个层次:逻辑结构(抽象层)、物理结构(结构层)、运算结构(实现层)。1.1 数据结构的逻辑结构逻辑结构指人对数据之间关系的理解和看法,逻辑结构和计算机无关。 逻辑结构: 1、集合结构:这种结构...
  • 结构   二叉树层次遍历算法: template <typename T> template <typename VST> //元素类型、操作器 void BinNode<T>::travLevel(VST& visit) { //二叉树局次遍历算法 Queue(T)> Q; //辅劣队列 Q....
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 学习数据数据结构的意义

    千次阅读 2018-12-31 14:09:05
    什么是数据结构,为什么要学习数据结构数据结构是否是一门纯数学课程?它在专业课程体系中起什么样的作用?我们要怎么才能学好数据结构?… 相信同学们在刚开始《数据结构》这门课的学习时,心里有着类似前面几个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 533,079
精华内容 213,231
关键字:

数据结构层次

数据结构 订阅